Path Planning Games
Path planning is a fundamental and extensively explored problem in robotic control. We present a novel economic perspective on path planning. Specifically, we investigate strategic interactions among path planning agents using a game theoretic path planning framework. Our focus is on economic tension between two important objectives: efficiency in the agents' achieving their goals, and safety in navigating towards these. We begin by developing a novel mathematical formulation for path planning that trades off these objectives, when behavior of other agents is fixed. We then use this formulation for approximating Nash equilibria in path planning games, as well as to develop a multi-agent cooperative path planning formulation. Through several case studies, we show that in a path planning game, safety is often significantly compromised compared to a cooperative solution.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Offline Grid-Based Coverage path planning for guards in games
Algorithmic approaches to exhaustive coverage have application in video games, enabling automatic game level exploration. Current designs use simple heuristics that frequently result in poor performance or exhibit unnatu…
Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek
Resource allocation games such as the famous Colonel Blotto (CB) and Hide-and-Seek (HS) games are often used to model a large variety of practical problems, but only in their one-shot versions. Indeed, due to their extre…
Open-Ended Question AnsweringPathBench: A Benchmarking Platform for Classical and Learned Path Planning Algorithms
Path planning is a key component in mobile robotics. A wide range of path planning algorithms exist, but few attempts have been made to benchmark the algorithms holistically or unify their interface. Moreover, with the r…
BenchmarkingWidth-based Lookaheads with Learnt Base Policies and Heuristics Over the Atari-2600 Benchmark
We propose new width-based planning and learning algorithms inspired from a careful analysis of the design decisions made by previous width-based planners. The algorithms are applied over the Atari-2600 games and our bes…
Atari GamesResearch Vision: Multi-Agent Path Planning for Cops And Robbers Via Reactive Synthesis
We propose the problem of multi-agent path planning for a generalization of the classic Cops and Robbers game via reactive synthesis. Specifically, through the application of LTLt and Coordination Synthesis, we aim to ch…
Program Synthesis