본문 바로가기

전체 글

다익스트라(Dijkstra) 알고리즘으로 로봇의 최단경로 계산 이전 글 "세선화 결과로부터 위상지도(topology map) 만들기에서 격자지도로부터 위상지도를 만들었습니다. 이제 위상지도에서 로봇의 출발지와 목적지가 정해지면 최적의 주행경로를 계산하는 방법 중 하나인 Dijkstra 알고리즘을 구현해 보겠습니다. Dijkstra 알고리즘에 대해서는 위키피디아 페이지를 참고하십시오: http://en.wikipedia.org/wiki/Dijkstra's_algorithm 아래는 구현된 소스코드입니다. 프로그램의 실행 결과는 다음과 같습니다. 더보기
세선화 결과로부터 위상지도(topology map) 만들기 아래 글에서 경로를 만들기 위한 기본 과정으로 격자 지도로부터 세선화 알고리즘을 수행하여 경로의 골격을 추출하였습니다. 경로 추출을 위한 Vornoi 세선화 알고리즘 - 경로 추출을 위한 세선화(thinning) 알고리즘 - 이제 이 경로의 골격과 위상이 일치하는 Topology Map을 만들도록 하겠습니다. 만드는 과정은 다음과 같습니다. 1) 격자 지도에서 로봇이 주행 가능한 영역을 세선화 하여 경로의 골격을 추출한다. 2) 경로의 골격 선이 끝나거나 여러 선들로 갈라져 나가는 부분을 노드로 찾는다. 즉, 현재 픽셀 주변에서 주변 픽셀을 카운트 했을 때 1개, 3개, 4개의 선이 연결되어 있으면 이 점은 분기 노드(branch node)로 고려한다. 2-1) 분기 노드로부터 선을 이루는 픽셀을 따라가.. 더보기
VFH(Vector Field Histogram)+ 알고리즘 VFH에 로봇이 동역학적으로 회전할 수 있는 회전반경을 고려하여 VFH+가 만들어졌습니다. 자세한 내용은 아래 문서를 참조하시기 바랍니다. 다음 예제코드를 실행해 보시기 바랍니다. 이 예제코드는 Robot Simulation Server가 필요합니다. 이에 관련된 글을 참조하시어 시뮬레이터를 먼저 실행한 후 VFH+_client 프로그램을 실행하십시오. 다음은 VFH+ 알고리즘이 실행되는 동영상입니다. 더보기
VFF(Virtual Force Field) 알고리즘 로봇의 장애물 회피 기법 중 하나인 VFF(Virtual Force Field) 알고리즘은 로봇 주변의 장애물들로부터 로봇에 작용하는 가상의 반발력을 만들어 장애물이 로봇을 밀어내고 목적지에서는 로봇을 끌어당기는 인력을 이용하여 로봇이 장애물에 충돌하지 않고 목적지로 이동하도록 하는 장애물 회피 방법입니다. VFF 알고리즘을 요약하자면 다음과 같습니다. (참조: http://www-personal.umich.edu/~johannb/vff&vfh.htm) 1. 포텐셜 필드 개념을 가진 히스토그램 격자를 전역 지도로 사용한다. 2. 로봇을 따라 움직이는 가상의 윈도우를 설정하고, 가상의 윈도우와 겹치는 히스토그램 격자영역을 활성화 윈도우라고 한다. 3. 활성화 윈도우 내의 셀들은 로봇을 향한 반발력을 생성한.. 더보기
Bug1, Bug2, Tangent Bug 알고리즘 (Choset H.M.의 책 Principles of robot motion: theory, algorithms, and implementation 참조, Siegwart의 책 Introduction to Autonomous Mobile Robots 참조) Bug1 Algorithm Bug1 알고리즘은 Bug 알고리즘 중 가장 단순한 알고리즘이다. 알고리즘은 다음과 같이 동작한다. 1) 목표위치를 항해 전진한다. 2) 목표위치에 도달하면 종료. 3) 장애물을 만나면 장애물의 외곽을 따라 움직인다. 3-1) 움직이는 동안 현재위치와 목표위치의 거리를 계산한다. 3-2) 현재위치와 목표위치의 최소 거리가 되는 위치를 기억한다. 4) 장애물을 한 바퀴 돌아 장애물을 처음 만난 위치로 돌아오면 최소 거리가 되는.. 더보기
이동로봇의 Trajectory Tracking Trajectory Tracking이란 로봇이 경로상에 있거나 있지 않은 위치로부터 로봇의 경로를 점근적으로 따라가도록 제어하는 방법을 말합니다. 여기서는 다음 3가지 방법에 대하여 소개합니다. Approximate linearization Nonlinear control Input/output linearization 자세한 내용은 아래 파일을 참조하시기 바랍니다. 아래는 3가지 방법에 대한 예제 코드와 프로그램의 실행 동영상입니다. Approximate linearization Nonlinear control Input/output linearization 더보기
이동로봇의 Motion Control 로봇의 경로가 주어지지 않은 상황에서 로봇이 목적지로 이동하고자 할 때, 목적지와 로봇의 현재 위치간의 오차로부터 로봇의 전진속도와 각속도를 계산하게 됩니다. 다음 문서는 이러한 상황에서 3가지 방법을 제시합니다. 1. Cartesian regulation: 로봇이 목적지에 도달하였을 때 로봇의 방향이 중요하지 않은 경우입니다. 즉, 로봇이 여러 경유점을 지나면서 이동하는 경우, 경유점에서 로봇의 방향은 중요하지 않고 경유점을 지나가기만 하면 됩니다. 이 때 각각의 경유점들이 로봇의 일시적인 목적지가 될 수 있습니다. 2. Posture regulation 1: Prof. Giuseppe Oriolo의 Autonomous and Mobile Robotics 발표자료에서 참조한 내용입니다. 로봇의 위치와 .. 더보기
추측항법(Dead-reckoning): odometric localization 추측항법(Dead-reckoning)이라고 함은 GPS와 같은 로봇의 위치인식 센서에서 로봇의 위치가 들어오지 않을 때 바퀴의 이동량만으로 로봇의 위치를 추측하는 방법을 말합니다. 로봇의 미끄러짐이 없고 바퀴의 크기와 회전각 등을 정확히 알고 있다고 하면 추측항법 만으로도 정확한 로봇의 위치를 계산할 수 있겠지만, 로봇 모델링의 오차와 주변에서 발생하는 각종 에러 요소에 의해 추측 항법으로 계산한 위치에는 에러가 누적됩니다. 이를 보정하기 위해 DGPS, North Star, U-SAT와 같은 각종 위치인식 센서를 사용하여 칼만필터로 정합하는 과정을 거치게 됩니다. 여기서는 추측항법을 위한 바퀴의 이동량을 적분하는 3가지 방법에 대하여 소개합니다. 자세한 내용은 아래 문서를 참조하시기 바랍니다. 더보기

티스토리툴바