Home

Bio

Publications

Research

Courses

Media

Contact

Realtime Alternate Routes Planning: The RRT*-AR Algorithm



Overview


In this project, we design a sampling based plannign algorithm that computes asymptotically optimal alternate routes. The algorithm, RRT*-AR, computes a set of good solutions by allowing for more possibilites as well as applies acceleration in computation by using cost approximations.

Abstract


Motion planning in the most general sense is an optimization problem with a single elusive best solution. However attempting to find a single answer isn't often the most desired approach. On the one hand, the reason is theoretical - planners often get trapped in local minimas because the cost function has many valleys or dynamics are too com- plex to fully exploit. On the other hand, there are many practical deterrents - unmapped obstacles might require the system to switch quickly to another plan, unmodelled dynamics can make a computed plan infeasible, or the system may have a human-in-loop who has a vote in the decision process. In situations where the current plan is no longer desirable, a new plan has to be planned. The re-planning time induces a reaction latency which might result in mission failure.
We advocate the use of alternate routes (AR), a set of spatially different, locally optimal paths, as a powerful tool to address several of the afore-mentioned issues. By enforcing the routes to be spatially separated, appearance of unexpected obstacles has less chance of rendering all trajectories to be infeasible. In such cases, alternate routes act as a set of backup options which can be switched to instantly. This reduces reaction latency allowing the system to operate with a lower risk.
This paper presents an algorithm, RRT*-AR, to generate alternate routes in real time by making tradeoffs in exploitation for exploration, precision for speed and leveraging assumptions about the vehicle and environment constraints. In the case of emergency landing of a helicopter, RRT*-AR outperformed RRT* by providing the human 280% more flight paths 67% faster on average. By planning multiple routes to potential landing zones, the planner was able to seamlessly switch to a new landing site without having to replan.

Publications


  • S. Choudhury, S. Scherer, S. Singh, "Realtime Alternate Routes Planning: The RRT*-AR Algorithm", tech report CMU-RI-TR-12-27, Robotics Institute, Carnegie Mellon University, 2012 (pdf).

  • Details


    A demonstration of RRT*-AR applied to emergency landing of a helicopter



    Some example scenarios for RRT*-AR are shown below.


    Example 1. The planner plans from the the centre of the world, to a region on goal points. The terminal cost of the goal points are shown by the colour (red having a high cost). The paths are curvature constrained.

    Example 2. The planner plans a curvature constrained set of alternate routes from the start (lower left) to goal (upper right).

    Links


    Here is Karaman's webpage for his work on RRT*.

    Here is the webpage on application of RRT* on emergency landing of a helicopter .