Task-aware waypoint sampling for planning robots

To achieve a complex task, a robot often needs to navigate in a physical space to complete activities in different locations. For example, it may need to inspect several structures, making multiple observations of each structure from different perspectives. Typically, the positions from which these activities can be performed are represented as waypoints – discrete positions that are sampled from the continuous physical space. Existing approaches to waypoint selection either iteratively consider the entire space or each activity separately, which can lead to task planning problems that are more complex than is necessary or to plans of compromised quality. We offer an approach that produces more efficient plans by performing a one-time computation of the connectivity graph and by prioritizing waypoints from which multiple activities can be performed. In addition, we support user specified performance preferences that represent preferences a system operator may have about the generated task plan but that cannot be directly represented in the map used for navigation, such as areas near doorways where it is preferable that the robot does not stop to perform activities. We demonstrate the performance benefits of our approach on simulated manufacturing tasks in an automated factory.