Although dynamic games provide a rich paradigm for modeling agents' interactions, solving these games for real-world applications is often challenging. Many real-wold interactive settings involve general nonlinear state and input constraints which couple agents' decisions with one another. In this work, we develop an efficient and fast planner for interactive planning in constrained setups using a constrained game-theoretical framework. Our key insight is to leverage the special structure of agents' objective and constraint functions that are common in multi-agent interactions for fast and reliable planning. More precisely, we identify the structure of agents' cost functions under which the resulting dynamic game is an instance of a constrained potential dynamic game. Constrained potential dynamic games are a class of games for which instead of solving a set of coupled constrained optimal control problems, a Nash equilibrium can be found by solving a single constrained optimal control problem. This simplifies constrained interactive trajectory planning significantly. We compare the performance of our method in a navigation setup involving four planar agents and show that our method is on average 20 times faster than the state-of-the-art. We further provide experimental validation of our proposed method in a navigation setup involving one quadrotor and two humans.
翻译:虽然动态游戏为模拟代理人的互动提供了丰富的范例,但解决这些用于现实世界应用的游戏往往具有挑战性。许多真实的狼人互动环境涉及一般的非线性状态和输入限制,这是双方代理人相互决定的。在这项工作中,我们开发了一个高效和快速的规划者,利用一个有限的游戏理论框架,在受限制的设置中进行互动规划。我们的关键洞察力是利用代理人的目标和约束功能的特殊结构,这种结构是多试剂相互作用中常见的,以便进行快速和可靠的规划。更确切地说,我们确定代理人的成本功能结构,由此形成的动态游戏是潜在动态游戏的一个受限制的例子。受约束的潜在动态游戏是一种游戏,是一种游戏,不是解决一系列相互制约的最佳控制问题,而是通过解决单一的受限制的最佳控制问题,可以找到一种纳什平衡。这大大简化了受限制的互动式轨迹规划。我们比较了我们的方法在由四个平面剂组成的导航装置中的表现,并表明我们的方法平均比状态和状态的快20倍。我们进一步实验验证了我们提出的导航装置中涉及一个方形和两个人的导航装置中的方法。