[논문]Min-Max Tours and Paths for Task Allocation to Heterogeneous Agents

Prasad, Amritha; Choi, Han-Lim; Sundaram, Shreyas

doi:10.1109/tcns.2020.2983791

[해외논문] Min-Max Tours and Paths for Task Allocation to Heterogeneous Agents 원문보기

IEEE transactions on control of network systems, v.7 no.3, 2020년, pp.1511 - 1522

Prasad, Amritha (School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA) , Choi, Han-Lim (Department of Aerospace Engineering, Korea Advanced Institute of Science and Technology, Daejeon, South Korea) , Sundaram, Shreyas (School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN, USA)

Abstract ▼ AI-Helper

We consider a scenario consisting of a set of heterogeneous mobile agents and a set of tasks dispersed over a geographic area. The agents are partitioned into different types. The tasks are partitioned into specialized tasks that can only be done by agents of a certain type, and generic tasks that can be done by any agent. Given this scenario, we address the problem of allocating these tasks among the available agents (subject to type compatibility constraints) while minimizing the maximum travel cost for any agent. We first look at the heterogeneous agent cycle problem where agents start at a common depot and need to tour the set of tasks allocated to them before returning to the depot. We provide a 5-approximation algorithm to solve this problem, regardless of the total number of agents and the number of agents of each type. We then consider the heterogeneous agent path problem (HAPP) where agents can start from arbitrary locations and are not constrained to return to their start location. We consider two approaches to solve HAPP. The first approach yields a 15-approximation factor, while the second yields a factor of 16.

참고문헌 (35)

10.2307/2033241
10.1017/CBO9780511804441
10.1007/978-3-319-16595-0_36
10.1007/978-3-319-62389-4_45
Lenstra, Jan Karel, Shmoys, David B., Tardos, Éva. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming, vol.46, no.1, 259-271.

상세보기
Prim, R. C.. Shortest Connection Networks And Some Generalizations. The Bell System technical journal, vol.36, no.6, 1389-1401.

상세보기
Bektas, Tolga. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, vol.34, no.3, 209-219.

상세보기
Xu, Zhou, Rodrigues, Brian. A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots. INFORMS journal on computing, vol.27, no.4, 636-645.

상세보기
Malik, W., Rathinam, S., Darbha, S.. An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem. Operations research letters : a journal of the Operations Research Society of America, vol.35, no.6, 747-753.

상세보기
10.1137/1.9781611973594
Yadlapalli, Sai, Rathinam, Sivakumar, Darbha, Swaroop. 3-Approximation algorithm for a two depot, heterogeneous traveling salesman problem. Optimization letters, vol.6, no.1, 141-152.

상세보기
Bae, Jungyun, Rathinam, Sivakumar. A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem. Optimization letters, vol.10, no.6, 1269-1285.

상세보기
10.1109/SFCS.1976.6
10.1007/978-3-319-21398-9_12
Even, G., Garg, N., Könemann, J., Ravi, R., Sinha, A.. Min–max tree covers of graphs. Operations research letters : a journal of the Operations Research Society of America, vol.32, no.4, 309-315.

상세보기
Arkin, Esther M., Hassin, Refael, Levin, Asaf. Approximations for minimum and min-max vehicle routing problems. Journal of algorithms, vol.59, no.1, 1-18.

상세보기
DTIC Document Worst-case analysis of a new heuristic for the travelling salesman problem christofides 1976
Sadeghi, Armin, Smith, Stephen L.. Heterogeneous Task Allocation and Sequencing via Decentralized Large Neighborhood Search. Unmanned systems, vol.5, no.2, 79-95.

상세보기
Papadimitriou, C.H.. The Euclidean travelling salesman problem is NP-complete. Theoretical computer science, vol.4, no.3, 237-244.

상세보기
10.2514/6.2009-5776
10.14311/APP.2016.56.0067
Laporte, G.. The traveling salesman problem: An overview of exact and approximate algorithms. European journal of operational research, vol.59, no.2, 231-247.

상세보기
Bullo, Francesco, Frazzoli, Emilio, Pavone, Marco, Savla, Ketan, Smith, Stephen L.. Dynamic Vehicle Routing for Robotic Systems. Proceedings of the IEEE, vol.99, no.9, 1482-1504.

상세보기
10.2514/6.2007-2788
10.1109/ROBOT.2006.1641771
Han-Lim Choi, Brunet, L., How, J.P.. Consensus-Based Decentralized Auctions for Robust Task Allocation. IEEE transactions on robotics : a publication of the IEEE Robotics and Automation Society, vol.25, no.4, 912-926.

상세보기
Autonomous systems innovation summit final report 2008
10.1109/ICUAS.2015.7152311
Khani, M. Reza, Salavatipour, Mohammad R.. Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems. Algorithmica, vol.69, no.2, 443-460.

상세보기
Zhang, Kai, Collins Jr., Emmanuel G., Shi, Dongqing. Centralized and distributed task allocation in multi-robot teams via a stochastic clustering auction. ACM transactions on autonomous and adaptive systems, vol.7, no.2, 1-22.

상세보기
NAGAMOCHI, H.. Approximating the Minmax Rooted-Subtree Cover Problem. IEICE transactions on fundamentals of electronics, communications and computer sciences, vol.ea88, no.5, 1335-1338.

상세보기
Mathew, Neil, Smith, Stephen L., Waslander, Steven L.. Planning Paths for Package Delivery in Heterogeneous Multirobot Teams. IEEE transactions on automation science and engineering, vol.12, no.4, 1298-1308.

상세보기
Wang, Liang, Yu, Zhiwen, Han, Qi, Guo, Bin, Xiong, Haoyi. Multi-Objective Optimization Based Allocation of Heterogeneous Spatial Crowdsourcing Tasks. IEEE transactions on mobile computing, vol.17, no.7, 1637-1650.

상세보기
10.1109/CDC.2018.8619118
Gerkey, Brian P., Matarić, Maja J.. A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems. The International journal of robotics research, vol.23, no.9, 939-954.

상세보기

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

원문 보기

AccessON 원문보기

원문 URL 링크

DOI : 10.1109/TCNS.2020.2983791
IEEE : 저널 > 논문
AccessON : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

오픈액세스(OA) 유형

BRONZE

출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증