Safe navigation in dense, urban driving environments remains an open problem and an active area of research. Unlike typical predict-then-plan approaches, game-theoretic planning considers how one vehicle's plan will affect the actions of another. Recent work has demonstrated significant improvements in the time required to find local Nash equilibria in general-sum games with nonlinear objectives and constraints. When applied trivially to driving, these works assume all vehicles in a scene play a game together, which can result in intractable computation times for dense traffic. We formulate a decentralized approach to game-theoretic planning by assuming that agents only play games within their observational vicinity, which we believe to be a more reasonable assumption for human driving. Games are played in parallel for all strongly connected components of an interaction graph, significantly reducing the number of players and constraints in each game, and therefore the time required for planning. We demonstrate that our approach can achieve collision-free, efficient driving in urban environments by comparing performance against an adaptation of the Intelligent Driver Model and centralized game-theoretic planning when navigating roundabouts in the INTERACTION dataset. Our implementation is available at http://github.com/sisl/DecNashPlanning.
翻译:与典型的预测和计划方法不同,游戏理论规划考虑一种车辆的计划会如何影响另一种车辆的行动。最近的工作表明,在普通游戏中找到带有非线性目标和限制的本地Nash 平衡游戏所需的时间有了显著改进。当这些工程在轻描淡写地应用到驾驶时,假定在现场的所有车辆都一起玩游戏,这可能导致密集交通的难以计算时间。我们制定一种分散的游戏理论规划方法,假设代理人只在其观察区域内玩游戏,我们认为这是对人驾驶的更合理的假设。对于互动图中所有密切相关的组成部分,运动会同时进行,大大减少每个游戏的玩家数目和限制,从而缩短规划所需的时间。我们证明,我们的方法可以实现无碰撞、高效率地在城市环境中驾驶,办法是将智能驱动器的性能与适应性能模型和中央游戏-理论规划进行比较,在InterACtion数据集的圆形旁飞行时,我们的执行可以在http://giashum/Decimal.comsising上查到。