Time Constrained Randomized Path Planning Using Spatial Networks

Abstract—Real time planning of optimal paths remains an open problem in many applications of autonomous systems. This paper demonstrates a computationally efficient method for generating a set of feasible paths through parameterization into a series of nodes. The nodes and the arcs make up a directed graph. The state of the environment is embedded in an occupancy based map. A notion of optimality is introduced by combining the directed graph with this map. Network optimization techniques are used to find the best path through the directed graph. NOMENCLATURE A Original set of arcs (edges) in network A ̃ Arcs to add in network B Spatial domain of occupancy map Cs Node subset at step s d Num steps in prediction horizon D(j) Span interval of arc j d−(j) Lower span interval of arc j d+(j) Upper span interval of arc j E Incidence matrix of network f() Returns node coordinate (f: i ∈ I → ℜ2) g() Returns occupancy map score (g: x → ℜ) I Set of nodes (vertices) in network j ∼ (i, i′) Arc starting at node i and ending at node i′ N Num times spatial network algorithm is run N+, N − Starting/ending node sets in min path algorithm M Num ops for (℘2) w / PF Algorithm M ′ Num ops for (℘2) w / combinatorial approac