In the Computational Robotics Lab we seek to deeply understand and to rigorously address the computational challenges that arise when planning for robots. Our research, lying at the intersection of Computer Science and Robotics, is motivated by the key insight that in order to address these challenges, traditional Computer Science algorithms, tools and paradigms need to be revisited. This requires both (i) understanding and analyzing the unique domain-specific computational challenges in robotic planning and (ii) developing algorithms to address these challenges to provide the robotics community foundational tools to solve real-world problems.

A recent talk I gave at the UW robotics seminar describing the work we are doing on planning for continuum robots can be found here.

Inspection Panning

Picture for Inspection Panning
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.
more info
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.

Efficient Bi- and Multi-Objective Search Algorithms

Picture for Efficient Bi- and Multi-Objective Search Algorithms
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.

Multi-Agent Path Finding

Picture for Multi-Agent Path Finding
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.
more info

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.

For some of the open challenges in the field, check out our recent blue-sky paper published at AAMAS 20.

Curvature-Constrained Tours in Robotic Applications

Picture for Curvature-Constrained Tours in Robotic Applications
The multi-goal planning problem (MGPP) is an important planning problem to determine a cost-efficient solution to visit a set of sites. It is a robotic variant of the NP-hard Traveling Salesman Problem (TSP) that is well-studied in Operational Research. However, the MGPP includes challenging generalizations of the regular combinatorial TSP that arise in robotics, where it is necessary to satisfy motion constraints and physical limitations of real robots. The fundamental challenge of solving the MGPP is related to the complexity of determining the travel cost between the individual sites to be visited which depends on the exact sequence of sites visited. Thus, one needs to simultaneously reason both on the order of sites to be visited (an NP-hard combinatorial problem) and on the cost to travel between adjacent sites (a PSPACE-hard continuous problem).
more info

We are interested in the specific variant of the MGPP where the robot has curvature constraints. Namely, it has a minimum turning radius that it can follow. This additional constraint allows modeling a wide range of systems such as UAVs and steerable needles and has attracted increasing attention in the planning community. Arguably, the best-known model for such systems is the Dubins model. Here, the robot is assumed to be a planar system that can only move forward with a constant velocity and a minimum turning radius.

The state of the system is defined by its position (the location of a predefined reference point on the robot) and orientation (the heading of the robot). In the absence of obstacles, the minimal-length path can be computed analytically. Unfortunately, when the environment contains obstacles, the problem is known to be NP-hard. Approximation algorithms exist but these are for the simplified case of a point robot moving amidst known polygonal obstacles and implementing them robustly is highly nontrivial.