Skip to content

notes_rp_09_dmap_planner.md

Latest commit

 

History

History
97 lines (59 loc) · 4.68 KB

notes_rp_09_dmap_planner.md

File metadata and controls

97 lines (59 loc) · 4.68 KB

Distance Map (DMap) Planning for Robot Programming

Executive Summary

This document analyzes the use of Distance Maps (DMap) as a fundamental tool for path planning in mobile robotics. The DMap is an optimized data structure for storing the distance between each cell and the nearest obstacle, enabling the integration of safety margins (clearance) and efficient evaluation of navigation costs.

Through the use of search algorithms based on 8-direction connectivity, it is possible to generate paths in linear time and determine the next move with constant complexity O(1). The practical implementation is based on processing occupancy grids and dynamically updating trajectories in response to robot movements and new goal definitions.

Technical Analysis of the Distance Map

Function and Structure of the DMap

The Distance Map is a key tool for managing the operational space in robotic navigation.

  • Distance Storage: Each cell contains the minimum distance from the nearest obstacle.
  • Clearance: Ability to expand distances to include a safety margin, ensuring that the robot maintains a minimum distance from obstacles.

Cost Modeling

The cost associated with a cell depends on the distance d from the nearest obstacle:

  • Maximum Cost: Applied if d < r (robot radius).
  • Linear Decay: For d ≥ r, the cost decreases linearly within an influence range.
  • Minimum Cost: Beyond the influence range, the cost stabilizes at the minimum value.

Comparison of Planning Algorithms: Dijkstra vs A*

In the context of grid-based Path Planning for ROS, the choice of search algorithm drastically affects the computational efficiency of the system.

  • Dijkstra: Explores the space blindly and uniformly (like an "oil spill"). Although it guarantees finding the minimum-cost path, it expands an extremely high number of nodes. This makes it too slow for continuous runtime recalculation. In our approach, Dijkstra is run only once on the static map to generate a global cost map (policy).
  • A* (A-Star): Drastically optimizes the search by introducing a heuristic function. A* expands far fewer nodes than Dijkstra because the heuristic "guides" the exploration directly toward the destination node, ignoring clearly disadvantageous paths.

Integration with the DMap: It is crucial to distinguish the roles of the data structures in A*:

  1. Traversal cost: Derived from the DMap. Cells close to obstacles have a higher cost, forcing the algorithm to prefer safe trajectories (clearance).
  2. Heuristic: Represented by the policy pre-computed initially with Dijkstra on the static map.

When the robot detects dynamic obstacles in its local map, A* uses the pre-computed heuristic and the updated DMap costs to recalculate a new safe trajectory in extremely short times.

Movement Mechanisms

  • Connectivity: 8-direction connectivity to explore adjacent cells.
  • Move Cost: Proportional to:
    1. Movement length (diagonal moves are more costly).
    2. Cell-specific cost derived from the DMap.

Computational Performance

  • Path Computation: Generation of a complete policy in linear time.
  • Local Decision: Next move determinable in constant time O(1).

Planning and Movement Algorithms

Path generation uses the cost grid derived from the Distance Map (DMap) to optimize robot movements.

Search Logic

  • Connectivity: 8-direction graph (8-connectivity) for path computation.
  • Movement Cost: Determined by:
    • Displacement length: Diagonal moves have higher cost than orthogonal ones.
    • Cell cost: Value derived from the DMap, function of the distance from the obstacle.

Computational Performance

  • Path Planning: Computable in linear time with respect to the number of cells.
  • Next Move Determination: Once the policy is established, choosing the next cell happens in constant time O(1).

System Implementation

Data Flow and Subscriptions

The system constantly monitors state X (estimated robot position) and interacts with:

  • Topic /map: Provides the occupancy grid for updating distances and gradients.
  • Transformations (tf): Acquisition of the robot's current pose.
  • Message /goal_pose: Final destination of the robot.

Operational Logic

  • Pose Update: New path calculated at each position update.
  • Goal Reception: Navigation policy recalculated upon receiving a new goal.

Software Architecture

  • Core Logic: dmap.cpp, dmap_planner.cpp and headers dmap.h, dmap_planner.h.
  • Grid Management: grid.h, grid_mapping.h.
  • Utilities and Tests: display_utils.h and script dmap_planner_test.cpp.
  • Build Configuration: Managed via CMakeLists.txt.