Carnegie Mellon University
Browse
file.pdf (1.22 MB)

Realtime Alternate Routes Planning: The RRT*-AR Algorithm

Download (1.22 MB)
journal contribution
posted on 2012-12-01, 00:00 authored by Sanjiban Choudhury, Sebastian SchererSebastian Scherer, Sanjiv Singh

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 complex 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.

History

Publisher Statement

All Rights Reserved

Date

2012-12-01

Usage metrics

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC