Efficient path planning algorithms in reach-avoid problems
Autor: | Jerry Ding, Claire J. Tomlin, Zhengyuan Zhou, Haomiao Huang, Ryo Takei |
---|---|
Rok vydání: | 2018 |
Předmět: |
0209 industrial biotechnology
Computer science Computation ComputingMilieux_PERSONALCOMPUTING 02 engineering and technology Commit Network topology Set (abstract data type) 020901 industrial engineering & automation Control and Systems Engineering Obstacle Differential game 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Motion planning Electrical and Electronic Engineering Algorithm Curse of dimensionality |
Zdroj: | Automatica. 89:28-36 |
ISSN: | 0005-1098 |
Popis: | We consider a multi-player differential game, referred to as a reach-avoid game, in which one set of attacking players attempts to reach a target while avoiding both obstacles and capture by a set of defending players. Unlike pursuit–evasion games, in this reach-avoid game one set of players must not only consider the other set of players, but also the target. This complexity makes finding solutions to such games computationally challenging, especially as the number of players grows. We propose an approach to solving such games in an open-loop sense, where the players commit to their control actions prior to the beginning of the game. This reduces the dimensionality of the required computations, thus enabling efficient computation of feasible solutions in real time for domains with arbitrary obstacle topologies. We describe two such formulations, each of which is conservative towards one side, and derive numerical algorithms based upon modified fast-marching methods (FMM) for computing their solutions. |
Databáze: | OpenAIRE |
Externí odkaz: |