Anytime exploration planning algorithm for UAVs

2^nd World Congress on Automation and Robotics

June 13-15, 2016 Philadelphia, USA

Sankalp Arora

Carnegie Mellon University, USA

Posters & Accepted Abstracts: Adv Robot Autom

Abstract :

Data gathering in the physical world is tedious and often risky. Robots are ideally suited for such applications. The objective of a data gathering robot is to travel between two points maximizing the information it gains while not exceeding energy or cost constraints. This problem can be formalized as that of finding budgeted routes in a graph such that the reward collected by the route is maximized, where the reward at nodes can be related. This problem is known as correlated orienteering. Unfortunately, state of the art solutions are too slow to even present an approximate solution while running online. We describe, RRO, a sampling based anytime orienteering algorithm that provides approximate solutions to the orienteering problem with computational costs that enable it to run online. This enables the UAV�s to reason about intelligently planning non-myopic paths to explore an environment at large scale. We prove the algorithm is asymptotically optimal, and converges in polynomial time, whilst analyzing the effects of various heuristics on run times. We demonstrate that the state of the art methods take 10-12 minutes to solve a 400 node problem, whereas the method presented here takes 7-8 seconds.

Biography :

Email: acesan23@gmail.com