State lattice-based planning has been used in navigation for ground, water, aerial and space robots. State lattices are typically constructed of simple motion primitives connecting one state to another. There are situations where these metric motions may not be available, such as in GPS-denied areas. In many of these cases, however, the robot may have some additional sensing capability that is not being fully utilized by the planner. For example, if the robot has a camera it may be able to use simple visual servoing techniques to navigate through a GPS-denied region. Likewise, a LIDAR may allow the robot to skirt along an environmental feature even if there is not enough information to generate an accurate pose estimate. In this paper we present an expansion of the state lattice framework that allows us to incorporate controller-based motion primitives and external perceptual triggers directly into the planning process. We provide a formal description of our method of constructing the search graph in these cases as well as presenting real-world and simulated testing data showing the practical application of this approach.

Operating micro aerial vehicles (MAVs) outside of the bounds of a rigidly controlled lab environment, specifically one that is unstructured and contains unknown obstacles, poses a number of challenges. One of these challenges is that of quickly determining an optimal (or nearly so) path from the MAVs current position to a designated goal state. Past work in this area using full-size unmanned aerial vehicles (UAVs) has predominantly been performed in benign environments. However, due to their small size, MAVs are capable of operating in indoor environments which are more cluttered. This requires planners to account for the vehicle heading in addition to its spatial position in order to successfully navigate. In addition, due to the short flight times of MAVs along with the inherent hazards of operating in close proximity to obstacles, we desire the trajectories to be as cost-optimal as possible. Our approach uses an anytime planner based on A* that performs a graph search on a four-dimensional (4-D) (x,y,z, heading) lattice. This allows for the generation of close-to-optimal trajectories based on a set of precomputed motion primitives along with the capability to provide trajectories in real-time allowing for on-the-fly re-planning as new sensor data is received. We also account for arbitrary vehicle shapes, permitting the use of a non-circular footprint during the planning process. By not using the overly conservative circumscribed circle for collision checking, we are capable of successfully finding optimal paths through cluttered environments including those with narrow hallways. Analytically, we show that our planner provides bounds on the sub-optimality of the solution it finds. Experimentally, we show that the planner can operate in real-time in both a simulated and real-world cluttered environments.

In the aerial supply delivery problem, an unmanned aircraft needs to deliver supplies as close as possible to the desired location. This involves choosing, flying to, sensing, and landing at a safe landing site that is most accessible from the goal. The problem is often complicated by the fact that the availability of these landing sites may be unknown before the mission begins. Therefore, the aircraft needs to compute a sequence of actions that will minimize the expected value of the objective function. The problem of computing this sequence corresponds to planning under uncertainty in the environment. In this paper, we show how it can be solved efficiently via a recently developed probabilistic planning framework, called Probabilistic Planning with Clear Preferences (PPCP). We show that the problem satisfies the Clear Preferences assumption required by PPCP, and therefore all the theoretical guarantees continue to hold. The experimental results in simulation demonstrate that our approach can solve large-scale problems in realtime while experiments on our custom quad-rotor helicopter provide a proof of concept for the planner.

In the aerial supply delivery problem, an un-manned aircraft needs to deliver supplies as close as possible to the desired goal location. This involves choosing and landing at a landing site that is closest to or most accessible from the desired goal location. The problem is complicated by the fact that the status of candidate landing sites is unknown before the mission begins, and instead the aircraft needs to compute a sequence according to which it flies and senses the candidate landing sites in order to land as quickly as possible. The problem of computing this sequence corresponds to planning under uncertainty about environment. In this paper, we show how it can be solved efficiently via a recently developed probabilistic planning framework, called Probabilistic Planning with Clear Preferences (PPCP). We show that the problem satisfies the Clear Preferences assumption required by PPCP,and therefore all the theoretical guarantees continue to hold. The experimental results in simulation show that our approachcan solve large-scale problems in real-time while experiments on a physical quad-rotor provide proof of concept.