시간적 유연성을 활용한 다중 에이전트 경로 재계획의 사전 연산
Precomputing Multi-Agent Path Replanning Using Temporal Flexibility
한국어 초록
에이전트(agent)에 지연이 발생하면 일반적으로 다른 에이전트들과의 충돌이 발생하기 때문에, 다중 에이전트 계획을 실행하는 것은 까다로울 수 있습니다. 따라서 안전한 새로운 계획을 신속하게 찾아야 합니다. 지연된 에이전트만 재계획하는 것은 종종 효율적인 계획을 도출하지 못하며, 때로는 실현 가능한 계획조차 도출하지 못하기도 합니다. 반면에 다른 에이전트들까지 재계획하는 것은 연쇄적인 변경과 지연을 초래할 수 있고 계산 비용도 많이 듭니다. 본 논문에서는 연쇄 지연을 방지하면서 다른 에이전트들의 시간적 유연성(temporal flexibility)을 추적하고 활용하여 단일 지연 에이전트를 효율적으로 재계획하는 방법을 제시합니다. 이러한 유연성은 초기에 지연된 에이전트 외의 다른 에이전트들과의 순서를 변경하지 않거나 다른 에이전트들을 추가로 지연시키지 않으면서 해당 에이전트가 감당할 수 있는 최대 지연 시간입니다. 제안하는 알고리즘인 FlexSIPP는 지연된 에이전트에 대해 가능한 모든 계획을 사전 연산하고 주어진 시나리오 내에서 다른 에이전트들의 변경 사항을 반환합니다. 밀집된 네덜란드 철도망에서의 열차 재계획 실제 사례 연구와 MovingAI MAPF 벤치마크 세트에서 본 방식을 입증합니다. 실험 결과는 FlexSIPP가 실제 상황의 조정과 관련된 효과적인 해법을 합리적인 시간 내에 제공함을 보여줍니다.
원문 초록
Executing a multi-agent plan can be challenging when an agent is delayed, because this typically creates conflicts with other agents. So, we need to quickly find a new safe plan. Replanning only the delayed agent often does not yield an efficient plan, and sometimes cannot even yield a feasible one. On the other hand, replanning other agents may lead to a cascade of changes and delays, and it is computationally expensive. We show how to efficiently replan a single delayed agent by tracking and using the temporal flexibility of other agents while avoiding cascading delays. This flexibility is the maximum delay that the agent can take without changing the order with agents other than the initially delayed agent, or further delaying other agents. Our algorithm, FlexSIPP, precomputes all possible plans for the delayed agent and returns the changes to the other agents within the given scenario. We demonstrate our method in a real-world case study of replanning trains in the densely-used Dutch railway network and in the MovingAI MAPF benchmark set. Our experiments show that FlexSIPP provides effective solutions relevant to real-world adjustments, and within a reasonable timeframe.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
동적 환경에서의 최적 계획 수립
Optimal Planning in a Dynamic World
배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.
Optimal any-angle path planning in static and dynamic environments
Optimal Sensor Scheduling and Selection for Continuous-Discrete Kalman Filtering with Auxiliary Dynamics
SystolicAttention: Fusing FlashAttention within a Single Systolic Array
ANN-Based Grid Impedance Estimation for Adaptive Gain Scheduling in VSG Under Dynamic Grid Conditions
Confucius3-Math: A Lightweight High-Performance Reasoning LLM for Chinese K-12 Mathematics Learning
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
Revision after a bug was found in the code. The fixes do not alter the conclusions; the MAPF results are slightly different from those published at SoCS26. The railway results changed as the code was rearranged, now returning proper valid paths, with a new data representation to show the actual differences between FlexSIPP and MAEDeR. In the Fig1 example a3s route changed to show a1s rerouting