Efficient motion planning for problems lacking optimal substructure
This addresses motion planning for robots in hazardous environments, offering a novel algorithmic solution for a specific incremental improvement in handling non-standard cost functions.
The paper tackles motion planning for robots in risk zones with a super-linear penalty for cumulative exposure, proposing a cost function that balances path length and risk time, and develops an algorithm that generalizes Dijkstra's to handle the lack of optimal substructure, achieving an O((n_B·n) log(n_B·n) + n_B·m) runtime and demonstrating efficiency in simulations.
We consider the motion-planning problem of planning a collision-free path of a robot in the presence of risk zones. The robot is allowed to travel in these zones but is penalized in a super-linear fashion for consecutive accumulative time spent there. We suggest a natural cost function that balances path length and risk-exposure time. Specifically, we consider the discrete setting where we are given a graph, or a roadmap, and we wish to compute the minimal-cost path under this cost function. Interestingly, paths defined using our cost function do not have an optimal substructure. Namely, subpaths of an optimal path are not necessarily optimal. Thus, the Bellman condition is not satisfied and standard graph-search algorithms such as Dijkstra cannot be used. We present a path-finding algorithm, which can be seen as a natural generalization of Dijkstra's algorithm. Our algorithm runs in $O\left((n_B\cdot n) \log( n_B\cdot n) + n_B\cdot m\right)$ time, where~$n$ and $m$ are the number of vertices and edges of the graph, respectively, and $n_B$ is the number of intersections between edges and the boundary of the risk zone. We present simulations on robotic platforms demonstrating both the natural paths produced by our cost function and the computational efficiency of our algorithm.