Page 88 - Innovations in Intelligent Machines

78 I.K. Nikolos et al.
problems. Besides the great variety of planning problems and models found
in Robotics, some basic terms are common throughout the entire subject.
The state space includes all possible situations that might arise during
the planning procedure. In the case of an UAV each state could represent its
position in physical space, along with its velocity. The state space could be
either discrete or continuous; motion planning is planning in continuous state
spaces. Although its definition is an important component of the planning
problem formulation, in most cases is implicitly represented, due to its large
size [3].
Planning problems also involve the time dimension. Time may be explicitly
or implicitly modeled and may be either discrete or continuous, depending
on the planning problem under consideration. However, for most planning
problems, time is implicitly modeled by simply specifying a path through a
continuous space [3].
Each state in the state space changes through a sequence of specific actions,
included in the plan. The connection between actions and state changes should
be specified through the use of proper functions or differential equations.
Usually, these actions are selected in a way to “move” the object from an
initial state to a target or goal state.
A planning algorithm may produce various different plans, which should
be compared and valued using specific criteria. These criteria are generally
connected to the following major concerns, which arise during a plan gen-
eration procedure: feasibility and optimality. The first concern asks for the
production of a plan to safely “move” the object to its target state, without
taking into account the quality of the produced plan. The second concern asks
for the production of optimal, yet feasible, paths, with optimality defined in
various ways according to the problem under consideration [3]. Even in simple
problems searching for optimality is not a trivial task and in most cases results
in excessive computation time, not always available in real-world applications.
Therefore, in most cases we search for suboptimal or just feasible solutions.
Motion planning usually refers to motions of a robot (or a collection of
robots) in the two-dimensional or three-dimensional physical space that con-
tains stationary or moving obstacles. A motion plan determines the appropri-
ate motions to move the robot from the initial to the target state, without
colliding into obstacles. As the state space in motion planning is continuous, it
is uncountably infinite. Therefore, the representation of the state space should
be implicit. Furthermore, a transformation is often used between the real world
where the robots are moving and the space in which the planning takes place.
This state space is called the configuration space (C-space) and motion plan-
ning can be defined as a search for a continuous path in this high-dimensional
configuration space that ensures collision avoidance with implicitly defined
obstacles. However, the use of configuration space is not always adopted and
the problem is formulated in the physical space; especially in cases with con-
stantly varying environment (as in most of UAV applications) the use of confi-
guration space results in excessive computation time, which is not available in