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
     
  1. 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"
    }
    
  2. 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"
    }
    
  3. 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"
    }