Dynamics-AwarePathfinding

Michael McGuinness
May 3, 2012

Attach:mmcguinnPaper.pdf

Dynamics-Aware Pathfinding

Overview

This project is an implementation of mapping and pathfinding using the Robot Operating System (ROS) as a basis. The implementation heavily leverages ROS' transform support to make coordinate frame transformations and straightforward (and bug-free) as possible. The pathfinding itself is done by searching on dynamic robot movement rather than directly on an occupancy grid. The simulation used for testing includes a number of real-world hassles, notably drifting odometry and inaccurate GPS readings.

Photograph

Here you can see the result of a search. The red line represents the path generated while the cloud of green arrows represent possible robot states that were considered during the search.

Concepts Demonstrated

Please identify the robotics concepts involved in your project here. Be brief; a simple list and one-sentence explanation for each concept should be adequate; e.g.:

  • Simulation is used to provide an accurate representation of a real robot and its problems, including GPS and odometry drift.
  • A* Search' is used as the core searching algorithm for the pathfinder.
  • Transform frames are used to view the robot in terms of its odometry, GPS location, and map position.

Innovation

Traditionally, A* is used to search directly on an occupancy grid or graph for use in pathfinding. This project instead searches on robot state itself, making it more aware of robot dynamics. This generates paths more realistic for the robot, with a more spline-like appearance rather than a simple grid-traversal.

Technology Used Block Diagram

Additional Comments

This approach to pathfinding definitely has merit, it can produce very realistic paths and even include possibilities such as reversing the robot when advantageous. It is however, in the state currently presented here, very computationally expensive. More discretization is required in order to make this technique plausible in non-trivial situations.