경로 계획 알고리즘
AMR의 회피 주행을 잘 활용할 수 있는 MAPF 알고리즘이 있을까? #2 - Velocity Obstacle
안녕하세요. 벌써 3월 중순이 가까워지고 있는데 여전히 날씨가 쌀쌀합니다 ㄷㄷ 다들 감기 조심하세요 ㅜ 이번에는 AMR의 회피 주행을 잘 활용할 수 있는 MAPF 알고리즘이 있을까? #1 에서 소개드렸던 논문들을 공부한 내용을 정리해보려고 합니다. VAN DEN BERG, Jur; LIN, Ming; MANOCHA, Dinesh. Reciprocal velocity obstacles for real-time multi-agent navigation. In: 2008 IEEE international conference on robotics and automation. Ieee, 2008. p. 1928-1935. 로봇의 지역 경로 계획(local planning)을 개선하여 충돌을 해소하는 방식인데 결과..
AMR의 회피 주행을 잘 활용할 수 있는 MAPF 알고리즘이 있을까? #1
안녕하세요. 간절기인데 무탈하신지요? 슬슬 봄이 찾아오고 있는지 온도가 영상 10도보다 높은 날들이 많아져서 무슨 옷을 입을지 애매합니다 ㅋㅋㅋ 저는 요즘 스스로 장애물을 피해 움직이는 Autonomous Mobile Robot(AMR)을 잘 활용할 수 있는 MAPF 알고리즘에 대해서 찾아보고 있습니다. MAPF 알고리즘들은 주로 Autonomous Guided Vehicle(AGV)를 대상으로 개발됩니다. MAPF 알고리즘 관점에서 AMR과 AGV의 차이를 꼽자면 AGV는 알고리즘의 결과값대로 움직이지만 AMR은 그렇지 않다는 것입니다. AMR과 AGV의 차이점이 더 궁금하시다면 트위니 블로그를 참고해주세요 :) 참고: AMR과 AGV 로봇의 차이점 (feat.쿠팡 소팅봇) AMR이 스스로 장애물을 피..
Conflict-Based Search for Explainable Multi-Agent Path Finding - Explainable MAPF가 대체 뭘까요!
안녕하세요. 이번에는 Explainable MAPF에 대해서 공부하고자 합니다. KOTTINGER, Justin; ALMAGOR, Shaull; LAHIJANIAN, Morteza. Conflict-based search for explainable multi-agent path finding. In: Proceedings of the International Conference on Automated Planning and Scheduling. 2022. p. 692-700. 제가 어떤 이유로 Explainable MAPF를 찾게 되었고, 이 논문을 읽었는지, 그리고 논문에서 어떤 것들을 배웠는지 간단히 정리해 보겠습니다. 1. 시작 - 버그 발견, 디버깅이 너무 어려워 ㅜㅠ MAPF 알고리즘을 실제로..
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses - RHCR 원조가 여기라던데!
안녕하세요. 오늘은 Lifelong MAPF 문제를 Windowed 기반의 접근법으로 해결하는 방법을 연구한 Lifelong Multi-Agent Path Finding in Large-Scale Warehouse 논문을 공부하려고 합니다.LI, Jiaoyang, et al. Lifelong multi-agent path finding in large-scale warehouses. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2021. p. 11272-11281. 물류센터 환경에서 가장 좋은 MAPF 모델은 뭘까요? 에서 사용되었던 Rolling Horizon Collision Resolution(RHCR)이 바로 이 논문에서 ..
우리나라 대기업 LG전자에서 MAPF를 연구한다면 어떨까요? - MAPF 제대로 연구하려면 로봇이랑 물류센터는 있어야 한다니깐요!
안녕하세요. 오늘은 무려 LG 전자에서 진행된 MAPF 연구를 공부해보려고 합니다.신동철, et al. 다중에이전트 경로탐색 (MAPF) 기반의 실내배송로봇 군집제어 구현. 로봇학회 논문지, 2022, 17.4: 407-416.로봇도 있고, 물류센터도 있으니 MAPF 연구를 진행하는데 필요한 핵심적인 것들이 전부 갖춰진 환경인 것 같더라고요...! 같이 한번 봐볼까요?1. Introduction1.1. 로봇의 실제 동작과 경로 계획 사이의 갭을 줄이기 위해 노력한 연구들기존 MAPF 연구들은 이론상 충돌 없는 경로를 계획할 수는 있지만 실제 로봇이 이를 정확하게 실행할 수 없다는 문제가 있습니다. 이를 보완하기 위해 로봇의 동역학적인 모델을 도입하여 경로를 보다 정확하게 계획하는 연구들이 있었지만 이들 ..
Conflict-Based Search with Optimal Task Assignment - 작업 배정과 경로 계획을 동시에 한다면?
안녕하세요. 오늘은 작업 배정과 다중 에이전트 경로 계획을 합쳐서 효율성을 높인 방법을 제안한 Conflict-Based Search with Optimal Task Assignment 논문을 공부해보도록 하겠습니다. HÖNIG, Wolfgang, et al. Conflict-based search with optimal task assignment. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018. 일반적으로 작업 배정과 다중 에이전트 경로 계획은 다른 단계에서 이뤄졌는데요. 이렇게 문제를 분해한 결과, Lifelong MAPF 문제를 빠르게 풀 수 있지만 어쩌면 있..