برنامهریزی پویا همزمان برای مسائل مبتنی بر شبکه و کاربرد آن برای برنامه ریزی مسیر زمان واقعی

This paper presents a concurrent approach for solving dynamic programming optimization problems such as the generation of optimal cost-to-go functions for robot motion planning in dense environments. Such optimization techniques are core to many robotics problems, but traditional approaches are inherently impractical due to their computational complexity. This limitation usually results in a configuration space being subsampled, lower configuration space coverage, less frequent planner updates, or the use of sub-optimal graph-based road map methods. The proposed approach provides mathematically identical results to traditional grid-based motion planning solvers in at least an order of magnitude less time by leveraging the concurrent architecture found in modern graphics hardware. Although results given here are presented in a robot navigation context, they are also applicable to other dynamic programming problems.

A current robust and accurate method of robot motion planning involves representing an environment as a grid-based configuration space. For example, [1] use laser range sensor data to construct a two-dimensional occupancy grid before generating an exhaustive cost-to-go function for planning. An optimal path is then extracted from the cost-to-go function, similar to [2], and is approximated to a nonholonomic solution under the constraints of the Unmanned Ground Vehicle’s (UGV’s) dynamic model. While planning on grid-based configuration spaces is accurate, generating a cost-to-go function can be computationally expensive [3] and [4]. The remainder of this paper provides a review of existing robot motion planning techniques and highlights prior approaches that either suffer from or attempt to defer the computational complexity of existing grid-based motion planners. A brief background is given in Section 3 to provide the reader with context of the proposed approach. Each evolution of the algorithm and implementation is then presented in Section 4, with experimental results given to properly assess the performance of each flavor in Section 5. In particular, the differing flavors presented focus on reducing the number of repeated redundant calculations performed in the GPU together with minimizing CPU time managing these subregions, with the CPU management being performed post iteration. The flavors are summarized here as follows for the reader’s convenience: Subregions Grouping cells within an occupancy grid and choosing to evaluate cells within this group together on the graphics hardware to properly balance GPU execution time against CPU management time. Caching subregion cell values Caching a subregion’s cell values at the post iteration check of titi so they can be used again at the ti+1ti+1 post iteration check without having to be re-read from the graphics hardware. Delayed post iteration check Performing the post iteration check every 2nd and 3rd iteration. Statistically scheduled post iteration check Performing the post iteration check on a schedule that targets the statistically appropriate iterations to perform the check on. A discussion is then raised in Section 5.6 on the generalized performance of the concurrent algorithm relative to a traditional sequential algorithm as a function of the characteristics of modern and possible future processor hardware. Future work is then discussed before conclusions are given.

This paper presented a concurrent grid-based implementation of a dynamic programming algorithm and demonstrated its application in the context of robot motion planning. While the two-dimensional implementation presented here is applicable to many ground vehicle applications, many motion planning problems exist in three and higher dimensions. Initial work has been undertaken to implement and benchmark a similar three-dimensional motion planner on graphics hardware. A simulation of this implementation running on a completely obstacle free occupancy volume can be seen at [34], with a second simulation involving a variety of obstacles available at [35]. Higher dimensional configuration spaces are mapped to a one-dimensional buffer in graphics memory, with a pair of linear functions that map a coordinate in RnRn to an index ii in a contiguous memory buffer. The kernel must also be modified so that in the 3D case, for example, in addition to checking the 8 neighbors on the same XYXY-plane for a given cell, the adjacent cells in the planes above and below must also be considered when evaluating the global cost of a cell. As the dimensionality of the configuration space increases, traditional robot motion planners tend to become exponentially computationally complex [4]. In contrast, a higher dimensional concurrent implementation provides the potential for a greater number of concurrent cell calculations to be made. For example, in a 2D configuration space, the wavefront at any iteration of the algorithm is a 1D perimeter to the evaluated cells. In a 3D configuration space, the wavefront is a 2D surface. In addition to robot motion planning in higher dimensions, areas of application outside of navigation are also being investigated, such as efficient protein folding. The algorithm has been proven to be at least an order of magnitude more efficient than mainstream sequential solutions and as graphics hardware capabilities continue to improve this theoretical advantage will become more evident in practical applications.