Multi-UAV Dynamic Routing with Partial Observations using Restless Bandit Allocation Indices

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 2007
Accession Number
AD1004475

Entities

People

  • Jerome L. Ny
  • Munther Dahleh
  • Éric Féron

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes
  • Sensors
  • Space
  • Weapons Technologies

DTIC Thesaurus Topics

  • Aircrafts
  • Algorithms
  • Communication Channels
  • Computations
  • Computer Programming
  • Dynamic Programming
  • Environmental Monitoring
  • Equations
  • Markov Chains
  • Military Operations
  • Monte Carlo Method
  • Optimization
  • Probability
  • Probability Distributions
  • Simulations
  • Unmanned Aerial Vehicles
  • Vehicles

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Aerial Unmanned Vehicle Swarm Micro Periodontal Dentistry.
  • Operations Research

Technology Areas

  • Autonomy