logistics13 최적 경로 찾기 #4 - 플로이드 워셜(Floyd Warshall) 알고리즘, 자바 코드 구현 포함 플로이드 워셜(Floyd Warshall) 알고리즘 플로이드 알고리즘은 로버트 플로이드(Robert W Floyd)이 발표한 알고리즘으로 버나드 로이(Bernard Roy)가 발표한 알고리즘, 스티븐 워셜(Stephen Warshall)이 발표한 알고리즘과 비슷하기 때문에 플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘 이라고도 불린다. 플로이드 알고리즘은 두 노드 사이에 존재하는 노드와의 가중치를 이용해 최소 가중치 합 경로를 구하는 알고리즘이다. 가능한 모든 경우의 수를 따지므로 시간복잡도가 크지만, 모든 노드에서 자신을 제외한 모든 노드로 가는 최소 가중치 경로를 얻을 수 있다. 플로이드 알고리즘이 다익스트라, 벨만 포드 알고리즘과의 가장 큰 차이점은 어떤 정점에서든지 최단 경로를 .. 2023. 7. 3. 최적 경로 찾기 #3 - 벨만-포드(Bellman-Ford) 알고리즘 벨만-포드(Bellman-Ford) 알고리즘 벨만포드 알고리즘은 리차드 벨만(Richard Bellman)과 레스터 포드(Lester Ford)에 의해서 개발되었고 그들의 이름을 따서 벨만포드라고 정해진 알고리즘이다. 벨만포드 알고리즘은 다익스트라 알고리즘과 비슷한 작동 원리를 가지지만 통행 비용에 음수값이 허용된다는 차이점이 있다. 최적 경로를 도출하기 위해 사용하는 노드의 개수가 n개라면 벨만 포드 알고리즘은 총 n-1 개의 노드에 대한 경로를 모두 탐색한다. 즉, 가장 먼 거리에 있는 노드를 제외한 모든 노드에 대한 경로를 탐색한다. 음수 값이 허용되는 이유는 다익스트라 알고리즘 사용할 때 노드의 간선의 가중치가 음수인 순환 경로가 존재할 경우 순환경로에서 벗어나지 못하고 최단 경로 탐색에 실패하게.. 2023. 7. 3. [SLAM] 몬테카를로 위치 추정(Monte Carlo Localization)이란? 몬테카를로 위치추정(MonteCarlo Localization, MCL) 몬테카를로 위치 추정(Monte Carlo Localization, 이하 MCL) 방법은 파티클 필터 기반의 위치 추정 알고리즘이다. MCL은 로봇이 위치할 가능성이 있는 모든 영역에서 로봇의 위치를 나타내는 샘플을 랜덤하게 추출하고, 각 샘플이 실제 로봇의 위치인지를 계산하는 과정을 거치게 된다. 따라서 추출한 샘플의 수는 MCL의 성능 및 수행시간과 직접적으로 연관이 있다. 샘플 수가 많으면 위치 정확도는 향상되고 위치추정 실패율은 감소되지만, 수행시간이 길어져 위치 갱신이 늦어진다. 따라서 MCL은 칼만필터 방법에 비해 수행시간이 오래 걸린다. MCL은 거리센서의 정보를 받아 위치추정 알고리즘을 이용하여 추정위치를 갱신하는 과.. 2023. 6. 27. [SLAM] 칼만 필터(Kalman Filter)란? 로봇의 각종 센서 정보를 통해 로봇의 위치를 추정하고 이동 경로 계획을 위한 SLAM을 하는 과정에서 센서를 통해 들어오는 정보에 잡음(노이즈)이 섞이는 경우가 발생한다. 이로 인해 추정된 위치 좌표가 실제 로봇의 위치와 다른 경우가 발생하는데 이러한 추정치를 보정하여 추정한 위치 좌표와 로봇의 실제 좌표와 일치시키는 알고리즘 중 하나인 칼만 필터를 소개하겠다. 칼만 필터(Kalman Filter)란? 칼만 필터는 잡음이 포함된 측정치를 바탕으로 선형 역학계의 상태를 추정하는 재귀 필터로 루돌프 칼만이 개발하였다. 칼만 필터는 물체의 측정값에 확률적인 오차가 포함되고, 또한 물체의 특정 시점에서의 상태는 이전 시점의 상태와 선형적인 관계를 가지고 있는 경우 적용이 용이하다. 또한 가우시안 분포에 효과적인.. 2023. 6. 27. 로봇공학 입문 - 자유도란? 로봇이 얼마나 자유롭게 움직일 수 있는가를 나타내는 자유도라는 개념에 대해 알아보겠다. 자유도를 이해하기 전에 공간을 나타내는 좌표계를 먼저 알아야 할 필요가 있다. 좌표계는 보통 왼손 좌표계와 오른손 좌표계를 많이 사용한다. 좌표계는 로봇공학 뿐만 아닌 그래픽 업계, 게임 업계 등 공간을 적용해야 하는 곳에서는 어디든지 사용된다. 좌표계 왼손 좌표계에서 회전 방향은 각 축에 대해 시계방향으로 회전한다. 오른손 좌표계에선 각 축에 대해 반시계방향으로 회전한다. 자유도(Degree of Freedom) 로봇공학에서 자유도는 로봇 구성에 필요한 실제 좌표의 최소 수라고 할 수 있다. 쉽게 말하면 로봇이 움직일 수 있는 경우의 최소 단위라고도 볼 수 있다. 즉. 자유도는 로봇의 위치와 자세를 결정하기 위해 필.. 2023. 6. 26. IMU센서와 센서 퓨전(Sensor Fusion) 기술 IMU 센서란? IMU(Inertial Measurement Unit) 센서란, ‘관성 측정 장치’로 신체의 힘, 각속도 또는 주변 자기장을 측정할 수 있는 전자 장치이다. IMU 센서는 보통 가속도 센서(Acceleration Sensor), 각속도 센서(Gyroscope Sensor)로 이루어진 6축 센서가 있고 지자기 센서(Magnetometer Sensor)가 추가된 9축 센서가 있다. IMU 6축 센서는 각속도 센서에 의해 3축의 움직임을 감지하고 각 축(x, y, z)의 각속도를 측정하며 가속도 센서에 의해 각 축의 가속도를 측정한다. 3축 가속도 및 각속도 자료는 장애물 및 구배, 노면상태 등 도로환경 요소별 평균 및 표준편차 등의 차이가 나타나므로 이륜차의 주행특석 분석을 위해 활용 가능한.. 2023. 6. 26. 이전 1 2 3 다음
