Solving routing problems for multiple cooperative Unmanned Aerial Vehicles using Transformer networks, vol. 122, pp. 106085, 2023
원문 초록
Missions involving Unmanned Aerial Vehicle usually consist of reaching a set of regions, performing some actions in each region, and returning to a determined depot after all the regions have been successfully visited or before the fuel/battery is totally consumed. Hence, planning a route becomes an important task for many applications, especially if a team of Unmanned Aerial Vehicles is considered. From this team, coordination and cooperation are expected to optimize results of the mission. In this paper, a system for managing multiple cooperative Unmanned Aerial Vehicles is presented. This system divides the routing problem into two stages: initial planning and routing solving. Initial planning is a first step where the regions to be visited are grouped in multiple clusters according to a distance criterion, with each cluster being assigned to each of the Unmanned Aerial Vehicles. Routing solving computes the best route for every agent considering the clusters of the initial planning and a variant of the Orienteering Problem. This variant introduces the concept of shared regions, allowing an Unmanned Aerial Vehicle to visit regions from other clusters and compensating for the suboptimal region clustering of the previous stage. The Orienteering Problem with shared regions is solved using the deep learning architecture Transformer along with a deep reinforcement learning framework. This architecture is able to obtain high-quality solutions much faster than conventional optimization approaches. Extensive results and comparison with other Combinatorial Optimization algorithms, including cooperative and non-cooperative scenarios, have been performed to show the benefits of the proposed solution.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
초과 경쟁적 결과를 넘어서: 최적 집행 게임을 위한 심층 강화학습에서의 담합 행위
Beyond Supra-Competitive Outcomes: Collusive Behaviour in Deep Reinforcement Learning for Optimal Execution Games
본 논문에서는 이탈을 억제하고 담합의 행동적 증거를 제공하는 학습된 징벌 메커니즘을 규명함으로써, 최적 집행(optimal-execution) 게임에서 나타나는 초과 경쟁적 결과(supra-competitive outcomes)에 대한 기존 연구 결과를 확장합니다. 저자들은 2인 유한 시간 지평 Almgren-Chriss 청산 게임에서 이 메커니즘을 조사합니다. 에피소드 내 가격 및 행동 이력에 접근할 수 있는 독립적인 근접 정책 최적화(PPO) 에이전트들은 내시(Nash) 벤치마크보다 낮은 비용을 달성합니다. 학습된 평균 청산 일정에 대항해 학습(training)시킴으로써 수익성 있는 이탈을 식별한 뒤, 원래 에이전트 중 하나에 이탈의 첫 거래를 강제합니다. 이에 상대방은 청산을 가속화하는 방식으로 대응합니다. 이러한 대응은 모든 실행과 두 플레이어 역할 모두에서 이탈자의 이득을 상쇄하고도 남으며, 동일한 이탈 하에서 처벌하지 않았을 때와 비교해 처벌자의 평균 보수는 실질적으로 변하지 않은 채 유지됩니다. 처벌자는 더 수익성이 높고 징벌성이 덜한 청산 계획을 선택할 수 있음에도 불구하고, 자신의 평균 보수를 보존하면서 이탈자에게 더 큰 손실(loss)을 부과합니다. 이에 상응하는 이탈과 그에 따른 추가 매도는 학습 과정에서 증가했다가 이후 감소하지만, 최종 정책은 효과적인 징벌적 대응을 유지합니다. 저자들은 처벌이 이탈로 인한 이득을 능가하는지 여부, 그리고 거래 행동의 변화가 부과된 손실을 설명할 만큼 충분히 큰지 여부라는 두 가지 검증 기준을 정식화합니다. 테스트된 이탈에 대해 두 검증 기준 모두 충족됩니다. 종합하면, 이러한 발견들은 학습된 초과 경쟁적 결과가 담합이라는 해석을 뒷받침하는 행동적 및 경제적 증거를 제공합니다.
FairTest: 다중 에이전트 강화학습 시스템을 위한 탐색 기반 공정성 테스트
FairTest: Search-Based Fairness Testing for Multi-Agent Reinforcement Learning Systems
다중 에이전트 강화학습(MARL)은 하나의 환경을 공유하는 에이전트 팀을 학습시키며, 에이전트들이 정책을 함께 학습한다. 학습은 팀 return을 최대화하지만, 높은 return이 모든 에피소드에서 에이전트 간 보상이 공정하게 분배된다는 뜻은 아니다. 테스트는 심층 강화학습의 실패를 찾아내는 확립된 방법이지만, MARL의 공정성을 다루는 방법은 거의 없다. 본 연구에서는 MARL 정책의 불공정한 실행을 찾는 탐색 기반 테스트 접근법 FairTest를 제안한다. 설계는 탐색 안내(search guidance)와 테스트 우선순위화를 결합한다. 안내는 세 가지 적합度(fitness) 함수로 각 후보를 점수화한다. 하나는 이미 수행된 실행의 공정성을 측정하고, 다른 하나는 추상 상태와 공정성 특징으로부터 공정성을 예측하며, 세 번째는 정책에서 의사결정 불확실성을 읽는다. 교차(crossover)와 변이(mutation)는 관측된 실행으로부터 추가 후보를 도출한다. 우선순위화는 예측된 공정성과 의사결정 불확실성으로 후보를 순위화하여, 실행이 실패가 예상되는 후보에 도달하도록 한다. FairTest는 세 가지 환경과 두 가지 MARL 알고리즘에서 평가되며, 네 가지 기준선에 동일한 예산을 부여한다. 통계적 유의성과 큰 효과 크기(effect size)를 가진 세 가지 기준선 대비 가장 많은 공정성 실패를 탐지한다. 실패 횟수는 평균적으로 가장 강한 기준선보다 221% 더 많으며, 커버리지(coverage)는 평균 23% 개선된다.
잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝
Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling
잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.
LEAP-CBF: 최소 노력 적대적 포텐셜(Least-Effort Adversarial Potentials)을 이용한 불확실 시스템용 안전 필터
LEAP-CBF: A Safety Filter for Uncertain Systems with Least-Effort Adversarial Potentials
제어 장벽 함수(Control Barrier Function, CBF)는 비선형 동역학 시스템의 안전성을 보장하기 위해 널리 쓰이는 안전 필터이다. 그러나 시스템에 불확실성과 외란이 존재할 때는 CBF의 강건(robust) 변형을 사용해야 하는데, 이러한 변형은 구성하기 어려울 수 있으며 특히 입력 제약이 있는 고차원 시스템에서는 지나치게 보수적일 수 있다. 본 연구에서는 이러한 문제를 해결하기 위한 새로운 접근법으로, 최소 노력 적대적 포텐셜(Least-Effort Adversarial Potentials, LEAP)을 제안한다. LEAP은 주어진 상태가 외란에 대해 갖는 강건성을, 외란이 실패를 일으키기 위해 필요한 노력의 크기로 정량화하는 인증서(certificate)이다. 우리는 LEAP이 외란이 없는 시스템에 대한 CBF임을 보이는 동시에, 누적 노력이 제한된 외란에 대해 강건한 안전 필터를 구성하는 데에도 사용될 수 있음을 보인다. 또한 온-정책(on-policy) 심층 강화학습(deep reinforcement learning)으로 LEAP을 구성하는 방법을 제안한다. 이어서 외란과 불확실성이 있는 다양한 멀티 에이전트 시스템에 대한 시뮬레이션에서 LEAP을 시연한다. 마지막으로, 사족보행 로봇과 쿼드로터를 이용한 하드웨어 실험을 통해 LEAP이 실제 로봇 시스템의 외란과 불확실성을 다루는 데 적합함을 검증한다.
학습과 탐색을 통한 조합 최적화에서 인간형 해법 이해
Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search
인간은 고급 컴퓨터 알고리즘에게도 계산적으로 어려운 조합 최적화 문제에 대해 종종 좋은 해를 찾는다. 유클리드 여행 판매원 문제(TSP)에서 사람들은 시간과 계산에 심각한 제약이 있음에도 불구하고 거의 최적인 경로(tour)를 빠르게 생성한다. 경로를 인간형으로 만드는 요인은 무엇이며, 이러한 해를 어떻게 학습할 수 있을까? 본 연구에서는 유클리드 TSP에서 인간의 수행을 대규모 행동 및 계산 조사를 통해 이러한 질문에 답한다. 우리는 TSP 인스턴스의 넓은 공간을 샘플링하고, 인간의 해를 수집했으며, 유효한 경로에 대한 확률 분포를 정의하는 어텐션 기반 포인팅 메커니즘을 갖춘 순환 신경망인 Pointer Networks에 기반한 신경 정책과 이를 비교했다. 우리는 강화학습(RL), 최적 경로로부터의 지도학습, 인간 경로로부터의 지도학습, 그리고 최적 경로 지도학습 사전학습 후 RL 미세조정을 포함한 여러 목적 함수로 이러한 네트워크를 학습시켰다. 인간의 경로는 최적 경로와 동일하지는 않았지만, 거의 최적인 기하학적 분지(basin)를 차지했다: 최적 해와 많은 구조적 특성을 공유하면서도 체계적인 인간 특유의 편차를 유지했다. 인간 경로에 대한 최상의 설명은 최적 경로의 직접적 모방이 아니라, 최적 경로로 사전학습하고 RL로 미세조정한 뒤 $\text{Best-of-}N$ 샘플링을 통해 디코딩한 모델이었다. 이러한 결과는 인간형 해가 구조화된 지도학습, RL, 테스트 시점 탐색의 결합으로부터 창발할 수 있음을 시사하며, 많은 현대 인공지능 시스템의 기반이 되는 계산 원리와 공명한다.
심층 강화학습을 활용한 라스트마일 픽업 통합 주문 배차 및 경로 최적화
Integrated Order Dispatching and Routing for Last-Mile Pickup via Deep Reinforcement Learning
최근 몇 년간 라스트마일 픽업 운영의 복잡성이 증가하면서 물류 플랫폼에서 빠르고 정확한 의사결정에 대한 필요성이 커졌다. 이 과제는 근본적으로 두 가지 핵심적이고 긴밀히 결합된 의사결정 과정, 즉 주문 배차와 경로 최적화에 의해 촉발된다. 이들을 개별적으로 해결하면 상호 의존성을 간과하게 되며, 완전한 end-to-end 학습은 희소 보상(sparse reward)으로 인해 대규모이고 가변적인 규모의 인스턴스에서 불안정하고 비용이 많이 든다. 이 문제를 해결하기 위해, 학습된 경로 오라클(routing oracle)과 실시간 배차 휴리스틱을 결합하는 통합 최적화 프레임워크를 제안한다. 경로 최적화 하위 문제에 대해서는 Look-Ahead Courier-Personalized 디코더를 갖춘 Dynamic-Residual Graph Attention Network 인코더를 개발한다. 배차 하위 문제에 대해서는 경로 오라클이 지도하는 국소 탐색(local search) 기반 배차 휴리스틱을 개발하며, 오라클은 실시간 확장성을 유지하면서 후보 배송 기사를 선택하기 위한 근최적 해를 제공한다. Cainiao Logistics의 실제 데이터셋을 활용한 광범위한 실험을 통해 오프라인 평가와 온라인 롤링 호라이즌(rolling-horizon) 시뮬레이션을 포함하여 접근법의 성능을 검증했다. 실험 결과, 제안 방법은 해 품질과 해결 시간 측면에서 다른 벤치마크를 능가하며, 실시간 대규모 라스트마일 픽업 문제 해결에 물류 기업을 효과적으로 지원할 수 있음을 보여준다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.