CS Seminar – Stefan Edelkamp (King's College London)

Let's get physical, task and motion planning and all that

In the clothes of vehicle routing, multi-goal task planning has been an apparent optimization question to operation research and logistics for a fairly long time. We will present novel advances in high-speed solving these discrete planning problems. With fast single-source shortest path search, the in- or outdoor map for the vehicle fleet is condensed into a graph of customer orders. For one vehicle this setting corresponds to variants of the NP-hard traveling salesman problem, while for several vehicles and according to the dynamics in the orders within a multi-agent simulation system, we support negotiating agents that offer multimodal transport services.

While the discrete multi-goal task planning problem is already hard, the "physical" motion planning problem is much more demanding: the integration of task and motion planning is considered the most important problem in nowadays robotics. 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 use 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.

February 13, 2020 (Thursday)
Room 205, Building E, Karlovo nám. 13


Stefan Edelkamp

Stefan Edelkamp is professor at King's College London, leading the planning group. Before that he was working 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. He earned his Ph.D. from Freiburg University and led a junior research group at Technical University of Dortmund. His scientific interest is Algorithmic Intelligence, and includes areas such as Heuristic Search, Action Planning, Game Playing, Machine Learning, Motion Planning, Multi-Agent Simulation, Model Checking, External-Memory Algorithms, Parallel and Distributed Computing, Algorithm Engineering, Computational Biology, Decision Diagrams, Priority Queues, Navigation Systems, Network Security, and Intrusion Detection. Stefan Edelkamp has organized international conferences, workshops, and seminars and won several performance awards at international planning competitions. Together with Stefan Schroedl he is author of the text book Heuristic Search - Theory and Applications published by Morgan Kaufmann / Elsevier Science.