GraphPlanning

Global planning for robotics based on graph search algorithms

TODO

• Accepting a new goal in rviz
  • Create new subscriber with check for current goal processing
  • Constraint check for the goal with dimensions of map
  • Round up the goal to cell of the map
  • Visualise the goal in rviz
  • Update the Map object with the new goal (wipe off any old goals as well)
• Breadth First Search Planner
  • Write Motion Model
  • Planning thread wait to receive goal
  • Iterate queue until goal cell is found
  • Build final path
  • Visualise frontier, explored nodes and final path
  • Add progress indicator during planning and performance metrics
  • Clear Map function
  • Add obstacles
  • Is diagonal exploration possible?
• Depth First Search Planner
  • Create stack data structure
  • Adapt breadth first search to depth first search
• 2D Cost Map
  • CostMap class as derived class of OGMap class
  • Initialise all costs to default values
  • Inflate OG Map obstacles in the cost map
  • Visualise Cost Map using marker array
  • what should be default cost value of cost map cells
• Dijkstra's Planner
  • Adapt search queue to priority queue
  • track movement costs
  • Visualise the frontier,explored nodes and final path
  • Introduce movement cost variable (No such variable needed ??? -> taken care of by COST_NEUTRAL)
  • Trade off between path length and proximity to obstacles (COST_NEUTRAL vs cost_scaling_factor)
• Greedy Best First Search Planner
  • Priority Queue returns cells closest to the goal
• A Star Planner
  • Introduce the manhattan distance (from goal) heuristic
  • Weight of the heuristic variable (Optimality condition : heuristic <true distance)
  • heuristic_weight variable -> trade off between Dijkstras and Greedy Best first search
  • Implement A Star with a compile time macro switch in Dijkstras

Depth First Search vs Breadth First Search

A* Planner vs Dijkstras Planner