Multi-Goal Motion Planning
Speaker: Stefan Edelkamp
Bio
Before joining the AI Center, Faculty of Electrical Engineering, Czech Technical University in Prague (CTU) as Full Professor, Stefan Edelkamp was leading the planning group at King’s College London. During his exciting research career, Stefan was also working in the Department of Computer Science at Freiburg University, at the Institute for Artificial Intelligence, Faculty of Computer Science and Mathematics of the University of Bremen, and at the University of Applied Science in Darmstadt. For a short period of time, he held the position of an Interim Professor at the University of Koblenz-Landau, and at the University Paris-Dauphine. Stefan earned his Ph.D. and habilitation degree from Freiburg University and led a junior research group at Technical University of Dortmund
Abstract
Multi-goal task planning has been an optimization question in Operation Research and Logistics for a long time. We will present novel advances for high-speed solving these discrete planning problems. With fast single-source shortest path search, the map is condensed into a graph of customer orders. While the discrete multi-goal task planning problem is already hard, the “physical” motion planning problem is even more demanding. The integration of task and motion planning is considered one the most important problems in robotics nowadays. Robots have sizes, heading, and velocity, and their motion can often be described only according to non-linear differential equations. The dynamics of movements, existing obstacles and many waypoints to
visit are only some of the challenges to face. In real-world problems, we often have additional constraints like inspecting areas of interest in some certain order, while still minimizing the time for the travel. The trickiest part is to solve the hard combinatorial discrete tasks like the generalized and clustered traveling salesman problems, and – at the same time – providing valid trajectories for the robot. We extend a framework in which a motion tree is steadily grown, and abstractions to discrete planning problems are used as a heuristic guidance for the on-going solution process to eventually visit all waypoints. In case of inspection, we generate the waypoints fully automatically, using a combination of skeletonization methods together with a filtering mechanism based on hitting sets.
Robots used for inspection or moving of goods are also often required to visit certain locations subject to time and resource consumption. This requires not only planning collision-free and dynamically feasible motions, but also reasoning about constraints. To effectively solve this open problem, we couple task planning over a discrete abstraction with sampling-based motion planning over the continuous state space of feasible motions. The discrete abstraction is obtained by imposing a roadmap that captures the connectivity of the free space. We increase the expressiveness and scalability of the approach, as we raise the number of goals and the difficulty of satisfying the time and resource constraints. With our technology we are able to efficiently generate and execute long-term missions in real-time. The robot, the environment model, and the planning problem specification can be modified non-intrusively, essential in many application scenarios. Other topics of interest are robot planning with limits in energy consumption.