arXiv:2606.18730v1 cs.RO

이동 장애물이 있는 이동 목표 외판원 문제를 위한 이단계 이중 수준 탐색

Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles

Allen George Philip, Anoop Bhat, Sivakumar Rathinam, Howie Choset

제출 2026-06-17

한국어 초록

이동 목표 외판원 문제(MT-TSP)는 정적 창고에서 출발하여 할당된 시간 창 내에 이동 목표 집합을 방문한 후 창고로 돌아오는 에이전트의 최소 비용 궤적을 찾는 문제입니다. 본 논문에서는 MT-TSP의 일반화된 버전인 이동 장애물이 있는 이동 목표 외판원 문제(MT-TSP-MO)를 연구합니다. 이 문제에서 에이전트 궤적은 이동 장애물을 피해야 합니다. 우리는 기성 솔버를 사용하여 해결할 수 있는 혼합 정수 원뿔 프로그래밍(MICP) 공식과, 문제에 대한 고품질의 실현 가능한 해를 계산하는 빠르고 확장 가능한 이단계 이중 수준 탐색(TPBS) 알고리즘을 제안합니다. 최대 40개의 목표와 40개의 장애물이 있는 다양한 문제 인스턴스에 대해 기존 기준선(baseline) 알고리즘과 비교하여 우리의 접근 방식을 평가했습니다. 결과는 제안된 두 방법 모두 성공률, 해 비용, 계산 시간 측면에서 기준선을 현저히 능가함을 보여줍니다.

원문 초록

The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and returns to the depot. In this article, we study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where the agent trajectory must avoid moving obstacles. We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm that computes high-quality feasible solutions for the problem. We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles. The results demonstrate that both the proposed methods significantly outperform the baseline with respect to success rates, solution costs, and computation time.

요약

이동 장애물이 있는 이동 목표 외판원 문제(MT-TSP-MO)에서 에이전트가 시간 창 내 이동 목표를 방문하며 이동 장애물을 피하는 최소 비용 궤적을 찾기 위해, 혼합 정수 원뿔 프로그래밍(MICP) 공식과 이단계 이중 수준 탐색(TPBS) 알고리즘을 제안한다. 최대 40개 목표·40개 장애물 인스턴스에서 기존 기준선 대비 성공률, 해 비용, 계산 시간 모두에서 두 방법이 크게 우수함을 보였다.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.18730v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.03312v1cs.AI공통 태그 Motion Planning, Scheduling, Combinatorial Optimization

동적 환경에서의 최적 계획 수립

Optimal Planning in a Dynamic World

배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.

arXiv:2609.22974v1cs.RO공통 태그 Navigate, Motion Planning, Combinatorial Optimization

로봇 내비게이션을 위한 최소 장애물 변위 계획의 호리즌 슬라이싱 접근법

A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation

본 논문에서는 로봇 동작 계획(motion planning) 관점에서 최소 장애물 변위 계획(Minimum Obstacle Displacement Planning) 문제를 다룬다. 이 문제는 처음에 충돌 없는 경로가 없을 때 이동 가능한 장애물을 변위시켜 목표 지점까지의 실행 가능한 경로를 찾는 것을 포함한다. 우리는 이 문제가 계산적으로 어렵고, 특히 장애물을 평면상의 다각형으로 모델링할 때 NP-hard임을 보인다. 문헌의 다른 문제들을 일반화하는 최소 장애물 변위 문제의 정확한 공식화와 이에 대응하는 최적해 외에, 본 논문은 계산 부담이 더 적은 근사해를 제안하며, 이는 최적해와 최적 비용의 일부만큼만 차이 나며, 경로 길이와 장애물 변위량 사이의 트레이드오프를 조절할 수 있다.

arXiv:2607.23316v2cs.NE공통 태그 Scheduling, Combinatorial Optimization

학생 학습 자원 배분을 위한 유전 알고리즘

A genetic algorithm for student academic resource allocation

개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.

arXiv:2610.03316v2cs.AI공통 태그 Scheduling, Combinatorial Optimization

LLM을 활용한 제로샷 교차 문제 일반화를 위한 다중 작업 진화

Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

다양한 조합 최적화(combinatorial optimization) 문제를 위한 효과적인 휴리스틱(heuristic)을 설계하는 것은 상당한 전문성과 반복적인 탐색을 필요로 합니다. 대규모 언어 모델(LLM)은 휴리스틱 생성과 개선을 자동화하지만, 휴리스틱 탐색은 일반적으로 최적화 대상 문제의 평가 피드백에 의존합니다. 따라서 소스 작업 피드백만을 사용하여 새로운 문제 정의로 일반화하는 것은 여전히 핵심적인 과제로 남아 있습니다. 본 논문에서는 제로샷(zero-shot) 교차 문제 일반화를 위한 LLM 기반 다중 작업 진화 프레임워크인 MECo를 소개합니다. MECo는 작업 조건부 휴리스틱 개체군을 유지하며, 교차 작업 개체군 성능에 기반한 전이 격차(transfer gap)를 활용해 이들의 상호작용을 유도합니다. 이러한 상호작용은 휴리스틱의 전이와 재조합을 가능하게 합니다. 그런 다음 상호보완적 선택 기준을 통해 각 개체가 소스 조합에 대해 제공하는 추가적인 커버리지를 보상함으로써 간결한 휴리스틱 세트를 구성합니다. 선택된 세트는 추가적인 탐색이나 적응 과정 없이 타깃 문제에 바로 적용됩니다. 차량 경로 문제(VRP) 및 유연한 잡숍 스케줄링(FJSP) 전반에 걸친 32가지 변형 문제를 대상으로 한 실험에서, MECo는 동일한 예산 하에 8개의 자동화된 휴리스틱 설계(AHD) 기준선과 비교해 가장 낮은 평균 비용을 달성함을 보여줍니다. 도메인 외(OOD) 문제에서도 각 제품군에서 가장 강력한 기준선을 능가합니다. 나아가 MECo 프레임워크를 서로 다른 AHD 방법들과 통합했을 때 두 제품군 모두에서 ID 및 OOD 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.

arXiv:2609.35965v2cs.CV공통 태그 Navigate, Scheduling

체계적 다중 에이전트 비전-언어 내비게이션: 공식화, 벤치마크 및 방법론

Systematic Multi-Agent Vision-and-Language Navigation: Formulation, Benchmark, and Method

비전-언어 내비게이션(VLN)은 주로 단일 에이전트가 단일 지시를 따르는 데 초점을 맞추어 왔으나, 많은 실제 응용 분야에서는 개별 에이전트의 역량을 넘어서는 작업을 해결하기 위해 로봇 팀을 필요로 합니다. 본 연구에서는 체계적 다중 에이전트 비전-언어 내비게이션을 제시하며, 우리가 아는 한 다중 에이전트 VLN을 제약 조건이 있는 협업 문제로 최초 체계적으로 공식화합니다. 각 임무는 의존성 및 자원 제약(존재 잠금 및 유지 체인)을 수반하는 하위 작업으로 구성됩니다. 검증된 4단계 제작 파이프라인을 통해 세 가지 지시 체제 하에서 최대 4개의 에이전트로 구성된 팀과 함께 145개 장면에 걸친 11,724개 에피소드로 이루어진 MAVLN으로 작업을 인스턴스화하고, 맞춤형 제약 인식 지표를 함께 제공합니다. 나아가 대규모 언어 모델(LLM) 기반 하위 작업 스케줄러, 각 에이전트의 탐험을 팀 지식으로 전환하는 공유 위상학적 메모리, 그리고 동시 의도를 충돌 없는 경로로 구현하는 충돌 인식 실행 메커니즘을 결합한 협업 지원 내비게이션 시스템인 TRISS를 제시합니다. 광범위한 실험을 통해 TRISS가 포괄적인 기준선임을 입증하며, 스케줄링, 계획, 실행 전반에 걸쳐 상당한 개선 여지가 있음을 밝혀 MAVLN 작업 제약 하에서의 협업 과제를 부각합니다. 프로젝트 페이지: https://xyz9911.github.io/mavln.

arXiv:2609.39360v2cs.AI공통 태그 Combinatorial Optimization, mixed-integer programming

혼합 정수 선형 및 비선형 프로그래밍에서의 자동 연구

Autoresearch in Mixed-Integer Linear and Nonlinear Programming

자동 연구(autoresearch)의 최근 발전에도 불구하고, 전형적으로 NP-난해(NP-hard) 혼합 정수 선형 또는 비선형 프로그램(MILP 또는 MINLP)으로 공식화되는 실제 운영 연구(operations research) 문제에 이를 적용하는 것은 여전히 어렵습니다. 효과적인 연구를 위해서는 상충하는 아이디어들과 장기적(long-horizon) 실험 궤적을 체계적으로 관리해야 하기 때문입니다. 본 논문에서는 아이디어 풀링(pooling)과 알고리즘 트리 탐색을 통해 혼합 정수 프로그래밍에서 장기적 자동 연구를 체계화하는 재사용 가능한 에이전트(agent) 스킬인 AutoMIP을 소개합니다. AutoMIP은 상호보완적인 후보 아이디어들의 지속적인 풀을 유지하는 동시에 실행 가능한 실험들을 알고리즘 트리로 구성하여, 에이전트가 탐색되지 않은 가설을 보존하고 유망한 알고리즘을 개선하며 과거 상태를 기반으로 대안적 방법론 방향으로 전환할 수 있도록 지원합니다. MILP 및 MINLP 벤치마크(benchmark) 코호트에서 AutoMIP은 평가된 자동 연구 프레임워크 중 가장 높은 최종 성공률을 달성했습니다. MIPLib에서 AutoMIP은 60개 인스턴스 중 31개에서 새로운 최적해를 발견하여 기존 자동 연구 프레임워크를 능가했습니다. MINLPLib에서는 60개 인스턴스 중 52개에서 새로운 최적해를 달성했습니다. 절제 연구(ablation study)는 아이디어 풀링과 알고리즘 트리 탐색의 상호보완적 기여를 추가로 입증하며, 장기적 자동 연구를 위해 다양한 연구 아이디어와 구조화된 실험 궤적을 함께 유지하는 것의 중요성을 강조합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.