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.
If you would like to contact us about our work, please scroll down to the people section and click on one of the group leads' people pages, where you can reach out to them directly.