Page 93 - Innovations in Intelligent Machines

UAV Path Planning Using Evolutionary Algorithms 83
determination for each team of UAVs assigned to a target of an estimated time
over target that ensures simultaneous intercept and is feasible for all UAVs
in the team. c) The determination of a path (specified via waypoints) that
can be completed within the specified time over target, taking into account
minimum and maximum velocity constraints. d) The transformation of the
initial path into a feasible UAV trajectory. e) The development of controllers
for each UAV to track their computed trajectory.
A simpler scenario is presented in [15], where the problem under consider-
ation is to generate routes for cooperating UAVs in real time, which take into
account the exposure of UAVs to the threats and enable the vehicles to arrive
at their goal location simultaneously. Some of the threats are known a priori,
some of them “pop up” or become known only when a UAV approaches to it.
For each UAV are imposed minimum and maximum velocity constraints. The
cooperation related constraints are: a) the simultaneous arrival of all UAVs
at goal locations, and b) the collision avoidance between UAVs.
In [20] the motion-planning problem for a limited resource of mobile sensor
agents (MSAs) is investigated, in an environment with a number of targets
larger than the available MSAs. The MSAs are assumed to move much faster
than the targets. In order to keep the targets in surveillance the members
of the MSA team have to fly back and forth to update the targets’ status.
This NP-hard problem is essentially a combination of the problems of sensor
resource management and robot motion planning. The problem is formulated
as an optimization problem whose objective is to minimize the average time
duration between two consecutive observations of each target.
In [12] the objective is to provide a coordinated plan for searching a geo-
graphic region, represented by a grid of cells, using a team of searchers. Each
cell is characterized by its elevation and a cost parameter that corresponds to
the danger of visiting it. Each vehicle carries a sensor, characterized by scan
radius, angle and direction. The mission objective is the target coverage, i.e.
the percentage of the region that must be scanned during the mission. Scans
can be performed only from safe cells (the cell and all 8 neighbors should
have been previously scanned). Additionally the path that connects scanning
points should traverse through already scanned cells (a soft constraint). For
safety reasons scanning paths are not allowed to be very close to each other.

Solution methodologies:

Path planning problems are actually multi-objective multi-constraint optimi-
zation problems, in most cases very complex and computationally demanding
[24]. The problem complexity increases when multiple UAVs should be used.
Various approaches have been reported for UAVs coordinated route planning,
such as Voronoi diagrams [16], mixed integer linear programming [25, 26] and
dynamic programming [27] formulations.
In [25, 26] mixed-integer linear programming (MILP) is used to solve
tightly-coupled task assignment problems with timing constraints. The