Deterministic Algorithms for Robotic Task and Motion Planning
Our goal is to investigate deterministic algorithms for robotic task and motion planning.
In the 1980s, roboticists produced strong decidability results for motion planning. However, in the 1990s, the robotics community shifted to almost exclusively use sample-based appraoches. While sampled-based planners are very fast, they have few theoretical guarantees and are provably incapable of solving certain types of task and motion planning (TAMP) problems. We are investigating deterministic approaches for TAMP, which have provable space and run-time guarantees. While guaranteed deterministic algorithms for these problems are generally intractable in the worst case, they can lead to insights on what makes problems hard and lead to new types of practical algorithms.