Extended BSA Coverage Algorithm for Large Unknown Map
Miao Xu, Hyun-Soon Lee, Bo‐Yeong Kang · Journal of Korean institute of intelligent systems · 2017
본 논문에서는 청소 로봇이 미지의 큰 맵에 대해 맵-분해를 적용할 수 있는 확장된 BSA(backtracking spiral algorithm) 커버리지 경로계획(coverage path planning)을 제안한다. 기존의 나선형 경로에 기반한 방법은 전체 맵을 로봇의 크기만큼 나누고 각 격자에서 맵 정보를 기록한 격자들을 통해서 청소 맵에 대한 커버리지 경로계획을 구현할 수 있지만 격자 수량이 많을수록 알고리즘의 성능이 떨어지는 단점이 존재한다. 제안한 방법은 큰 맵에서 맵 축소 및 A* 탐색 기법을 이용하여 맵을 분해하고 맵의 크기 조절을 통해서 격자의 수량을 효율적으로 제어할 수 있기 때문에 기존의 방법의 단점을 극복할 수 있을 뿐만 아니라 분해된 작은 맵에서 기존의 BSA기법을 사용하여 나선형 경로에 기반한 커버리지 경로계획의 장점도 유지할 수 있다. 일련의 실험을 통하여 제안된 방법은 미지의 큰 맵에서 커버리지 경로계획을 보다 효과적으로 적용이 가능하였고, 기존의 BSA 기법의 성능을 효율적으로 개선할 수 있었다.