Realtime Alternate Routes Planning:The RRT*-AR Algorithm

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