Page 89 - Innovations in Intelligent Machines

UAV Path Planning Using Evolutionary Algorithms 79
real-time in-flight applications. Path planning is the generation of a space path
between an initial location and the desired destination that has an optimal or
near-optimal performance under specific constraints [4]. A detailed descrip-
tion of motion and path planning theory and classic methodologies can be
found in [2] and in [3].

1.2 Cooperative Robotics
The term collective behavior denotes any behavior of agents in a system of
more than a single agent. Cooperative behavior is a subclass of collective behav-
ior which is characterized by cooperation [5]. Research in cooperative Robot-
ics has gained increased interest since the late 1980’s, as systems of multiple
robots engaged in cooperative behavior show specific benefits compared to a
single robot [5]:
• Tasks may be inherently too complex, or even impossible, for a single
robot to accomplish, or the performance is enhanced if using multiple
agents, since a single robot, despite its capabilities and characteristics, is
spatially limited.
• Building or using a system of simpler robots may be easier, cheaper,
more flexible and more fault-tolerant than using a single more compli-
cated robot.

In [5] cooperative behavior is defined as follows: Given some tasks specified
by a designer, a multiple robot system displays cooperative behavior if, due
to some underlying mechanism, i.e. the “mechanism of cooperation”, there is
an increase in the total utility of the system.
Geometric problems arise when dealing with cooperative moving robots,
as they are made to move and interact with each other inside the physical 2D
or 3D space. Such geometric problems include multiple-robot path planning,
moving to and maintaining formation, and pattern generation [5].
According to Fujimura [6], path planning can be either centralized or distri-
buted. In the first case a universal path planner makes all decisions. In the sec-
ond case each agent plans and adjusts its path. Furthermore, Arai and Ota [7]
allow for hybrid systems that are combinations of on-line, off-line, centralized,
or decentralized path planners. According to Latombe [2], centralized planning
takes into account all robots, while decoupled planning corresponds to indep-
endent computation of each robot’s path. Methods originally used for single
robots can be also applied to centralized planning. For decoupled planning
two approaches were proposed: a) prioritized planning, where one robot at a
time is considered, according to a global priority, and b) path coordination,
where the configuration space-time resource is appropriately scheduled to plan
the paths.
Cooperation of UAVs has gained recently an increased interest due to the
potential use of such systems for fire fighting applications, military missions,