computational robotics

from tasks to motions

Multi-Goal Motion Planning

In video games, mobile agents often need to visit several goal regions while seeking to minimize the distance traveled and avoiding collisions with obstacles. This multi-goal motion-planning problem presents unique computational challenges as it intertwines a hard discrete problem, namely the Traveling Salesman Problem (TSP), with physical constraints imposed by the vehicle dynamics and obstacle avoidance. It is not sufficient to just compute an ordering of the regions that minimizes the distance traveled, in itself a hard problem even when a closed tour is not required~\cite{KumarCK13}, but a collision-free and dynamically-feasible trajectory must be planned to enable the vehicle to reach each goal. Vehicle dynamics constrain the feasible motions by imposing limits on velocity, turning radius, directions of motions, making it difficult to navigate in unstructured environments characterized by numerous obstacles and narrow passages. In order to produce physically-realistic motions, vehicle dynamics need to be taken into account during planning. Consequently, the planner needs to work with simulations of vehicle dynamics based on differential equations or with physics-based game engines which provide more realistic simulations of general rigid-body dynamics.

Multi-Group Motion Planning

Multi-group motion planning provides a generalization of the multi-goal motion-planning problem. In multi-group motion planning, the overall set of goal regions is divided into groups and at least one goal per group needs to be visited while seeking to minimize the traversal cost. Such formulation provides a general setting that allows grouping of similar goals. It also has applications in modern video games with more interesting capabilities where a mobile agent has to visit multiple regions. Multi-group motion planning poses significant challenges. Its discrete counterpart corresponds to the Generalized Traveling Salesman Problem (GTSP), which extends TSP by grouping graph vertices and requiring visiting at least one vertex per group. Moreover, constraints imposed by the dynamics and collision avoidance may make it impossible for the vehicle to follow a particular GTSP tour. Thus, it is generally infeasible to separate the two problems by first computing a GTSP tour that ignores the physical constraints and then seeking to follow the tour. These intertwined dependencies make multi-group motion planning a challenging problem.

To efficiently solve the multi-group motion-planning problem, this work combines sampling-based motion planning with a GTSP solver. The approach is based on a hybrid search, where the expansion of a motion tree in the continuous state space is guided by heuristic costs and GTSP tours computed over a discrete abstraction. The discrete abstraction is obtained via a probabilistic roadmap constructed over a low-dimensional configuration space resulting from a simplified problem setting which relaxes the constraints imposed by the vehicle dynamics. The motion tree is incrementally expanded by adding collision-free and dynamically feasible trajectories as branches. The roadmap is used to induce a partition of the motion tree based on the nearest roadmap configuration to a tree vertex and the goal groups that have yet to be reached by its successors. Moreover, the roadmap provides GTSP tours that can effectively guide the expansion from each partition toward the remaining goal groups. Experiments with ground and aerial vehicles modeled by differential equations and physics-based engines demonstrate the efficiency and scalability of the approach.

Related Publications

  • Plaku E, Rashidian S, and Edelkamp S (2016): "Multi-Group Motion Planning in Virtual Environments." Computer Animation and Virtual Worlds, in press  [publisher]  [preprint]
  • Rashidian S, Plaku E, and Edelkamp S (2014): “Motion Planning with Rigid-Body Dynamics for Generalized Traveling Salesman Tours.” ACM SIGGRAPH Motion in Games, pp. 87–96  [publisher]  [preprint]
  • Edelkamp S and Plaku E (2014): “Multi-goal Motion Planning with Physics-based Game Engines.” IEEE Conference on Computational Intelligence and Games, pp. 115--122  [publisher]  [preprint]