Beginning at the spatio-temporal nodes connected to the start state by the edges of the STPS as exemplarily shown for one node in Figure REF , the LTPS performs a search in the spatio-temporal graph. It generates edges connecting spatio-temporal nodes of the following layers until the desired planning horizon is reached. In general, a spatio-temporal node can be reached with multiple paths through the spatio-temporal graph, ending in the time and velocity intervals of the node (blue squares). Each path has a total cost which is the sum of the edge costs along the path beginning at the start state. Instead of expanding all reached states with edges to the next layer, only the end state of the cheapest path ending within the intervals is used as an initial state for further expansion from the considered node. This procedure follows the principle of dynamic programming and not only reduces the number of nodes by the use of intervals, but also prevents the exponential growth of the number of edges to be generated with an increasing planning horizon. As in [1]} we sample constant accelerations along the spatial edges to create the spatio-temporal edges. This is shown in Figure REF , simplified with one acceleration (green) and one deceleration (orange) profile applied per spatial edge. Instead of an exhaustive search that proceeds from layer to layer, we perform a search based on Dijkstra's algorithm [2]} which is suited for graphs that are built during the search and often referred to as uniform-cost search. This algorithm makes it possible to go back in layers and expands only the node with the cheapest path to reach it. While the uniform-cost search retains optimality in terms of our cost function, it requires significantly fewer edges to be generated in our application, reducing the computation time by a factor of three compared to an exhaustive search. Another major advantage is that the search can be interrupted if it approaches an upper calculation time limit. In this case, we select the – at this stage – cheapest available path through the graph that satisfies the planning horizon and still obtain a suboptimal solution.
