Nash Equilibrium in Competitive Path Planning
http://rpg.ifi.uzh.ch/docs/RSS18_Spica.pdf
Beyond its use in analysis of social networks, game theory has a number of applications. One such application is described in the paper above where the concept of Nash Equilibrium has been used for solving path planning in 2-player drone racing. The paper lays out some definitions for the specific problem. These include the race track, how to compute a location along the track, a condition regarding drone flight dynamics, and a collision condition. Specifically, the problem is setup to optimize how far along the track the drone is subject to the following conditions: the drone’s position is an integral of its velocity (estimated by a summation), two drones cannot be too close to each other, the drone must remain within the bounds of the track, and the velocity of the drone must be less than it’s maximum velocity. These equations only show that one drone affects the other drone’s path only when close enough to collide. The paper notes that this isn’t the only effect of the collision condition. In a race, the drone doesn’t need to be the fastest. It only need to finish before the other one. To capture this effect the optimized equation is changed to be a weighted difference between the drone’s positions. The way that Game Theory fits into this problem is described in the paper but in general, the optimization of the problem is solving for a Nash equilibrium. At any move, the drones will plan a path that is the best possible given the opponent’s path and vice versa. The actual solving and optimization is computed using optimization methods and solving for convergence (this is the main portion of the paper). Specifically, solving for the Nash Equilibrium is solved using the Iterative Best Response algorithm by solving for each drone’s path holding the opposite drone’s path constant until the solution converges.
It’s interesting to see that game theory can be applied to a significantly more abstract concept and seeing briefly how a Nash Equilibrium can be estimated. Once racing is viewed as a game with multiple players it’s easier to see how to connect game theory to fields outside of the usual. This concept shows how it can be extended to a variety of situations. Furthermore, the Iterative Best Response method for computing the Nash Equilibrium is also quite intuitive. Computing each side iteratively seems like it should converge to the correct solution but this is not as easy to prove. Also seeing that one can terminate the computation before convergence and achieve a reasonable result is interesting. Since strict time constraints can be applied to practical applications it’s also good to see how an estimate can be used in place of the true solution.