Multi-goal task planning has been an optimization question in Operation Research and Logistics for a long time. We are now working on 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.
Join the project as a PhD student or a postdoctoral researcher! More info can be found in the newly published open call.
