This paper presents at a class of new methods which explore and
describe an unstructured environment according to the free space as
seen by a vehicle within the environment. The proposed methods use
such sensor-based information to present a safe, goal-seeking path
through the environment. The methods are suitable to both online,
reactive pathfinding and obstacle avoidance as well as online or offline
global navigation and goal-seeking behaviours. Experimental results on
ground vehicles and in simulation are presented to demonstrate the
path-planning capabilities of the proposed methods.
advances being in sensor UAVs and The continual indoor
microThemadevehiclesand technologies have recently givenMAVs gives
especiallya small, autonomous aerial (MAVs) the potential to be an
effective solution for wideranging selection of tasks . small size
three-dimensional mobility of them significant 1
advantages over ground vehicles and other traditional robots which
operate in constrained areas. However, these same capabilities present
significant challenges in the development of the robust and effective
online path-planners necessary for fully autonomous flight. While there
is a rich body of research related to path-planning in sparse
environments for both individual and swarms 3 4 5 of autonomous
Unmanned Aerial Vehicles (UAVs), the introduction of similar
capabilities in MAVs and UAVs operating in crowded or highly
constrained environments has been more limited 6 .7 The reasons for
this are diverse. The small size and payload capacity of most MAVs
makes it impossible to carry a wide variety of sensors popular on
larger vehicles. In addition, it is often impossible to reap the
benefits of sensor fusion on a vehicle that is limited to a single
sensor. Path-planning in constrained environments presents a special
challenge due to the limits on viable configurations of the vehicle and
consequences of poor path-planning.
One sensor that has shown considerable promise in use on MAVs is the
camera. The small size and weight of modern CMOS camera modules has
allowed single and even stereo cameras to be outfitted to MAVs 8 .7
Cameras provide a large amount of information about the environment,
which is of great benefit when trying to perform online
path-planning. Recent improvements in processing of camera images have
made planning in 3D from this information feasible .9 There have been
two major approaches to the problem of path-planning in constrained
three-dimensional environments. The first approach is commonly known as
quasi- two-dimensional or 2.5 dimensional pathplanning, and is similar
to constrained two dimensional movement in a plane. However 2.5D
path-planning typically takes additional measures to incorporate
information from the third dimension so as to provide additional
flexibility when it becomes necessary to move out-of-plane. The second
major approach is the full three dimensional path planner. These
methods provide the maximum amount of robustness in complex
scenarios, but come at the cost of additional processing
overhead. Increasing the dimensionality of the problem by one can
easily cause an order of magnitude increase in the amount of data that
has to be processed. This has severely limited the applicability of
full three dimensional path planners. The Aerospace Robotics Lab at
Iowa State University has recently begun work on cooperative indoor
and terrain masking operations between ground and small aerial
vehicles as partially introduced in.10 As part of this work a need for
path planning methods that could provide goal seeking behaviour in
environments that are cluttered with obstacles and other constraining
factors were needed. These methods were required to be highly
responsive to the limitations inherent in the environment, as well as
being able to operate solely using the vehicle’s onboard active
sensors. Because the environments are often GPS-denied a global
position estimate could not be a requirement for safe navigation. In
this paper three such path-planners are presented, and as part of the
lab’s ongoing research these methods will be further refined and
tested. In this paper, we shall be presenting lightweight methods for
exploring an environment and performing goal seeking behaviours
constrained within a plane. The Heuristic Circular Sector Expansion
(HCSE) method is presented in section IV.A; it provides a capable
method of generating a constantly updated path tree which can be used
to find shortest-path, safest-path or exploratory routes through an
environment. This method has been experimentally validated on the
Aerospace Robotics Lab’s ground rovers in dynamic indoor and outdoor
environments. The edge cutting tree (ECT) algorithm is presented in
section IV.B as another 2D collision-free sensor-based path-planning
algorithm. ECT generates multiple paths from a binary tree
geometrically constructed from the sensor information. It is designed
to be efficient especially for indoor environments with walls and hall
ways. The generated paths can be optimized by adjusting the waypoints
laterally on the edges that cut through the paths and then can easily
be identified if the paths lead to deadends or not. Currently, the
method is waiting to be experimental validated. We shall then extend
HCSE to improve its applicability to aerial vehicles through the use
of a 2.5 dimensional Cylindrical Sector Expansion (CySE). This method,
presented in section IV.C, provides the ability to incorporate
altitude changes into the path planner for better agility in complex
environments. Finally, we will show a fully robust method of finding
paths in the most complex environments through the expansion of
spheres in all three dimensions. Spherical Sector Expansion (SSE) is
presented in IV.D, and has been demonstrated in MATLAB simulations to
provide complete information about the available paths in an
environment.
The robotics community has been interested in path-planning and
navigation in indoor environments for several decades, although the
bulk of research in that area has been limited to ground vehicles. One
method used in the robotics community that has found success is the
usage of the edges of the Voronoi Diagram (GVD) of an environment to
plan a path. This guarantees a path that is not only free of
obstacles, but is in fact the safest path through the
environment. Ronnback showed that it is possible to quickly find the
edges of the Generalized Voronoi Diagram of laserscan data by
expanding a series of circles starting from the vehicle location .11
Ronnback then further expanded this method to provide dynamic path
planning and topographical mapping for a self-guided wheelchair .12
There are diverse approaches for the 2D path-planning problem. Ours is
close to the computational geometry or topology-based approaches such
as Ref.13. The method known as rapidly-exploring random tree (RRT14 )
is widely used for the purpose and it has common characteristics as
ours in using the tree structure. An advanced method15 from RRT was
introduced by Frazzoli to deal with moving obstacles in the
environment efficiently. Such approaches usually have well defined goal
to reach and assume that all the information of the environment is
given in advance so that the algorithms can compute best paths a
priori. Our approach is a little different in that only the information
that gathered from each scan of the range finding sensor is used and
the planning aims at on-line computation. As a trade-off, our
approaches lack the proof of probabilistic completeness of the
algorithms but we rather chose to experimentally validate the
methods. The potential for planning safe paths in three dimensional
environments was recognized by Vandapel, Kuffner and Amidi ,16 where a
grid of “free space bubbles” was used to find a safe path through a
forest canopy. This offline method was performed using laser scan data taken
from a prior flight through the forest with a helicopter. By looking at
the intersections of the spheres it was possible to determine the path
which stayed the greatest distance from obstacles at all times.
Figure 1 summarizes the problem of vehicle movement in a plane. In the
strict 2D case the motion of the vehicle is limited to motion within a
plane and all information about the environment that does not lie in
the plane is discarded. In this world model the vehicle’s state can be
described as x x= y ˆ (1) ψ where x and y are the vehicle’s
position on the plane and ψ describes its heading relative to some
reference heading. The environment itself is then described as a
collection of obstacles Λ, such that Λ ∈ {λ|λ → R2 } (2)
Alternatively it can also be convenient to represent the world
obstacles in polar coordinates centered around the vehicle, where ¯ Λ
= {[d α]T |d ∈ R, −π ≤ α ≤ π} (3)
In this paper we will be representing the vehicle as a sphere with
constant radius rvehicle . In the 2D case a collision is defined as an
obstacle λi being within the vehicle’s safety circle rsaf ety
Quasi-2D motion is conceptually similar to movement in a plane. In the
2.5D world model the altitude information in the world is divided into
a set of discrete intevals and the vehicle motion is limited to
movement
within the current plane and transitional movements between two
planes. In many environments the motion of an aerial vehicle can be
reduced to quasi-2D motion at a constant altitude. This approximation
reduces the order of the resulting pathfinding problem. This
approximation can be further improved by adding the height information
back into the problem through a discretization of the vertical
axis. This leads to the 2.5D world approximation. In this
approximation the vehicle’s state is described by x y x=
ˆ (4) z ψ where z ∈ {f (x)|x ∈ I} (5)
Similarly the obstacles in the environment are binned into discrete
layers where all obstacles with an altitude in the range between two
discrete values are grouped together. In this environment model a
collision is defined as the set of states where an obstacle λi has a 2D
distance within the safety radius of the vehicle, and an altitude
difference from the vehicle less than half the altitude discretization
distance.
In some situations the limitations of the 2.5D approximations can
limit the possible motions of the vehicle. This is especially true of
helicopters and other vehicles with operating advantages in
constrained environments, which are capable of performing maneuvers
which would require full three-dimensional path planning. Figure 3
shows an example scenario where full 3D pathfinding can provide
benefits. In the full 3D pathfinding problem the vehicle’s state is