A* 알고리즘 초기 설계(2021.07.25.)

최단경로 찾기 및 장애물 피하기

1. 위치한 지점에서 8방위 선정

2. 8방위 점 중 장애물/벽 좌표와 위치가 같거나 안전범위에 겹침 → 4번 / 겹치지 않음 → 3번
   2-1. LiDAR에서 인식한 Circle 장애물 : (갈 지점과 장애물 중심점 사이 거리) > (장애물 반지름 + 안전거리) 일 때만 필터링
   2-2. LiDar에서 인식한 Wall 장애물 : min(갈 지점과 start점 사이 거리, 갈 지점과 end 점 사이 거리, 벽 중심까지 거리) > (안전거리) 일 때만 필터링
   2-3. 경계선 : 직선의 방정식 넘어갔나 넘어가지 않았나 판단

3. f = g + h 값을 계산했을 때 최소 f값임 → 5번 / 최소 f값이 아님 → 4번
   3-1. g = (시작점에서부터 지나온 거리) + (지금 이동할 값) , 시작점부터 거리는 전체 클래스에서 누적된 값, 지금 이동할 값에는 heading을 틀어야 하는 각도 범위에 따라 가중치 부여

   (Q) heading 따라 가중치 주려면 배가 그 자리에 있어야 하는데 미리 경로를 짜 두는 알고리즘 특성과 위배됨
   (S) predicted_bearing을 써서 배가 돌아가는 각도를 누적시킬까?

   3-2. h = (지금 이동할 위치로부터 목적지까지 거리)

   (Q) f 계산 시에는 [g, h, bearing]으로 전달하고 trajectory에는 [x, y, bearing]으로 전달해야 할까?

4. 갈 수 있거나 최적 지점이 아니므로 메모리 해제

   (Q) 메모리 해제시키면 이미 탐색했던 곳을 또 탐색하게 됨
   (S) 어차피 heading이 달라져서 g 값도 달라지나?

5. 갈 위치를 trajectory에 저장 → 1번 다시 수행

   (Q) 탐색 속도와 배가 실제로 이동하며 장애물을 탐지하는 속도가 차이 날 경우? 이미 알고리즘은 장애물 없다 치고 경로 짜 놓고 그리로 가라고 했는데 실제 가 보니 그 자리에 장애물을 탐지하면?
   (S) 탐색을 갱신하는 rate를 설정해 경로를 다시 짜거나 미리 경로를 잡아놓을 칸 수를 제한하기?

장애물 탐색

1. 라이다를 이용해 장애물 위치 잡아 좌표 변환
2. 전체 장애물 목록에 추가

(Q) 이미 지나온 부분에 있는 장애물이라면 삭제?
(Q) 장애물 너무 많아지면 g 검사에서 과하게 메모리 먹지 않을까?

실제 이동

1. trajectory 다음 위치로 이동했을 때 bearing과 좌표 고려해 그 다음 배열 위치로 servo, thruster에 Publish

(Q) 직진이나 작은 각도로 갈 때는 속도를 높일까?

Map 구성

상대 좌표로의 변환

1. map의 각 꼭짓점의 GPS 좌표를 따옴

2. 한 점을 원점(0, 0)으로 하고 진북방향을 y축, 진북과 수직이면서 원점을 지나는 축을 x축이라 함

   (Q) 눈금의 스케일은?
   (S) 조정 가능 파라미터로 두되, 배의 크기 등을 고려해 최소 범위 두기

   (Q) 좌표가 직사각형이 아니면?
   (S) GPS 좌표가 3개 이상이기만 하면 만들 수 있게 하자

3. 나머지 점들도 좌표 상에 나타냄

   (Q) 이건 어떻게 처리할 건가?
   (S) 진북과 원점 이용한 사잇각+거리? 정수가 아니면 어떻게 처리?

4. 각 점들을 잇는 직선의 방정식 만들어 벽을 경로 탐색 알고리즘에 전달

   (Q) 탐색 8방위 점에 벽이 있는지 어떻게 알지?
   (S) 직선 밖/안으로 판단 & 직선에 해당하는 점

좌표 위 점 설정

(Q) 딱 좌표 위가 아닌 경우 어떻게 처리?(실수 꼴)
(S) 배열에 좌표 위치를 넣을 것이니 괜찮음

(Q) 변환 시 출발 지점이 경기장 벽 밖에 있다면?

1. 배가 있는 지점(출발 포함)을 GPS에서 상대좌표로 실시간 변환 해줘야 함
2. 도착 지점은 GPS 좌표 찍고 상대좌표로 변환

   (Q) 도착 ‘범위’로 지정하기?!

Simulator

1. 조정 가능 파라미터 :
   배 너비 및 길이 / 안전거리 / 장애물 위치 및 크기 / 벽 좌표(GPS) / 시작 좌표(GPS) / 경로 탐색 속도 또는 step / 목표점 또는 목표범위 / 눈금 스케일 등

2. 표시할 것 :
   heading 방향 / 눈금 / 지나온 trajectory / 현재 탐색중인 trajectory / 경과 시간 등

3. 장애물은 random 시간마다 random한 크기와 종류의 장애물을 실시간으로 생성

   (Q) heading 뒤쪽으로는 생성하지 말까?

(Q) 호핑 투어 용으로도 만들자. waypoint GPS 좌표 넣어서!

Source Code

GitHub(실시간 업데이트) : AutonomousShipAlgorithm/A_star