From a minimally-invasive medical robot automatically inspecting the surface of a diseased organ to an autonomous quadcopter inspecting the structure of a bridge, robots in a variety of scenarios must plan their motions to efficiently inspect regions of interest. These are examples of robot-inspection planning tasks which arise in diverse applications. Here, we are tasked with planning motions for a robot that enable it to efficiently inspect a region of interest using its on-board sensors. Such an inspection plan should not only inspect the region of interest but also obey the robot’s kinematic constraints, avoid obstacles (e.g., parts of a bridge or sensitive anatomical structures in bridge inspection and medical applications, respectively), and minimize some metric (such as time to completion or distance traveled), all while considering real-world uncertainties (e.g., uncertainty in the robot’s kinematic model or external forces). Inspection planning is extremely challenging and naively-computed inspection plans may enable inspection of only a subset of the region of interest and may be highly suboptimal.
Computing a high-quality inspection plan is important for many applications, e.g., a medical diagnostic inspection plan should minimize procedure duration to decrease the amount of time a patient is under anesthesia, all while thoroughly inspecting the region of interest. Current approaches to computing inspection plans are either highly tailored to specific applications, provide no guarantees on the quality of solution, or come with very long computation times for non-trivial problems, rendering them impractical for real-world applications.
The typical objective of search problems is to find a path between two nodes in a network such that some cost function is minimal on the chosen path, for example finding the shortest travel time between two locations on a street map. Search over large networks is a fundamental problem in computer science with numerous applications in the fields of robotics and artificial intelligence (AI). The larger the network, the more difficult it becomes to find these shortest paths. Furthermore, many applications are concerned with two (or more) competing resources, such as traversal time and energy consumption. Examples include solving transportation problems, planning power-transmission lines, scheduling satellites, and routing packets in computer networks. In these cases, there is a need for bi-objective (or multi-objective) search algorithms, where multiple-dimension cost functions are considered. To address this complicated problem, we combine ideas from existing bi-objective search algorithms with ideas from the AI search community to develop the next generation of optimal and approximately-optimal multi-objective search algorithms that will allow for real-time searches on much larger networks than possible using current techniques.
Coordinating the movement of a fleet of agents or robots is a decades-old family of problems, which has been intensively studied by the robotics and AI communities with applications in diverse settings including assembly, evacuation, micro-droplet manipulation and search-and-rescue. One specific application is the logistics domain: Modern warehouses store inventory pods where a large number of robots autonomously pick up, carry and release the pods from their storage locations to designated dropooff locations where needed goods are manually removed from the pods (to be packaged and then shipped to customers). The successful use of robots in warehouses led to a multi-billion industry led by tech-giants such as Amazon robotics and Alibaba.
We are interested in two types of problems that can be used to model such applications. In the first, called Multi Agent Path Finding (MAPF), the objective is to find collision-free paths for a given set of agents from their start to their goal locations. In the second, called multi-agent pickup and delivery (MAPD), agents have to attend to a stream of delivery tasks. Here, we need to assign each delivery task to an agent. This agent has to first move to the assigned pickup location and then to the assigned delivery location while avoiding collisions with the environment obstacles as well as with other agents.
