Home | People | Research | Publications| Links | News | Contact  

Multiresolution Path Planning for Autonomous Agents

The current practice in control system design is to develop the control algorithm, without giving any specific thought
to the available hardware required for its implementation. Finding the suitable control hardware to implement the algorithm is an after-the-fact task. For many problems involving embedded control hardware with limited computational resources (both in terms of available CPU and memory) this traditional way of doing things may not be possible. This research aims at reversing this line of thinking and introduce a new paradigm, such that the operational limitations of the hardware become part of the control algorithm design specifications.

As a particular instance of this transformative control design philosophy, the ubiquitous problem of vehicle navigation
in a natural environment full of obstacles will be used. A new multi-resolution algorithm is being proposed to efficiently encode all possible paths inside this environment. The main idea used is the fact that paths have lower dimensionality than the ambient space they lie in, and hence, a more efficient encoding of the problem data than standard 2D and 3D cell decompositions should be possible. As a result, the search space is considerably reduced. The main mathematical tool used is wavelets and beamlets, whose unique properties capture directionality, in addition to scale and locality. The adoption of beamlets enables for numerically more efficient algorithms than previous cell decomposition-only based path planning approaches. As an added benefit of the approach, the typically uncoupled geometric and dynamic planner layers in the motion planning hierarchy can now be naturally coordinated by passing information about the allowable dynamic envelope of the vehicle to the geometric layer. This ensures that the paths computed by the geometric layer will indeed be rendered dynamically feasible.


 Wavelet Cell Decompositions for Path Planning: We propose a computationally efficient, hierarchical path-planning algorithm for autonomous agents (e.g., UAVs) navigating in a partially known environment W using an adaptive, discrete, cell-based approximation of W. The innovation of our approach hinges on using wavelets and beamlets to encode the district levels of fidelity (resolution) of W at different distances from the agent's current position. The motivation for this approach is simple: first, the agent's immediate reaction to an obstacle or a threat is needed only at the vicinity of its current position. Faraway obstacles or threats do not (or should not) have a large effect on the vehicle's immediate motion. Therefore, it is not prudent from a computational point of view to find a solution with great accuracy over large distances or over a long time horizon. The most accurate and reliable information of the environment is required (or it is even available) only at the vicinity of the vehicle. In that sense, the proposed algorithm can be classified under the category of "agent-centered'' search
algorithm. Pictorially, such a multiresolution decomposition of the environment (say, an elevation map in this case) can be visualized as shown in the figure below.

 In a departure from these quadtree-based methods, in this work we make use of the wavelet transform to perform the required multiresolution decompositions of the environment. This has several advantages. First, the wavelet transform provides a very fast decomposition  of a function at different levels of resolution (the  computational complexity of the wavelet transform is of order O(n)where n is the input data. This is even better than the FFT which has complexity of order O(n log_2 n). Since the range and resolution levels can be chosen by the user, the proposed algorithm results in search graphs of known prior complexity. The algorithm is therefore scalable, and can be tailored to the available computational resources of the agent. Second, the use of wavelet transform has the added benefit of allowing the construction of the associated cell connectivity relationships directly from the wavelet coefficients, thus eliminating the need for quadtrees. Finally, the use of wavelet transform provides flexibility in terms of the choice of the wavelet basis functions, which can help in reducing the complexity of the resulting abstraction (i.e., topological search graph) of the environment.

Example movie form multiresolution path-planning

From Wavelets to Beamlets: Wavelets induce a multiresolution hierarchy over a wide range of locations and scales. However, they exhibit a small, fixed number of preferred orientations (horizontal, vertical, diagonal), and are better described as roughly isotropic. A given path in 2D (or its approximation by a chain of line segments) has distinct, local bias towards certain orientations. Beamlets provide a framework for multiscale analysis similar to that of wavelets, in which line segments play a role analogous to the role played by points in wavelet analysis. They add two crucial elements missing from wavelet processing, however: orientation and elongation information. Beamlets are proven to achieve optimal asymptotic performance in detection problems. For instance, they have been used to design an efficient coding method for images made of curves. Beamlets are numerically more efficient than traditional curve processing algorithms, because they use the multiscale structure among them in an innovative manner.


m-A* Algorithm: We propose an innovative beamlet-based graph structure for path planning that utilizes multiscale information of the environment. This information is collected via a bottom-up fusion algorithm. This new graph structure goes beyond "nearest-neighbor'' connectivity, incorporating "long-distance'' interactions between the nodes of the graph. Based on this new graph structure, we obtain a multiscale version of A*, which is advantageous when preprocessing is allowable and feasible. Compared to the benchmark A* algorithm, the use of multiscale information leads to an improvement in terms of computational complexity.


The main idea of the proposed multiscale graph structure can be summarized as follows. Consider a uniform n x n grid representing the world (or an image) assuming, without loss of generality, 4-nearest-neighbor connectivity. There are O(n^2) vertices and  O(n^2) edges in the corresponding graph. In order to reduce the number of node expansions (the most time-consuming step in all graph search algorithms), the proposed graph structure first employs a recursive dyadic partitioning to divide the environment into "blocks'' of different sizes, where the sizes are determined by the relative importance of information within those blocks. The collection of all blocks of the same size defines the information scale. The preprocessing of information within each block is conducted via an innovative Bottom-Up Fusion algorithm, which "fuses'' multiscale information from finer scales to coarser scales. Therefore, a properly designed search algorithm, defined on the preprocessed "blocks,'' can significantly reduce the number of vertices in the graph, while only slightly increasing the number of edges. As a result, path searching can be sped-up significantly, when preprocessing is feasible.


Support for this project is provided by NSF.

Selected Publications

Home | People | Research | Publications| Links | Contact