Multi-robot Systems - GACR

Sampling-based planning of actions and motions using approximate solutions

GACR funding

People: V. Vonasek, R. Penicka, D. Fiser

Task and motion planning are crucial problems in robotics. Given propositions and discrete abstract actions, a high-level task planner finds a sequence of the actions leading to a goal. Then, a low-level motion planner finds feasible trajectories for each set of actions in the abstract plan. The task planning leads to a search in a discrete space which is often searched using a heuristic. The task of motion planning is to find a collision-free trajectory for a robot (or object) from a given start position to a goal position.

The motion planning problem can be formulated using the concept of configuration space [36]. The dimension of the configuration space is determined by the number of degrees of freedom (DOF) of the robot and, in many cases, motion planning leads to a search in a high-dimensional configuration space.

Generally, it is not computationally tractable to explicitly represent obstacles in a configuration space (e.g., using a grid). Instead the configuration space can be searched using sampling-based methods like RRT or PRM. A key issue of sampling-based planners is the presence of narrow passages. Narrow passages are small regions in the configuration space that are difficult to cover with random samples. Despite many published modifications of sampling-based planners, the narrow passage problem is still challenging.

Project Goals

The proposed project aims to develop novel sampling-based motion planning methods for scenarios with narrow passages. To cope with the narrow passage problem, we aim to construct an approximate solution considering a relaxed version of the problem. In the case of motion planning of 3D objects, the relaxation can be achieved by modifying the geometry of the robot, e.g., by shrinking or by approximating the robot using basic geometric primitives. The level of relaxation is then given by various shrinking factors or, in the case of an approximated robot, by considering several levels of details of the approximation. The effect of such a relaxation is that the relative volume of the narrow passages in configuration space increases, which helps to cover them by the random samples. The approximate solution will be then used to guide the search in the configuration space. This guiding will be realized iteratively, starting with the most relaxed (easy) version of the problem in order to help finding a solution for a harder problem until the solution of the origininal problem is found.

Toys scenario. Each object can be moved only by

the corresponding window

Windows scenario with simple L-shaped,

I-shaped and S-shaped objects

Hedgehog in the cage benchmark

Planning with 'disabled' regions


1st solution	2nd solution	3rd solution

J Janoš, V Vonásek and R Pěnička. Multi-Goal Path Planning Using Multiple Random Trees. IEEE Robotics and Automation Letters 6(2):4201-4208, April 2021. URL arXiv, DOI BibTeX

@article{janos2021multigoal,
	author = "J. {Jano\v{s}} and V. {Von\'{a}sek} and R. {P\v{e}ni\v{c}ka}",
	journal = "IEEE Robotics and Automation Letters",
	title = "Multi-Goal Path Planning Using Multiple Random Trees",
	year = 2021,
	month = "April",
	volume = 6,
	number = 2,
	pages = "4201-4208",
	doi = "10.1109/LRA.2021.3068679",
	url = "https://ieeexplore.ieee.org/document/9385932",
	arxiv = "http://arxiv.org/abs/2106.03407"
}

D Fiser, R Horcík and A Komenda. Strengthening Potential Heuristics with Mutexes and Disambiguations. In Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. 2020, 124-133. BibTeX

@inproceedings{fiser2020strengthening,
	author = "Fiser, D. and Horcík, R. and Komenda, A.",
	title = "Strengthening Potential Heuristics with Mutexes and Disambiguations",
	booktitle = "Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling",
	publisher = "Menlo Park: AAAI Press",
	year = 2020,
	pages = "124-133",
	issn = "2334-0835",
	isbn = "978-1-57735-824-4"
}

V Vonásek, R Pěnička and B Kozlíková. Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning. Journal of Intelligent & Robotic Systems 100:1547-1543, 2020. DOI BibTeX

@article{vonasek2020searching,
	author = "Von{\'a}sek, V. and R. P\v{e}ni\v{c}ka and Kozl{\'i}kov{\'a}, B.",
	title = "Searching Multiple Approximate Solutions in Configuration Space to Guide Sampling-Based Motion Planning",
	journal = "Journal of Intelligent {\&} Robotic Systems",
	pages = "1547-1543",
	volume = 100,
	issue = 3,
	year = 2020,
	doi = "https://doi.org/10.1007/s10846-020-01247-4"
}

V Vonásek, R Pěnička and B Kozlı\'ková. Computing multiple guiding paths for sampling-based motion planning. In 2019 19th International Conference on Advanced Robotics (ICAR) (). December 2019, 374-381. PDF, DOI BibTeX

@inproceedings{vonasek2019computing,
	author = "V. {Vonásek} and R. {P\v{e}ni\v{c}ka} and B. {Kozl\i{\'}kov\'{a}}",
	booktitle = "2019 19th International Conference on Advanced Robotics (ICAR)",
	title = "Computing multiple guiding paths for sampling-based motion planning",
	year = 2019,
	volume = "",
	number = "",
	pages = "374-381",
	keywords = "iterative methods;mobile robots;path planning;probability;sampling-based planners;narrow passage problem;random samples;guided-based planners;six-dimensional configuration space;guided sampling;multiple approximate solutions;multiple narrow passages;multiple guiding paths;sampling-based motion planning;path planning;3D solid objects",
	doi = "10.1109/ICAR46387.2019.8981589",
	issn = "null",
	month = "Dec",
	pdf = "data/papers/vonasek-icar19-multiple.pdf"
}

V Vonásek and R Pěnička. Sampling-based motion planning of 3D solid objects guided by multiple approximate solutions. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (). November 2019, 1480-1487. PDF, DOI BibTeX

@inproceedings{vonasek2019iros,
	author = "V. {Vonásek} and R. {P\v{e}ni\v{c}ka}",
	booktitle = "2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)",
	title = "Sampling-based motion planning of 3D solid objects guided by multiple approximate solutions",
	year = 2019,
	volume = "",
	number = "",
	pages = "1480-1487",
	keywords = "",
	doi = "10.1109/IROS40897.2019.8968578",
	issn = "2153-0858",
	month = "Nov",
	pdf = "data/papers/vonasek-iros-2019.pdf"
}

M Petrlik, V Vonasek and M Saska. Coverage Optimization in the Cooperative Surveillance Task using Multiple Micro Aerial Vehicles. In 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC). October 2019. PDF BibTeX

@inproceedings{petrlik2019smc,
	author = "M. {Petrlik} and V. {Vonasek} and M. {Saska}",
	booktitle = "2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)",
	title = "Coverage Optimization in the Cooperative Surveillance Task using Multiple Micro Aerial Vehicles",
	year = 2019,
	month = "Oct",
	pdf = "data/papers/petrlik2019smc.pdf"
}

V Vonásek and R Pěnička. Space-filling forest for multi-goal path planning. In 2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). 2019, 1587-1590. PDF, DOI BibTeX

@inproceedings{vonasek_etfa19_SFF_multigoal,
	author = "V. {Vonásek} and R. {Pěnička}",
	booktitle = "2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)",
	title = "Space-filling forest for multi-goal path planning",
	year = 2019,
	pages = "1587-1590",
	keywords = "Vegetation;Path planning;Planning;Robots;Task analysis;Forestry;Two dimensional displays",
	doi = "10.1109/ETFA.2019.8869521",
	month = "Sep.",
	pdf = "data/papers/vonasek-etfa-2019-multigoal-sff.pdf"
}

V Vonásek and R Pěnička. Path planning of 3D solid objects using approximate solutions. In 2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA). 2019, 593-600. PDF, DOI BibTeX

@inproceedings{vonasek_etfa19_3Dplanning,
	author = "V. {Vonásek} and R. {Pěnička}",
	booktitle = "2019 24th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)",
	title = "Path planning of 3D solid objects using approximate solutions",
	year = 2019,
	pages = "593-600",
	keywords = "Robots;Geometry;Collision avoidance;Planning;Three-dimensional displays;Solids;Path planning",
	doi = "10.1109/ETFA.2019.8869344",
	month = "Sep.",
	pdf = "data/papers/vonasek-etfa-2019-rrt-iis-peeling.pdf"
}

V Vonásek and R Pěnička. Computation of Approximate Solutions for Guided Sampling-Based Motion Planning of 3D Objects. In 2019 12th International Workshop on Robot Motion and Control (RoMoCo). July 2019, 231-238. PDF, DOI BibTeX

@inproceedings{vonasek_romoco19_app_guided_sampling,
	author = "V. {Vonásek} and R. {Pěnička}",
	booktitle = "2019 12th International Workshop on Robot Motion and Control (RoMoCo)",
	title = "Computation of Approximate Solutions for Guided Sampling-Based Motion Planning of 3D Objects",
	year = 2019,
	pages = "231-238",
	keywords = "collision avoidance;graph theory;mobile robots;path planning;sampling methods;search problems;collision-free samples;narrow passage problem;approximate solution;guided sampling-based motion planning;3D solid objects;graph-search methods;6D configuration space;iterative guiding process;Planning;Surface treatment;Collision avoidance;Three-dimensional displays;Legged locomotion;Solids",
	doi = "10.1109/RoMoCo.2019.8787344",
	month = "July",
	pdf = "data/papers/vonasek-romoco-2019-rrt-iis.pdf"
}