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

Hi.

I'm Kito.

I go places and build stuff engineer.

You can hide the bio, or see pictures of the things I've built and the places I've been.