` Intelligent and Mobile Robotics


Path planning is one of the most studied problems in robotics. Our research in this area is focused to three main topics: basic motion planning, problem, multi-goal path planning and mission planning.

Motion planning

In the classical path planning problem, the task is to find a path between two given robot configurations. Usually this problem is studied for simple 2D robots moving in a simple environment. However, such a simplification is not suitable for robots with many DOFs moving in a 3D workspaces. A path for such a robot can be found using a configuration space approach. Due to high-dimensionality nature of the configuration space, usually a randomized techniques are used to find a feasible path, for example sampling-based methods like RRT or PRM are usually used. The runtime of these methods can be increased, if a narrow passage is present in the configuration space. The passages are significantly smaller than the other part of the configuration space which, which decreases the probability, that a feasible free configurations will be found in the passage. We are developing techniques for finding paths through a narrow passages in a general configuration space. The optimal motion planning is studied for formations of mobile robots and UAVs.

Hedgehog in a cageAlpha-puzzleExample of motion planning on a terrainManipulation planningProtein docking

Multi-Goal Path Planning

In the standard path planning, the path is found only given two configurations. However, the robots usually move along long trajectories with many goals. In such a case, the path should be designed considering both visiting the goals and minimizing its length. This leads to a multi-goal path planning. Our approach for solving this problem is based on Self-organizing maps (SOM), which allows to desing a multi-criterial fitness functions. The proposed SOM-based methods can be used for solving sensory placement, where the task is to find sensing locations, which allows to see the whole workspace. The path planning through the determined sensing places are then solved as traveling salesman problem if a single robot is considered, or using multiple traveling salesman problem for a group of robots. The watchman routing problem, where the task is to find a shortest path, from which the whole environment can be seen, can be also solved by the SOM-based techniques.

The multi-goal path planning has been advantage for planning trajectories for robots with considering their localization uncertainty, like odometryless mobile robots or UAVs.

Sensor Placement: Boundary Placement algorithmMulti-Goal Path Planning using SOMMulti-Robot variant of the Multi-Goal Path PlanningWatchman Route Algorithm using SOM

Mission planning

In the mission planning, a long-term plan is created for an autonomous vehicle. Usually, the robot moves in an unknown or partially known environment, hence a map of the environment has to be created. If a robot is searching and unknown environment, exploration strategies are used to determine goals for the robots.


Motion planning for modular robots

More info here

People involved:

Miroslav Kulich




We are using several benchmark maps to compare algorithms. Our repository is here. For motion planning we use Parasol benchmarks.


(:includefile demos/demos_planning.html:) see more demos ...

Selected publications:

  • Vonásek, V. - Saska, M. - Košnar, K. - Přeučil, L.: Global Motion Planning for Modular Robots with Local Motion Primitives. In ICRA2013: Proceedings of 2013 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2013, . ISBN 978-1-4673-5642-8.
  • Vonásek, V. - Saska, M. - Přeučil, L.: Motion Planning for a Cable Driven Parallel Multiple Manipulator Emulating a Swarm of MAVs. In ROBOT MOTION AND CONTROL 2013. Pistacaway, NJ: IEEE Robotics and Automation Society, 2013, p. 13-18.
  • Jan Faigl, M. Kulich, and L. Přeučil. A sensor placement algorithm for a mobile robot inspection planning. Journal of Intelligent & Robotic Systems, 62(3-4):329-353 2011. doi: 10.1007/s10846-010-9449-0.
  • Jan Faigl, M. Kulich, V. Vonásek, and L. Přeučil. An Application of Self-Organizing Map in the non-Euclidean Traveling Salesman Problem. Neurocomputing 74:671-679, 2011. doi: 10.1016/j.neucom.2010.08.026.
  • Jan Faigl. Approximate Solution of the Multiple Watchman Routes Problem with Restricted Visibility Range. IEEE Transactions on Neural Networks, 21(10):1668-1679, 2010. doi: 10.1109/TNN.2010.2070518
  • Jan Faigl. On the Performance of Self-Organizing Maps for the non-Euclidean Traveling Salesman Problem in the Polygonal Domain. Information Sciences. (accepted)
  • Jan Faigl, L. Přeučil. Self-Organizing Map for the Multi-Goal Path Planning with Polygonal Goals. In T. Honkela et al. (Eds.): ICANN 2011, Part I, LNCS 6791, 85-92, 2011. (to appear)
  • Jan Faigl, T. Krajník, V. Vonásek, and L. Přeučil. Surveillance Planning with Localization Uncertainty for UAVs. In 3rd Israeli Conference on Robotics, Ariel, 2010, [pdf].
  • Saska, M. - Vonásek, V. - Přeučil, L.: Formation Coordination with Path Planning in Space of Multinomials. In Artificial Intelligence and Soft Computing 2011 [CD-ROM]. Calgary: IASTED, 2011, p. 348-355. ISBN 78-0-88986-885-4.
  • Saska, M. - Vonásek, V. - Přeučil, L.: Roads Sweeping by Unmanned Multi-vehicle Formations. In ICRA2011: Proceedings of 2011 IEEE International Conference on Robotics and Automation. Madison: Omnipress, 2011, p. 631-636. ISBN 978-1-61284-386-5.
  • M. Saska, V. Vonasek, T. Krajnik. Airport snow shoveling. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2010 [CD-ROM]. Taipei: IEEE Industrial Electronics Society, 2010, vol. 1, p. 2531-2532. ISBN 978-1-4244-6676-4.
  • M. Saska, V. Vonasek, L. Preucil. Control of ad-hoc formations for autonomous airport snow shoveling. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2010 [CD-ROM]. Taipei: IEEE Industrial Electronics Society, 2010, vol. 2, p. 4995-5000. ISBN 978-1-4244-6676-4.
  • M. Saska, V. Vonasek, L. Preucil. Navigation and Formation Control Employing Complementary Virtual Leaders for Complex Maneuvers. In 7th international Conference on Informatics in Control, Automation and Robotics [CD-ROM]. Angers: University of Angers, 2010, vol. 2, p. 141-146. ISBN 978-989-8425-01-0.
  • M. Hess, M. Saska, K. Schilling. Application of Coordinated Multi Vehicle Formations for Snow Shoveling on Airports. Intelligent Service Robotics, Volume 2, Number 4, Pages 205-217, October, 2009.
  • M. Saska, J. S. Mejia, D. M. Stipanovic, and K. Schilling. Control and navigation of formations of car-like robots on a receding horizon, in Proc of IEEE Control Applications, (CCA) & Intelligent Control, (ISIC), part of the IEEE Multi-Conference on Systems & Control (MSC) 2009.
  • M. Saska, M. Hess and K. Schilling. Route Scheduling Approach for Airport Snow Shoveling using Formations of Autonomous Ploughs. 10th International Conference on Control, Automation, Robotics and Vision (ICARCV 2008),Hanoi, Vietnam, 2008.
  • Vonásek, V. - Faigl, J. - Krajník, T. - Přeučil, L.: A Sampling Schema for Rapidly Exploring Random Trees Using a Guiding Path. In Proceedings of the 5th European Conference on Mobile Robots [CD-ROM]. Örebro: AASS Research Centre, 2011, p. 201-206
  • Vonásek, V. - Faigl, J. - Krajník, T. - Přeučil, L.: RRT-Path: a guided Rapidly exploring Random Tree. In Robot Motion and Control 2009. Heidelberg: Springer, 2009, p. 307-316. ISBN 978-1-84882-984-8

Projects and funding:

COLOS - grant MŠMT no. LH11053
Symbrion-Enlarged - European Union grant no. 216342
PostDoc GAČR - Martin Saska - grant MŠMT no. P103/12/P756