Page 155 - Innovations in Intelligent Machines

Algorithms for Routing Problems Involving
UAVs

1
Sivakumar Rathinam and Raja Sengupta 2
1
University of California, Berkeley rsiva@berkeley.edu
2
University of California, Berkeley raja@path.berkeley.edu
Abstract. Routing problems naturally arise in several civil and military applica-
tions involving Unmanned Aerial Vehicles (UAVs) with fuel and motion constraints.
A typical routing problem requires a team of UAVs to visit a collection of targets
with an objective of minimizing the total distance travelled. In this chapter, we
consider a class of routing problems and review the classical results and the recent
developments available to address the same.

1 Introduction

This chapter is dedicated to reviewing classical approaches and disseminating
recent approaches on the resource allocation problems that arise in the use
of Unmanned Aerial Vehicles (UAVs). Small autonomous UAVs are seen as
ideal platforms for many applications such as monitoring a set of targets,
mapping a given area, aerial surveillance, fire monitoring etc. A collection of
small autonomous UAVs with the necessary sensors can potentially replace a
manned vehicle in dangerous environments and warfare. A common mission
that can be carried out by a group of UAVs is a surveillance operation where
a set of destinations needs to be monitored. If the number of destinations to
be visited are higher than the number of UAVs available, then the following
resource allocation questions naturally arises:
1. How to partition the set of destinations into subsets such that each UAV
gets a subset of destinations to monitor?
2. Given a subset for each UAV, how to determine the order in which the
destinations should be monitored?
3. Can we find a partition and an order for each UAV such that the total
distance travelled by the UAVs is minimum or the total risk encountered
is minimum?

If there is only one vehicle, the problem of finding an optimal sequence
such that each destination is visited once and the total distance travelled

S. Rathinam and R. Sengupta: Algorithms for Routing Problems Involving UAVs, Studies in
Computational Intelligence (SCI) 70, 147–172 (2007)
www.springerlink.com c Springer-Verlag Berlin Heidelberg 2007