Solving the Hamilton-Jacobi-Bellman Equation for Route Planning Problems Using Tensor Decomposition

Sammanfattning: Optimizing routes for multiple autonomous vehiclesin complex traffic situations can lead to improved efficiency intraffic. Attempting to solve these optimization problems centrally,i.e. for all vehicles involved, often lead to algorithms that exhibitthe curse of dimensionality: that is, the computation time andmemory needed scale exponentially with the number of vehiclesresulting in infeasible calculations for moderate number ofvehicles. However, using a numerical framework called tensordecomposition one can calculate and store solutions for theseproblems in a more manageable way. In this project, we investi-gate different tensor decomposition methods and correspondingalgorithms for solving optimal control problems, by evaluatingtheir accuracy for a known solution. We also formulate complextraffic situations as optimal control problems and solve them.We do this by using the best tensor decomposition and carefullyadjusting different cost parameters. From these results it canbe concluded that the Sequential Alternating Least Squaresalgorithm used with canonical tensor decomposition performedthe best. By asserting a smooth cost function one can solve certainscenarios and acquire satisfactory solutions, but it requiresextensive testing to achieve such results, since numerical errorsoften can occur as a result of an ill-formed problem.