Hierarchical Annotated Skeleton
Related Projects:  Robot Task and Motion Planning    Guided Planning    Workspace Guided Planning    Dynamic Region Planning    Multi-robot Skeleton Guidance  

The hierarchical planning strategy with annotated skeleton guidance adapts planning effort based on the solution's acceptance criteria. It improves its reliance on the skeleton as planning evolves, and takes into consideration additional information to bias its path finding efficiency.



Planners are evaluated in terms of efficiency to find suboptimal paths and c-space coverage, and previous work on Dynamic Regions planning strategies showed that skeleton guidance is useful when it maps a significant subspace of the c-space. The skeleton can be annotated with additional information to adapt to the solution’s acceptance criteria. For example, the planner can infer collision detection based on workspace clearance.

Algorithm Overview

Initialization
The hierarchical annotated skeleton planner prioritizes finding the paths that are marked by the skeleton first, and fixing the path only when needed. Local connected components are initialized in sampling regions around the skeleton vertices. In addition, connected components in adjacent regions across the skeleton edge are connected lazily, without validation, by assuming c-space connectivity between them.

Hierarchical Path Finding
In the next step, a path is queried, and evaluated. If no valid path is found, all the partially valid ones are returned to the planner. The planner attempts fixing invalid paths, by iteratively advancing the regions from each end of the skeleton edge corresponding to the invalid edge.

Evaluation

We compared our strategy against five PRM variants including the skeleton-guided Dynamic Regions PRM. The algorithms were tested on a store environment with many narrow obstacles and traffic variation. The results showed that:
  • HASPRM's overall planning time is improved due to the initial roadmap construction with lazy conection
  • HASPRM's graph is sparse due to the long edges between local connected components
  • In large environments, the advantages of HASPRM to its PRM counterparts are more noticeable
This video presents more details on the implementation and experimental results presented at the 2022 IROS conference.

Related Publications

Hierarchical Planning With Annotated Skeleton Guidance, Diane Uwacu, Ananya Yammanuru, Marco Morales, Nancy M. Amato, IEEE Robotics and Automation Letters (RA-L), Vol: 7, Issue: 4, pp. 11055-11061, Oct 2022. DOI: 10.1109/LRA.2022.3196885
Keywords: Lazy Evaluation, Motion Planning, Workspace Topology
Links : [Published] [Manuscript] [Video]

BibTex

@ARTICLE{9851528,
author={Uwacu, Diane and Yammanuru, Ananya and Morales, Marco and Amato, Nancy M.},
journal={IEEE Robotics and Automation Letters},
title={Hierarchical Planning With Annotated Skeleton Guidance},
year={2022},
volume={7},
number={4},
pages={11055-11061},
doi={10.1109/LRA.2022.3196885}}


Abstract

We present a hierarchical skeleton-guided motion planning algorithm to guide mobile robots. A good skeleton maps the connectivity of the subspace of c-space containing significant degrees of freedom and is able to guide the planner to find the desired solutions fast. However, sometimes the skeleton does not closely represent the free c-space, which often misleads current skeleton-guided planners. The hierarchical skeleton-guided planning strategy gradually relaxes its reliance on the workspace skeleton as C-space is sampled, thereby incrementally returning a sub-optimal path, a feature that is not guaranteed in the standard skeleton-guided algorithm. Experimental comparisons to the standard skeleton guided planners and other lazy planning strategies show significant improvement in roadmap construction run time while maintaining path quality for multi-query problems in cluttered environments.