Techniques to determine region route guiding points using convergence circles

A non-transitory computer-readable storage medium storing computer-executable instructions that, when executed by a processor, cause a computing system to:

• receive a graph comprising points of an ordered connection of regions of a map of a space, each point corresponding to a respective region of the regions;
• determine a start point and an end point of the points in the graph, the start point and end point connected by at least a portion of the graph comprising a subset of the points;
• generate a route between the start point and the end point by:
• (a) designating the end point as a current guide point;
• (b) determining a convergence radius for each point of the subset, the convergence radius representing a non-zero distance from each point and based on a (i) characteristic of a computer-guided vehicle or (ii) a characteristic of the map of the space;
• (c) evaluating, based at least in part on the convergence radii determined for each point of the subset of the points, a visibility criterion between the current guide point and the points in the subset by determining whether each point of a convergence circle centered at a point of the subset of the points is visible from each point of an additional convergence circle centered at the current guide point;
• (d) responsive to an evaluation that a subsequent point fails the visibility criterion, designating an additional point that passed the visibility criterion as the current guide point;
• and
• (e) adding the current guide point to the route;
• and
• causing the computer-guided vehicle to move through the space according to the route.

A robotic system, comprising:

• a guided vehicle;
• a processor of the guided vehicle;
• and
• a memory storing computer-readable instructions that, when executed by the processor, cause the robotic system to:
• obtain a graph comprising points of an ordered connection of regions of a map of a space, each point corresponding to a respective region of the regions;
• determine a start point and an end point of the points in the graph, the start point and the end point connected by at least a portion of the graph comprising a subset of the points;
• generate a route between the start point and the end point by:
• (a) designating the start point as a current guide point;
• (b) determining a convergence radius for each point of the subset of the points in the portion of the graph that is subsequent to the current guide point, the convergence radius representing a non-zero distance from each point and based on a characteristic of the guided vehicle;
• (c) evaluating, based at least in part on the convergence radii determined for each point of the subset of the points, a visibility criterion between the current guide point and subsequent points in the subset of the points by determining whether a convergence circle centered at the subsequent point is visible from an additional convergence circle centered at the current guide point, the convergence circle characterized by the convergence radius, the convergence circle and the additional convergence circle defined by corresponding convergence radii;
• (d) responsive to an evaluation that a subsequent point fails the visibility criterion, designating a prior point as the current guide point;
• and
• (e) adding the current guide point to the route;
• and
• move the guided vehicle through the space according to the route.