큰 맵에 적용가능한 확장된 BSA 커버리지 알고리즘 (Extended BSA Coverage Algorithm for Large Unknown Map)

서지정보

· 발행기관 : 한국지능시스템학회
· 수록지 정보 : 한국지능시스템학회 논문지 / 27권 / 5호 / 408 ~ 419페이지
· 저자명 : 미마오 쉬, 이현순, 강보영

초록

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

영어초록

In this paper we propose an extended BSA (Backtracking Spiral Algorithm) which uses coverage path planning method for mapdecomposition of large unknown maps. The existing spiral path planning method divides the entire map into grids by the size of the cleaning robot and stores the grid information which is then used to generate the cleaning path. The main disadvantage of this existing method is that when the size of map increases the grid information necessary to complete the cleaning path generation also increases which is less efficient. The proposed method thus overcomes the disadvantages of existing method by effectively controlling the size of map to form a contracted map and by using A* method for map-decomposition. As the proposed method can effectively control the number of grid it not only overcomes the disadvantages of the existing spiral path planning method but also maintains the advantages of using BSA in the decomposed map. Through a series of experiments it was found that the proposed method can effectively apply the coverage path planning in large unknown maps and improve the performance of the existing BSA method

참고자료

· 없음