Rsimulator

github에서 Rsimulator 보기

Rsimulator 소개

 Rsimulator는 Visual studio 2010, C++, opencv 기반으로 만들어진 이동 로봇 시뮬레이터입니다.

라이센스

 Rsimulator는 GPL을 따릅니다.(GPL 한글 번역 전문)

 기업, 학교, 개인이 마음대로 개작하고 재배포해도 좋지만, 개작된 소프트웨어의 소스코드는 GPL에 따라 공개되어야 하고 Rsimluator를 사용했다는 것을 밝혀야 합니다.. Rsimulator를 공공의 목적으로 공개하는 이유이기도 합니다.

기능 명세

• 로봇 설정(두 개의 바퀴와 하나의 캐스터)
• 장애물 환경 디자인(사각형, 원형, 직선 등)
• 초음파, 레이저 센서 스캔 시뮬레이션
• 점유 격자 지도 작성 시뮬레이션
• 전역 경로 계획 시뮬레이션
• 지역 경로 계획 시뮬레이션
• UKF SLAM 시뮬레이션

소스 다운로드 방법

 git에 대해 익숙하신 분은 본 글 상단의 링크를 참고하시면 됩니다.

 처음이신 분은 본 글 상단의 링크를 통해 Rsimulator git을 fork하고

 github for windows를 통해 clone을 받으시면 됩니다.

간단 사용 방법

 처음 화면에 몇 개의 원이 뿌려져 있습니다. 랜덤하게 생성된 35의 점(랜드마크 입니다.) r 키로 적당한 크기의 로봇의 생성시키고 space bar를 누르면 정해진 궤적을 따라가면서 SLAM을 수행합니다.

 왼쪽 메뉴의 DT, VFF, VFH를 선택하면 로봇이 다르게 반응합니다. 자세한 설명서는 시간이 허락하면 작성할 계획입니다.

시뮬레이터 개선 계획

  현재는 없습니다. 다만, 본 프로그램을 사용하시는 분이 좋은 아이디어를 바탕으로 개선한 내용을 github에 pull하고 싶으시다면 적극 환영합니다. 공동으로 작업하고 싶은 의향도 있습니다. 그것이 공중 소프트웨어의 본질이라고 생각합니다.

시뮬레이터 실행 화면

Dijkstra, Best First Search, A* search

Dijkstra, Best First Search, A* search

전역 경로 계획

 거창하게 전역 경로 계획(Global path planning)이라고 이름을 붙이기는 했지만, 지역 경로 계획에 대비되는 용어일 뿐이다.

 지역 경로 계획은 가까운 곳의 장애물을 회피하기 위한 방법이라면 전역 경로 계획은 출발점에서 도착점까지 가장 가까운 거리를 찾는 것을 목적으로 한다. 그러므로 전역 경로 계획으로 생성된 경로에서 지역적으로 발생하는 장애물을 회피하는 방법을 복합적으로 사용하는 것이 바람직하다. 전역 경로 계획은 컴퓨터 공학 그래프 이론에서 출발한 것들이기 때문에 지역 경로 계획과는 근본적으로 조금 다른 성향을 가진다.
 실상이 없는 노드와 에지의 연결체에서 최단 경로를 찾는 것은 로봇의 모션 플래닝의 관점과는 조금 맞지 않을 수도 있다.

 이외에도 다른 방법들이 많이 있지만 다음 세가지에 국한해서 예시를 든다.

• Dijkstra
• Best First Search
• A* Search

 워낙 오래되고 많이 사용되는 방법들이기 때문에 특별히 많은 설명이 필요하지는 않을 것 같다. 다음그림으로 세 가지 방법의 차이점을 명확히 이해할 수 있다.

Dijkstra, BFS, A* 비교(왼쪽부터)

 Occupancy grid와 같은 평면 지도를 작성했다면 위의 그림처럼 경로 계획을 하는 것이 적합한 것임을 이해할 수 있다. 각 셀을 노드로 셀간의 연결(4개 또는 8개)을 에지로 생각하면 그래프와 같기 때문이다.

 Dijkstra에서는 인접 셀에 거리 측정 방법(Manhattan distance, Euclidean distance)으로 측정된 비용에 따라 도착점 까지의 비용이 산출된다. 각 인접셀에 도달하는 비용은 동일하기 때문에 도착점까지의 가능한 모든 경로에 대해서 비용을 산출한 뒤에야 최단 경로가 생성되지만 최단 거리를 보장해준다는 장점이 있다.

 BFS에서는 도착점까지의 거리가 가장 가까운 지점을 먼저 방문한다. Dijkstra보다 빠르지만 그림에서 보는 것처럼 최단경로를 찾지 못할 수 도 있다는 단점이 있다.

 A* search algorithm은 상기 두 가지 방법을 적절히 혼용한 것으로 볼 수 있다. 출발점으로 부터 인접셀의 비용을 계산하되 도착점까지의 거리가 적을 것으로 생각되는 지점을 먼저 계산한다. 아래 그림에서 경로를 계산하는 순서를 확인할 수 있다.

 게시물 작성중에 최근에 새로운 것이 있는지 확인해본 결과 흥미로운 것을 발견했다. 기존의 Dijkstra's algorithm을 GPGPU를 이용해서 비약적으로 성능을 확장시킨 것이다. 가능한 인접셀을 모두 병렬로 방문함으로써 반복의 횟수를 절감했다.