Multi-UAV dynamic routing with partial observations using restless bandit allocation indices
Authors:
- 1 June 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4220-4225
Abstract
Motivated by the type of missions currently performed by unmanned aerial vehicles, we investigate a discrete dynamic vehicle routing problem with a potentially large number of targets and vehicles. Each target is modeled as an independent two-state Markov chain, whose state is not observed if the target is not visited by some vehicle. The goal for the vehicles is to collect rewards obtained when they visit the targets in a particular state. This problem can be seen as a type of restless bandits problem with partial information. We compute an upper bound on the achievable performance and obtain in closed form an index policy proposed by Whittle. Simulation results provide evidence for the outstanding performance of this index heuristic and for the quality of the upper bound.Keywords
This publication has 15 references indexed in Scilit:
- Relaxations of Weakly Coupled Stochastic Dynamic ProgramsOperations Research, 2008
- Stochastic Control Bounds on Sensor Network Performance2006
- Some indexable families of restless bandit problemsAdvances in Applied Probability, 2006
- Cooperative path planning for multiple UAVs in dynamic and uncertain environments2003
- Approximate dynamic programming for sensor management2002
- Restless bandits, partial conservation laws and indexability2001
- The Complexity of Optimal Queuing Network ControlMathematics of Operations Research, 1999
- On an index policy for restless banditsJournal of Applied Probability, 1990
- The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted CostsOperations Research, 1978
- On the determination of optimal costly measurement strategies for linear stochastic systemsAutomatica, 1972