2022.10.05.(수) 공부 내용 - A* 알고리즘

 

# 정리해야하는 알고리즘

A*
Pure Pursuit
VFH(Vector Field Histogram)
Potential Field
Visibility Graph
Voronoi Diagram
PRM(Probabilistic Roadmap Method)
RRT(Rapidly-exploring Random Tree)

[Book] Introduction to Autonomous Robots

4. Path Planning

이 챕터의 목표는 아래 3가지이다.

• 적절한 맵 표현(representations)을 소개한다.
• 기본적인 path-planning 알고리즘(Dijkstra, A*, D*, RRT)을 설명한다.
• coverage path planning(커버리지 경로 계획)과 같은 path-planning 문제의 변형들을 소개한다.

4.1. Map representations

- Discrete approximation

incidence matrix / list (인접 행렬/리스트)

- Continuous approximation

[?] A continuous approximation requires the definition of inner (obstacles) and outer boundaries, typically in the form of a polygon, whereas paths can be encoded as sequences of points defined by real numbers.

 

"Despite the memory advantages of a continuous representation, discrete maps are the dominant representation in robotics."

 

- Combination of discrete and continuous representation

 

* Grid map

For mapping obstacles, the most common map is the occupancy grid map.

Disadvantages of grid maps are their large memory requirements as well as computational time to traverse data structures with large numbers of vertices.

--> solution: K-d tree

The pieces can easily be stored in a graph with each vertex having four children, which are the four pieces the vertex is broken into, or is a leaf of the tree.

 

장애물이 포함된 영역의 경우 더 많이 쪼개져야한다..? 그러나 일반적으로 가능한 가장 작은 크기까지 쪼갤 필요는 없다는 것이 이 데이터 구조의 매력적인 포인트이다..?

 

quadtree (쿼드 트리, 사분 트리)

 자료구조의 트리를 기반으로 각 내부 노드에 자식 노드가 4개인 트리 데이터 구조를 의미한다. 3D 데이터를 표현하기 위한 자료구조를 '장면 그래프(Scene graph)'라고 부르는데, 이도 역시 그에 포함된다.

 

query(쿼리) 

데이터베이스에게 특정한 데이터를 보여달라고 클라이언트(사용자)가 요청하는 것.

e.g. 내가 구글에 '파이썬'을 검색하는 것이 '파이썬'에 대한 데이터를 달라고 쿼리를 주는 것이며, 서버가 이에 응답하여 데이터베이스에서 데이터를 보여주게 된다. 이때 사용자에게는 '파이썬'에 대한 검색 결과가 보여지게 되는 것이다.

  --> "쿼리문을 작성한다." : '데이터베이스에서 원하는 정보를 가져오는 코드를 작성한다.'

따라서 쿼리문을 잘 작성한다는 것은 데이터베이스에서 필요한 데이터에 빠르게 접근하고, 데이터를 능숙하게 핸들링한다는 말로도 볼 수 있다.

 

 

- coverage path planning (커버리지 경로 계획 문제)

- topological map : 중요한 정보만 남겨 단순화한 다이어그램 유형의 맵

- traverse data structure : 횡단 데이터 구조

 

"No Silver Bullet ( No Magic Bullet)."

"한 번에 완벽한 해결책은 없다."

 

k-d tree (K-dimension tree) 

k차원 공간의 점들을 구조화하는 공간 분할 자료 구조. k = 4이면 quadtree인가?

 

4.2. Path-Planning Algorithms

data packet

 데이터를 전송할 때 송신측과 수신측에 하나의 단위가 되어 전송되는 집합체 의미.

즉 우리가 인터넷을 이용해 주고받는 다양한 데이터의 내용을 작은 단위로 쪼갠 데이터로 이해하면 된다.

(패킷은 헤더, 데이터, 테일러로 이루어진다.)

4.2.1. Robot embodiment

In order to deal with the physical embodiment of the robot, which complicates the path-planning process, the robot is reduced to a point-mass and all the obstacles in the environment are grown by half of the longest extension of the robot from its center. This representation is known as configuration space as it reduces the representation of the robot to its x and y coordinates in the plane.

 

- representation of robot : 그냥 딱 로봇의 상태 (위치,  rotation)에 대해 설명하는 coordinates 같은 개념..?

- point-mass : '질점', 물체의 질량중심에 그 물체의 모든 질량이 모인 것으로 볼 때,  이 질량 중심에 해당하는 공간상의 점.

 

4.2.3.  A*

• A* 알고리즘은 가장 적은 비용으로 두 지점 사이의 최적의 경로를 찾는 데 사용되는 경로 탐색 알고리즘이다.
• 시작 노드만을 지정해 다른 모든 노드에 대한 최단 경로를 파악하는 다익스트라(Dijkstra) 알고리즘과 다르게, 시작 노드와 목적지 노드를 분명하게 지정해 이 두 노드 간의 최단 경로를 파악할 수 있다.
• 휴리스틱(heuristic) 추정값을 통해 알고리즘을 개선할 수 있다.
  (휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 얼마나 빨리 최단 경로를 파악할 수 있는지가 결정된다.)

모든 방향으로 탐색하는 것보다 목표로 한 것과 근사한 방향으로의 knowledge가 명백히 잘못된 방향으로의 탐색을 피하게 도와준다. 이때 관찰자가 가진 knowledge는 휴리스틱 함수(heuristic function)을 이용하여 표현될 수 있다.

예를 들어, 우리는 목표로부터 더 가까운 거리에 있는 노드에 대해 우선권을 줄 수 있다. 이것을 위해 우리는 모든 노드에 대해 실제 거리뿐만 아니라 추정되는 비용을 고려해야할 것이다. 이러한 알고리즘을 A* 알고리즘이라 한다.

 

A* 알고리즘은 환경에 따라 다익스트라(Dijkstra) 알고리즘보다 더 빠르고 더 거친 환경에서의 퍼포먼스도 가능할 것이다.

또한 Dijkstra와 마찬가지로 A*는 비용이 가장 낮은 셀만 평가하지만 나머지 거리의 추정치를 고려한다.

 

Such special knowledge that such an observer has can be encoded using a 'heuristic function', a fancier word for a “rule of thumb”.   (rule of thumb : 경험에 바탕을 둔 방법, 실제에 근거한 수단)

 

A* and D* become computationally expensive when either the search space is large, e.g., due to a fine-grain resolution
required for the task, or the dimensions of the search problem are high, e.g. when planning for an arm with multiple degrees of freedom. Solutions to these problems are provided by sampling-based path planning algorithms that are described further below.

 

heuristic function (휴리스틱 함수)

가용한 정보를 기반으로 각 분기 단계에서 어느 한 분기를 선택하기 위해 사용하는 다양한 탐색 알고리즘의 대안 함수이다.

https://enghqii.tistory.com/29 참고해서 다시 정리해보기

 

 

fine-grained

하나의 작업을 작은 단위의 프로세스로 나눈 뒤, 다수의 호출을 통해 작업 결과를 생성해내는 방식.

 

 

참고 자료를 바탕으로 직접 ppt를 만들어보았다.

 

 

 

#참고 자료

[Introduction to autonomous robots - Nikolaus Correll]

 

https://hengbokhan.tistory.com/133

02. 쿼리(query)란 무엇인가?

https://stackoverflow.com/questions/13487953/difference-between-quadtree-and-kd-tree

Difference between quadtree and kd-tree

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jin750226&logNo=120191771400 

데이터 패킷(Packet)이란?

http://msl.cs.illinois.edu/~lavalle/cs598/

Representations in Robotics

https://m.blog.naver.com/laonple/221207919855

5. 포인트 클라우드에서 누가 누가 빠른가? KDTree

http://www.gisdeveloper.co.kr/?paged=2&cat=9 

Algorithms – 페이지 2 – GIS Developer