Tasks :

• Paper readings: Hierarchical Planning With Annotated Skeleton Guidance
• Running simulation in the Duckiebot
• Implement and run a planning strategy
  • Following Planning I and II from edX course

Notes from “Hierarchical Planning With Annotated Skeleton Guidance”:

Goal:

The main goal of this algorithm is to efficiently guide robots through complex environments by using a skeleton that maps the connectivity of the configuration space (C-space). This skeleton helps in quickly finding sub-optimal paths, which is particularly useful in cluttered environments.

• Configuration Space (C-space): The configuration space is the mathematical space representing all possible configurations (positions and orientations) of a robot.

• Degrees of freedom (DoF)
• Dimensions of c-space : free space , obstacle space

• Sampling based probabilistic roadmap method ( Basic PRM)
• efficiency in quickly finding a sub-optimal solution, and 
• coverage that leads to reusability for multi-query problems.

• The validity of c space comes from collision detector method 
• Sampling based algorithm : 

 Sampling based algorithm approximates c space by generating random road map configuration or connecting them to build roadmap graph (Basic PRM) or Rapidly exploring random trees( RRT) 

• Guided motion planning : A User Guided Planning Strategy that  allows the user to define and manipulate workspace sampling regions that the planner follows in real time to explore the planning space inside the user-defined region.
• A workspace skeleton is a uni-dimensional graph in the workspace such that the free space can be collapsed into the skeleton continuously.

Hierarchical Annotated Skeleton Planning (HASP)

The HASP strategy introduces several innovative concepts:

• Annotated Skeletons: Skeletons are enhanced with additional information, such as obstacle clearance and expected traffic, making them better guides for C-space sampling.
• Phased Pathfinding: The algorithm initially searches for easy-to-find paths indicated by the skeleton and progressively searches for more difficult paths according to problem specifications.
• Delayed Validation: Similar to lazy planning strategies, HASP delays validation to reduce the number of collision detection calls required to build a roadmap.

The HASP method is detailed in three phases:

1. The roadmap is initialized by sampling configurations at each skeleton vertex that satisfies certain criteria (e.g., obstacle clearance). These configurations form local connected components.
2. Paths from the start to goal configurations are built and stored in a path set. Each path is checked for validity, and invalid edges are recorded.
3. The planner iterates through the partially invalid paths, attempting to fix invalid edges by expanding sampling regions and reconnecting them with shorter, lazily drawn edges.

Experimental Validation:

1. Create Environment: A 3 DOF nonholonomic robot navigates a space with narrow and wide path options. HASP returned high-clearance paths efficiently.
2. Rhombus Environment: Three rhombuses with varying distances provide different clearance pathways for a point robot. HASP showed lower path cost and query time compared to other planners.
3. Store Environment: A grocery store setup with a 3 DOF nonholonomic robot and fifty obstacles tested the scalability of the algorithm. HASP demonstrated the lowest planning time and efficiently handled the high number of obstacles.

Experimental Setup and Results:

• The algorithm builds a skeleton-guided roadmap, initializing sampling regions at each skeleton vertex. These regions expand outward along the skeleton edges to explore the C-space efficiently.
• The algorithm delays validation of roadmap edges to reduce the number of collision detection calls, similar to lazy planning strategies.
•  Experiments show that the Hierarchical Annotated Skeleton Planning (HASP) method significantly reduces planning time and collision detection calls while maintaining high path quality. It performs well in various environments, including cluttered and narrow passages, and scales effectively with the complexity of the environment.