Resource-Constrained Shortest Path with Polytopic Reset Sets
For robotic path planning under resource constraints, this provides a framework for optimal path computation with budget resets, though the approach is incremental.
This paper solves the resource-constrained shortest path problem with polytopic reset sets, showing the optimal path has a distinct geometric structure. The proposed two-step approach (graph-based then convex programming) yields near-optimal solutions, demonstrated with a numerical experiment.
This paper investigates the problem of computing the shortest path between two states under resource constraints in environments with resource-replenishment regions. Namely, the length of the path is limited by a budget that can be restored within polytopic replenishment regions. We show that the optimal path in this problem exhibits a distinct geometric structure: it consists of straight-line segments, changes direction at replenishment regions, and visits regions at most once. We propose an approach to solve the continuous problem in two steps: using a graph-based approach, followed by convex programming. First, we define a graph whose nodes are possible waypoints of feasible paths, and the edges are the Euclidean distances between these nodes. To obtain a discrete set of nodes that ensure a feasible and near-optimal solution, we utilize a wavefront algorithm. With a sufficiently small spacing between wavefronts, the solution of the shortest path problem on this graph yields the optimal sequence of polytopes to visit. Next, we use convex optimization on this sequence of polytopes to find the exact optimal path. A numerical experiment is presented to demonstrate the effectiveness of the approach. This approach provides a framework for solving the resource-constrained shortest path with budget reset.