다중 에이전트 경로 검색

그리드 환경에서 Multi-에이전트 경로 찾기 예제입니다.

MAPF(Multi-Agent Path Finding) 문제는 다중 에이전트 계획의 한 예로, 해당 위치에서 할당된 타겟에 대한 에이전트 그룹에 대한 무충돌 경로 계산으로 구성됩니다.모든 에이전트가 목표 셀에 도달할 때까지의 시간 스텝 수로 정의되는 특정 목적 함수를 최적화하는 경로를 찾는 것이 목적이기 때문에 이는 최적화 문제입니다.MAPF는 경로 찾기 문제의 다중 에이전트 일반화이며 그래프 이론의 맥락에서 최단 경로 문제와 밀접하게 관련되어 있습니다.

MAPF 문제를 해결하기 위해 몇 가지 알고리즘이 제안되었습니다.그 복잡성 때문에 대규모 환경이나 다수의 에이전트가 있는 환경에서는 최적의 접근법이 실현되지 않을 수 있습니다.그러나 자동화된 창고 및 공항 관리와 같이 MAPF가 관여하는 애플리케이션을 고려할 때, 솔루션의 효율성과 효과 사이의 균형에 도달하는 것이 중요하다.

문제의 공식화

기존 MAPF 문제의 요소는 다음과 같습니다.

a $A=\{1,2,...,k\}$ A $=$ { $A=\{1,2,...,k\}$ , $A=\{1,2,...,k\}$ , $A=\{1,2,...,k\}$ . $A=\{1,2,...,k\}$ . , $A=\{1,2,...,k\}$ $}$ {{ $displaystyle$ A=\{ $1,$ 2, $...,$ k\}}개 k ${\displaystyle$ k $}$ 개 $A=\{1,2,...,k\}$ $k$ $에이전트$ ;
무방향 $G=(V,E)$ G $=$ ( $G=(V,E)$ , $G=(V,E)$ ) { $displaystyle$ G=( $V,E$ $V$ 서V {\ $displaystyle$ V $}$ 는 $V$ 노드 $E$ 이고E {\ $displaystyle$ E $}$ 는 $E$ 에지 세트입니다.노드는 에이전트의 가능한 위치를 나타내며, 호는 이러한 위치 간의 가능한 연결입니다.
$s:A\to V$ s $s:A\to V$ $s:A\to V$ $s:A\to V$ {\ $displaystyle$ s: $각$ 에이전트를 그 시작점과 관련짓는 $A\to$ V $.$
$t:A\to V$ t $t:A\to V$ $t:A\to V$ $t:A\to V$ {\ $displaystyle$ t $:$ $각$ 에이전트를 대상 포인트와 관련짓는 A $\to$ V $.$

시간은 이산적이며 각 에이전트가 각 시간 단계에서 1개의 작업을 수행할 수 있다고 가정합니다.액션에는 에이전트가 노드에 남아 있는 대기 액션과 에이전트가 인접 노드로 이동할 수 있는 이동 액션의 두 가지 유형이 있습니다.작용은 $a:V\to V$ a $a:V\to V$ $a:V\to V$ $a:V\to V$ \ $displaystyle$ a $:$ 로 공식화됩니다. $a(v)=v'$ $\to$ V $a:V\to V$ 즉 $a(v)=v'$ v ${\$ {\ $displaystyle$ $a(v)=v'$ v $'$ 가 $v'$ v{\ $displaystyle$ v $}$ 에 $v$ $v$ 인접하여 v ${\$ {\displaystyle v $v'$ 와 다르거나 $v$ {\ $displaystyle$ v $'$ 에 머무르는 $경우$ $= v$ {\ $displaystyle$ v $'$ 에서 $a(v)=v'$ $v'$ v로 $v'$ 하는 동작을 나타냅니다. $v$ v $v=v'$ $v=v'$ \ $displaystyle$ v $=v'$ 인 $v=v'$

에이전트는 시작 지점에서 대상 위치로 이동하는 일련의 작업을 수행합니다. $에이전트$ i { $style$ i $}$ 에 $i$ 의해 수행된 일련의 작업은 $\pi _{i}=(a_{1},a_{2},...,a_{n})$ $\pi _{i}=(a_{1},a_{2},...,a_{n})$ $=$ ( $\pi _{i}=(a_{1},a_{2},...,a_{n})$ $\pi _{i}=(a_{1},a_{2},...,a_{n})$ , $\pi _{i}=(a_{1},a_{2},...,a_{n})$ a $\pi _{i}=(a_{1},a_{2},...,a_{n})$ , $\pi _{i}=(a_{1},a_{2},...,a_{n})$ . $\pi _{i}=(a_{1},a_{2},...,a_{n})$ , $\pi _{i}=(a_{1},a_{2},...,a_{n})$ ) $\pi _{i}=(a_{1},a_{2},...,a_{n})$ { $displaystyle \pi$ _ ${i$ }= ( $a_{1}, a_{2},$ ..., $a_{$ n})로 $\pi _{i}=(a_{1},a_{2},...,a_{n})$ 나타나며 계획이라고 합니다.(I) - 그렇죠 - 기초부터 시작하자 - 기초부터 시작하자아이.MAPF 문제에 대한 해결책은 k\ $displaystyle$ k \ ( ( ( (플랜 $k$ (에이전트마다 1개씩) $k$ 입니다.이러한 플랜이 서로 충돌하지 않도록 합니다.에이전트가 대상에 도달하면 대상 위치에 그대로 있을 수도 ^[1]있고 사라질 수도 있습니다.

충돌 유형

MAPF 문제에 대한 유효한 해결책을 얻으려면 k $\display k}$ $k$ 의 $k$ 싱글 에이전트 플랜이 서로 충돌하지 않도록 해야 합니다.plan $\pi _{i}$ $\pi _{i}$ $i$ \ displaystyle \ $pi$ _ { i $}$ $\pi _{i}[x]$ $plan$ plandisplay $\pi _{i}$ [ [ [ ${\$ [ [ [ [ [ i $\pi _{i}$ \ $displaystyle$ $\pi$ $_$ $\pi _{i}$ { $i$ $}$ $i$ i i i i ii \ $displaystyle$ x $i$ i of $x$ of of of $of$ of i \ $displaystyle$ _ { i} 。5가지 충돌 유형을 구분할 수 있습니다.etween 2개의 플랜 $\pi _{i}$ i \ $display$ style \ $pi$ _ { $i$ } 및 $\pi _{i}$ ${\$ $\pi _{j}$ \ $display$ style \ $pi$ _ { $j$ ^[1] 。

컨플릭트의 종류: (a) 엣지 컨플릭트, (b) 정점 컨플릭트, (c) 다음 컨플릭트, (d) 사이클 컨플릭트, (e) 스왑 컨플릭트.

정점 충돌: 두 에이전트가 동시에 같은 위치에 있을 경우 플랜 $\pi _{i}$ i \ $displaystyle$ \ $pi$ _ { $j$ }와 $\pi _{i}$ $\pi _{j}$ 플랜 $\pi _{j}$ j \ $display style$ \ $pi$ _ { $j$ } 사이에 정점 충돌이 발생합니다.공식적으로 정점 경합은 $\pi _{i}[x]=\pi _{j}[x]$ i [ $\pi _{i}[x]=\pi _{j}[x]$ ] $=$ $\pi _{i}[x]=\pi _{j}[x]$ j [ $]{$ $displaystyle \pi$ _ ${i}[x$ ]=\ $pi$ _ ${j}[x$ 일 때 발생합니다.
에지 충돌: 두 에이전트가 동시에 동일한 방향으로 동일한 에지를 교차할 때마다 에지 충돌이 발생합니다. 즉, $\pi _{i}[x]=\pi _{j}[x]$ i [ $\pi _{i}[x]=\pi _{j}[x]$ ] $\pi _{i}[x]=\pi _{j}[x]$ j [ $]$ \ $displaystyle$ \ $pi$ $_$ { $i$ } [ $x$ = $\pi _{i}[x+1]=\pi _{j}[x+1]$ i [ $x$ + $\pi _{i}[x+1]=\pi _{j}[x+1]$ ] $\pi _{i}[x+1]=\pi _{j}[x+1]$ $\pi _{i}[x+1]=\pi _{j}[x+1]$ j $\pi _{i}[x+1]=\pi _{j}[x+1]$ [ $\pi _{i}[x+1]=\pi _{j}[x+1]$ + $1$ ] _ $pi$ \ pi \ $pi$ \ pi $=$ [ $1$ ]정점 충돌이 허용되지 않으면 모서리 충돌이 존재할 수 없습니다.
다음 충돌: 다음 충돌은 특정 시간 단계에서 에이전트가 이전 시간 단계에서 다른 에이전트에 의해 점유된 위치를 점유할 때 발생합니다.수학적으로 다음 경합은 $\pi _{i}[x+1]=\pi _{j}[x]$ i [ $\pi _{i}[x+1]=\pi _{j}[x]$ + $\pi _{i}[x+1]=\pi _{j}[x]$ ] $=$ $\pi _{i}[x+1]=\pi _{j}[x]$ j [ $]{$ $displaystyle \pi$ _ ${i}[x+1$ ]=\ $pi$ _ ${j}[x$ 로 표시됩니다.
주기 충돌: 일련의 에이전트(3개 이상)가 주기 내에서 회전하는 것처럼 이동할 때마다 주기 충돌이 발생합니다.즉, 각 에이전트는 이전에 다른 에이전트가 차지했던 위치를 사이클에서 한 단계 먼저 차지합니다.다음 충돌이 금지되면 주기 충돌이 발생할 수 없습니다.
스와핑 컨플릭트: 스와핑컨플릭트는 2개의 에이전트가 서로 다른 방향으로 같은 엣지를 동시에 통과하면서 위치를 교환하는 경우입니다. $\pi _{i}[x+1]=\pi _{j}[x]$ i [ $\pi _{i}[x+1]=\pi _{j}[x]$ + $\pi _{i}[x+1]=\pi _{j}[x]$ ] $=$ $\pi _{i}[x+1]=\pi _{j}[x]$ j $\pi _{i}[x+1]=\pi _{j}[x]$ [ $]$ \ $displaystyle$ $\pi$ $_$ $\pi _{j}[x+1]=\pi _{i}[x]$ { $i$ } [ $x$ + $\pi _{j}[x+1]=\pi _{i}[x]$ ]= $\pi _{j}[x+1]=\pi _{i}[x]$ [ [ $i$ $\pi _{j}[x+1]=\pi _{i}[x]$ 로 $표시$ 됩니다.

MAPF 문제를 공식화할 때 어떤 경합이 허용되고 어떤 경합이 금지되는지 결정할 수 있습니다.허용 및 거부된 충돌에 대한 통일된 표준은 존재하지 않지만 정점과 가장자리 충돌은 둘 다 ^[1]허용되지 않습니다.

목적 함수

단일 에이전트 계획을 계산할 때 목표는 사용자 정의 목적 함수를 최대화하는 것입니다.채택해야 할 표준 목적 함수는 없지만, 가장 일반적인 것은 다음과 같습니다.^[1]

flowtime: 이 척도는 각 에이전트가 목표 위치에 도달하기 위해 사용하는 시간 단계를 합산하여 얻습니다.형식적으로는 $\sum _{i\in A}|\pi _{i}|$ A $\sum _{i\in A}|\pi _{i}|$ \ $displaystyle \$ $sum$ _ ${i\in$ A} \ $pi$ $\sum _{i\in A}|\pi _{i}|$ _ ${i}$ $\sum _{i\in A}|\pi _{i}|$ 와 같습니다.여기서 $,i,\in$ A는 $\pi _{i},i\in A$ 충돌이 없는 단일 에이전트 플랜입니다.
makespan : 모든 에이전트가 태스크를 완료하기 위해 필요한 시간 스텝의 수 $i$ 로 $\max _{i\in A}|\pi _{i}|$ 됩니다. $\pi _{i}$ 서 $\pi _{i}$ $(\displaystyle \pi$ $\pi _{i}$ _ ${i})$ 는 유효한 $,i\in A$ 솔루션의 일부입니다.
최종 기한에 도달한 목표의 최대화: 목표는 최종 ^[2]기한에 도달한 에이전트의 수를 최대화하는 유효한 솔루션을 찾는 것입니다.

알고리즘

MAPF 문제를 해결하기 위해 몇 가지 알고리즘이 제안되었습니다.문제는 평면 ^[4]그래프 또는 ^[5]그리드와 유사한 그래프를 고려할 때도 최적의 제작 범위 또는 흐름 시간 ^[3]솔루션을 찾는 것이 NP-어렵다는 것이다.차선의 솔루션에 대해서는 $({$ ^[6]보다 작은 최적 계수를 가진 makespan-optimal 솔루션을 찾는 것이 NP 어려운 것으로 나타났다.최적의 MAPF 솔버는 고품질 솔루션을 반환하지만 효율은 낮다.대신, 경계 차최적 솔버와 차최적 솔버는 더 효율적이지만 솔루션의 효과는 더 낮습니다.또한 MAPF ^[7]문제를 해결하기 위해 기계 학습 접근법이 제안되었다.

우선 순위 계획

계산의 복잡성에 대처하기 위한 하나의 접근방식은 우선도가 높은 ^[8]계획입니다.이는 MAPF 문제를k\ $displaystyle$ k $\$ single-agent $k$ 경로 검색 $k$ 로 분리하는 것으로 구성됩니다.

첫 번째 단계는 각 에이전트에 지정된 우선순위에 대응하는 고유 번호 $\{1,2,...,k\}$ 2, $\{1,2,...,k\}$ $}({displaystyle \$ 1 $, 2$ , $..., k\})$ 를 $\{1,2,...,k\}$ 할당하는 것입니다.그런 다음 우선 순위에 따라 각 에이전트에 대해 대상 위치에 도달하기 위한 계획이 계산됩니다.계획을 세울 때 에이전트는 이미 계획을 계산한 우선순위가 높은 다른 에이전트 경로와의 충돌을 피해야 합니다.

이러한 설정에서 MAPF 문제의 해결책을 찾는 것은 시간 확장 그래프의 ^[9]최단 경로 문제에 해당합니다.시간 확장 그래프는 시간의 경과를 고려한 그래프입니다.각 노드는 2개의 엔트리 $(v,t)$ , $)$ 로 구성됩니다. $v$ 서v $displaystyle$ v $}$ 는 $v$ $노드명$ 이고 t {\ $displaystyle$ t $}$ 는 $t$ 타임스텝입니다각 노드 $(v,t)$ $)$ { $displaystyle (v,t)}$ 는 $(v,t)$ 노드 $,$ + $(u,t+1)$ )에 링크되어 있습니다.이 $경우$ u ${$ $displaystyle$ u}는 $(u,t+1)$ $u$ v ${displaystyle$ $v$ $}$ 에 $v$ $u$ 하고 u{ $displaystyle$ ( $u$ $,$ t $u$ $+1)$ 는 t $t+1$ 에서 $t+1$ 점유되지 않습니다.

우선 순위 계획의 단점은 그것이 건전한 접근법이라고 해도(유효한 솔루션을 반환한다) 최적도 ^[10]완전하지도 않다는 것입니다.즉, 알고리즘이 솔루션을 반환할 것이라고 확신할 수 없으며, 그 경우에도 솔루션이 최적이 아닐 수 있습니다.

최적의 MAPF 솔버

최적의 MAPF 솔버의 ^[10]4가지 카테고리를 구별할 수 있습니다.

A*의 확장: 이 카테고리의 알고리즘은 A* 접근방식의 수정 버전을 사용합니다.
비용 트리 검색 ^[11]증가: 증가하는 검색 트리와 해당 알고리즘을 이해하는 MAPF 문제에 대한 새로운 공식화가 제안된다.이 알고리즘은 2개의 레벨로 구성되며 MAPF 문제의 유효한 솔루션이 단일 에이전트용 솔루션세트로 구성된다는 가정에 의존합니다.
Conflict-Based Search: 이 알고리즘은 단일 에이전트 경로 검색 ^[12]문제를 해결할 때와 마찬가지로 경로를 계산하고 충돌을 피하기 위해 증분 방식으로 제약을 추가합니다.
제약 프로그래밍:^[13] 이러한 접근 방식에서는 MAPF 문제가 일련의 제약으로 변환되어 SAT 및 혼합 정수 프로그래밍(MIP) 솔버와 같은 특정 제약 해결사를 사용하여 해결됩니다.

경계 차선의 MAPF 솔버

한계 차선 알고리즘은 최적성과 솔루션 비용 간의 균형을 제공합니다.최적 솔루션 비용에 요인을 곱한 값과 같은 비용으로 솔루션을 반환하기 때문에 특정 요인에 의해 제한된다고 합니다.MAPF 경계 ^[10]차최적 솔버는 최적 MAPF 솔버에 대해 제시된 동일한 분류에 따라 분할할 수 있습니다.

바리에이션

MAPF 문제를 정의하는 방법은 그리드 환경에 있다는 사실이나 시간이 이산적이라는 가정 등 다양한 측면을 변경할 수 있다.이 섹션에서는 기존의 MAPF 문제의 몇 가지 변형에 대해 설명합니다.

익명 MAPF

MAPF 버전입니다.이 버전에서는 타깃로케이션 세트는 존재하지만 에이전트에는 ^[14]특정 타깃이 할당되지 않습니다.타겟에 도달한 에이전트가 중요한 것은 타겟이 완료된다는 것입니다.이 버전의 약간의 변경은 에이전트가 그룹으로 분할되어 ^[15]각 그룹이 일련의 타깃을 수행해야 하는 경우입니다.

복수 에이전트 픽업 및 배송

MAPF 문제는 실제 어플리케이션과 관련된 몇 가지 측면을 캡처할 수 없습니다.예를 들어, 자동화된 창고에서는 로봇이 여러 가지 작업을 차례로 완료해야 하는 경우가 많습니다.이 때문에 Multi-Agent Pickup and Delivery(MAPD;^[16] 멀티 에이전트픽업 앤 딜리버리)라고 불리는 확장 MAPF 버전이 제안됩니다.MAPD 설정에서 에이전트는 태스크 스트림을 완료해야 합니다.각 태스크는 픽업 위치 및 전송 위치로 구성됩니다.작업 완료를 계획할 때 경로는 로봇의 현재 위치에서 시작하여 픽업 지점을 통과하여 작업 전달 위치에서 끝나야 합니다.MAPD는 태스크가 ^[16]증분적으로 도착하는 MAPF의 "라이프" 버전으로 간주됩니다.

기존 MAPF를 넘어서는

에이전트가 그리드 환경에 있고 속도가 일정하며 시간이 이산적이라는 가정은 가설을 단순화합니다.많은 연구는 속도와 방향과 같은 ^[17]작용제의 운동학적 제약을 고려하거나 호의 무게가 모두 ^[18]1이라는 가정을 지나간다.다른 연구들은 분리된 시간 가정을 제거하는 데 초점을 맞추고 있으며, 조치의 지속 시간은 정확히 한 번의 시간 ^[19]단계와 동일하다.현실을 반영하지 않는 또 다른 가정은 에이전트가 그들이 있는 환경의 정확히 하나의 세포를 차지한다는 것입니다. 이 ^[20]가설을 극복하기 위해 일부 연구가 수행되었습니다.에이전트가 완전히 겹치지 않더라도 서로 충돌할 수 있으므로 에이전트의 모양과 지오메트리에 따라 새로운 유형의 충돌이 발생할 수 있습니다.

적용들

MAPF는 다음과 같은 실제 상황에서 적용할 수 있습니다.

자동화된 창고: 창고 로지스틱스는 MAPF의 주요 산업 응용 분야입니다.창고 내 자동화가 생산성 ^[21]수준을 높이는 데 성공하는 것으로 나타났습니다.
공항 운영: 혼잡한 공항에서 MAPF 알고리즘을 사용하여 ^[22]항공기를 운송하는 견인 차량을 조정할 수 있습니다.이러한 문제를 최적화할 수 있으면 환경에도 이점이 있습니다.
자율형 모바일 서비스 로봇: 서비스 로봇은 비산업 환경에서 ^[23]인간을 위해 위험하고 반복적인 작업을 수행하는 자동화된 에이전트입니다.그들의 주된 목표는 인간을 돕는 것이다.
비디오 게임: 이러한 설정에서 MAPF의 유용성은 플레이어가 혼잡한 비디오 게임 ^[24]환경에서 에이전트 팀을 이동해야 할 때 찾을 수 있습니다.

「」를 참조해 주세요.

메모들

^ ^a ^b ^c ^d ^e ^f Stern, Roni; Sturtevant, Nathan R.; Felner, Ariel; Koenig, Sven; Ma, Hang; Walker, Thayne; Li, Jiaoyang; Atzmon, Dor; Cohen, Liron; Kumar, T. K. Satish; Boyarski, Eli; Barták, Roman (2019). "Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Ma, Hang; Wagner, Glenn; Felner, Ariel; Li, Jiaoyang; Kumar, T. K. Satish; Koenig, Sven (2018). "Multi-Agent Path Finding with Deadlines". arXiv:1806.04216 [cs.AI].
^ Yu, Jingjin; LaValle, Steven M. (2013). "Structure and intractability of optimal multi-robot path planning on graphs". AAAI'13: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. 27: 1443–1449. doi:10.1609/aaai.v27i1.8541. S2CID 11655439.
^ Yu, Jingjin (January 2016). "Intractability of Optimal Multirobot Path Planning on Planar Graphs". IEEE Robotics and Automation Letters. 1 (1): 33–40. arXiv:1504.02072. doi:10.1109/LRA.2015.2503143. S2CID 10275469.
^ Banfi, Jacopo; Basilico, Nicola; Amigoni, Francesco (October 2017). "Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes". IEEE Robotics and Automation Letters. 2 (4): 1941–1947. doi:10.1109/LRA.2017.2715406. S2CID 36801258.
^ Ma, Hang; Tovey, Craig; Sharon, Guni; Kumar, T. K.; Koenig, Sven (5 March 2016). "Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem". Proceedings of the AAAI Conference on Artificial Intelligence. 30 (1). doi:10.1609/aaai.v30i1.10409. S2CID 1585005.
^ Sartoretti, Guillaume; Kerr, Justin; Shi, Yunfei; Wagner, Glenn; Kumar, T. K. Satish; Koenig, Sven; Choset, Howie (July 2019). "PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning". IEEE Robotics and Automation Letters. 4 (3): 2378–2385. doi:10.1109/LRA.2019.2903261. S2CID 52191178.
^ Cap, Michal; Novak, Peter; Kleiner, Alexander; Selecky, Martin (July 2015). "Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots". IEEE Transactions on Automation Science and Engineering. 12 (3): 835–849. doi:10.1109/TASE.2015.2445780. S2CID 347488.
^ Silver, David (2021). "Cooperative Pathfinding". Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. 1 (1): 117–122. doi:10.1609/aiide.v1i1.18726. S2CID 17714238.
^ ^a ^b ^c Stern, Roni (2019). "Multi-Agent Path Finding – An Overview". Artificial Intelligence. Lecture Notes in Computer Science. 11866: 96–115. doi:10.1007/978-3-030-33274-7_6. ISBN 978-3-030-33273-0. S2CID 204832267.
^ Sharon, Guni; Stern, Roni; Goldenberg, Meir; Felner, Ariel (February 2013). "The increasing cost tree search for optimal multi-agent pathfinding". Artificial Intelligence. 195: 470–495. doi:10.1016/j.artint.2012.11.006.
^ Sharon, Guni; Stern, Roni; Felner, Ariel; Sturtevant, Nathan R. (February 2015). "Conflict-based search for optimal multi-agent pathfinding". Artificial Intelligence. 219: 40–66. doi:10.1016/j.artint.2014.11.006. S2CID 3809045.
^ Bartak, Roman; Zhou, Neng-Fa; Stern, Roni; Boyarski, Eli; Surynek, Pavel (November 2017). "Modeling and Solving the Multi-agent Pathfinding Problem in Picat". 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI): 959–966. doi:10.1109/ICTAI.2017.00147. ISBN 978-1-5386-3876-7. S2CID 7819470.
^ Kloder, S.; Hutchinson, S. (August 2006). "Path planning for permutation-invariant multirobot formations". IEEE Transactions on Robotics. 22 (4): 650–665. doi:10.1109/TRO.2006.878952. S2CID 62805494.
^ Ma, Hang; Koenig, Sven (2016). "Optimal Target Assignment and Path Finding for Teams of Agents". arXiv:1612.05693 [cs.AI].
^ ^a ^b Ma, Hang; Li, Jiaoyang; Kumar, T. K. Satish; Koenig, Sven (30 May 2017). "Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks". arXiv:1705.10868 [cs.AI].
^ Hoenig, Wolfgang; Kumar, T. K. Satish; Cohen, Liron; Ma, Hang; Xu, Hong; Ayanian, Nora; Koenig, Sven (2016). "Multi-Agent Path Finding with Kinematic Constraints". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Barták, Roman; Švancara, Jiří; Vlk, Marek (2018). "A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs" (PDF). Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems: 748–756.
^ Andreychuk, Anton; Yakovlev, Konstantin; Surynek, Pavel; Atzmon, Dor; Stern, Roni (April 2022). "Multi-agent pathfinding with continuous time". Artificial Intelligence. 305: 103662. arXiv:1901.05506. doi:10.1016/j.artint.2022.103662. S2CID 207791641.
^ Li, Jiaoyang; Surynek, Pavel; Felner, Ariel; Ma, Hang; Kumar, T. K. Satish; Koenig, Sven (17 July 2019). "Multi-Agent Path Finding for Large Agents". Proceedings of the AAAI Conference on Artificial Intelligence. 33: 7627–7634. doi:10.1609/aaai.v33i01.33017627. S2CID 53687939.
^ Wurman, Peter R.; D'Andrea, Raffaello; Mountz, Mick (20 March 2008). "Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses". AI Magazine. 29 (1): 9. doi:10.1609/aimag.v29i1.2082.
^ Morris, Robert; Pasareanu, Corina S.; Luckow, Kasper; Malik, Waqar; Ma, Hang; Kumar, T. K. Satish; Koenig, Sven (2016). "Planning, Scheduling and Monitoring for Airport Surface Operations". AAAI Workshop: Planning for Hybrid Systems.
^ Veloso, Manuela; Biswas, Joydeep; Coltin, Brian; Rosenthal, Stephanie (2015). "CoBots: Robust Symbiotic Autonomous Mobile Service Robots". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Ma, Hang; Yang, Jingxing; Cohen, Liron; Kumar, T. K. Satish; Koenig, Sven (2017). "Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

외부 링크

MAPF.info

[stern-1] ^ ^a ^b ^c ^d ^e ^f Stern, Roni; Sturtevant, Nathan R.; Felner, Ariel; Koenig, Sven; Ma, Hang; Walker, Thayne; Li, Jiaoyang; Atzmon, Dor; Cohen, Liron; Kumar, T. K. Satish; Boyarski, Eli; Barták, Roman (2019). "Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks" (PDF). {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[deadline-2] Ma, Hang; Wagner, Glenn; Felner, Ariel; Li, Jiaoyang; Kumar, T. K. Satish; Koenig, Sven (2018). "Multi-Agent Path Finding with Deadlines". arXiv:1806.04216 [cs.AI].

[nphard-3] Yu, Jingjin; LaValle, Steven M. (2013). "Structure and intractability of optimal multi-robot path planning on graphs". AAAI'13: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence. 27: 1443–1449. doi:10.1609/aaai.v27i1.8541. S2CID 11655439.

[planar-4] Yu, Jingjin (January 2016). "Intractability of Optimal Multirobot Path Planning on Planar Graphs". IEEE Robotics and Automation Letters. 1 (1): 33–40. arXiv:1504.02072. doi:10.1109/LRA.2015.2503143. S2CID 10275469.

[5] Banfi, Jacopo; Basilico, Nicola; Amigoni, Francesco (October 2017). "Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes". IEEE Robotics and Automation Letters. 2 (4): 1941–1947. doi:10.1109/LRA.2017.2715406. S2CID 36801258.

[6] Ma, Hang; Tovey, Craig; Sharon, Guni; Kumar, T. K.; Koenig, Sven (5 March 2016). "Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem". Proceedings of the AAAI Conference on Artificial Intelligence. 30 (1). doi:10.1609/aaai.v30i1.10409. S2CID 1585005.

[rl-7] Sartoretti, Guillaume; Kerr, Justin; Shi, Yunfei; Wagner, Glenn; Kumar, T. K. Satish; Koenig, Sven; Choset, Howie (July 2019). "PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning". IEEE Robotics and Automation Letters. 4 (3): 2378–2385. doi:10.1109/LRA.2019.2903261. S2CID 52191178.

[prpl-8] Cap, Michal; Novak, Peter; Kleiner, Alexander; Selecky, Martin (July 2015). "Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots". IEEE Transactions on Automation Science and Engineering. 12 (3): 835–849. doi:10.1109/TASE.2015.2445780. S2CID 347488.

[9] Silver, David (2021). "Cooperative Pathfinding". Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. 1 (1): 117–122. doi:10.1609/aiide.v1i1.18726. S2CID 17714238.

[overview-10] Stern, Roni (2019). "Multi-Agent Path Finding – An Overview". Artificial Intelligence. Lecture Notes in Computer Science. 11866: 96–115. doi:10.1007/978-3-030-33274-7_6. ISBN 978-3-030-33273-0. S2CID 204832267.

[11] Sharon, Guni; Stern, Roni; Goldenberg, Meir; Felner, Ariel (February 2013). "The increasing cost tree search for optimal multi-agent pathfinding". Artificial Intelligence. 195: 470–495. doi:10.1016/j.artint.2012.11.006.

[cbs-12] Sharon, Guni; Stern, Roni; Felner, Ariel; Sturtevant, Nathan R. (February 2015). "Conflict-based search for optimal multi-agent pathfinding". Artificial Intelligence. 219: 40–66. doi:10.1016/j.artint.2014.11.006. S2CID 3809045.

[ics-13] Bartak, Roman; Zhou, Neng-Fa; Stern, Roni; Boyarski, Eli; Surynek, Pavel (November 2017). "Modeling and Solving the Multi-agent Pathfinding Problem in Picat". 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI): 959–966. doi:10.1109/ICTAI.2017.00147. ISBN 978-1-5386-3876-7. S2CID 7819470.

[14] Kloder, S.; Hutchinson, S. (August 2006). "Path planning for permutation-invariant multirobot formations". IEEE Transactions on Robotics. 22 (4): 650–665. doi:10.1109/TRO.2006.878952. S2CID 62805494.

[15] Ma, Hang; Koenig, Sven (2016). "Optimal Target Assignment and Path Finding for Teams of Agents". arXiv:1612.05693 [cs.AI].

[Lifelong-16] Ma, Hang; Li, Jiaoyang; Kumar, T. K. Satish; Koenig, Sven (30 May 2017). "Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks". arXiv:1705.10868 [cs.AI].

[kinematics-17] Hoenig, Wolfgang; Kumar, T. K. Satish; Cohen, Liron; Ma, Hang; Xu, Hong; Ayanian, Nora; Koenig, Sven (2016). "Multi-Agent Path Finding with Kinematic Constraints". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[arcw-18] Barták, Roman; Švancara, Jiří; Vlk, Marek (2018). "A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs" (PDF). Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems: 748–756.

[timecont-19] Andreychuk, Anton; Yakovlev, Konstantin; Surynek, Pavel; Atzmon, Dor; Stern, Roni (April 2022). "Multi-agent pathfinding with continuous time". Artificial Intelligence. 305: 103662. arXiv:1901.05506. doi:10.1016/j.artint.2022.103662. S2CID 207791641.

[20] Li, Jiaoyang; Surynek, Pavel; Felner, Ariel; Ma, Hang; Kumar, T. K. Satish; Koenig, Sven (17 July 2019). "Multi-Agent Path Finding for Large Agents". Proceedings of the AAAI Conference on Artificial Intelligence. 33: 7627–7634. doi:10.1609/aaai.v33i01.33017627. S2CID 53687939.

[kiva-21] Wurman, Peter R.; D'Andrea, Raffaello; Mountz, Mick (20 March 2008). "Coordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses". AI Magazine. 29 (1): 9. doi:10.1609/aimag.v29i1.2082.

[airport-22] Morris, Robert; Pasareanu, Corina S.; Luckow, Kasper; Malik, Waqar; Ma, Hang; Kumar, T. K. Satish; Koenig, Sven (2016). "Planning, Scheduling and Monitoring for Airport Surface Operations". AAAI Workshop: Planning for Hybrid Systems.

[cobots-23] Veloso, Manuela; Biswas, Joydeep; Coltin, Brian; Rosenthal, Stephanie (2015). "CoBots: Robust Symbiotic Autonomous Mobile Service Robots". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[24] Ma, Hang; Yang, Jingxing; Cohen, Liron; Kumar, T. K. Satish; Koenig, Sven (2017). "Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[1]

[2]

[4]

[5]

[3]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

Search

다중 에이전트 경로 검색

네임스페이스

더

목차