Visibility Graph

이 글은 아래의 책을 기반으로 작성되었습니다.

 

Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G. A., & Burgard, W. (2005). 
Principles of robot motion: theory, algorithms, and implementations. MIT press.

 

개념 설명

• Topological maps : represent graphlike structures with nodes and edges
  
  
• roadmap : node - a specific location
                    edge - a path between neighboring locations
  
  
• 5 types of roadmaps : visibility maps, deformation retracts, retract-like structures, piecewise retracts, silhouette

 

 

Visibility Graph Definition

• defined in a two-dimensional polygonal configuration space
  
  
• nodes : start location, goal location and all vertices of the configuration space obstacles
• edges : straight-line segments that connect two line-of-sight nodes

 

 

Polygonal Configuration Space

 

 

Node naming

 

Visibility array

 

Find the path : Using A* Algorithm (최단 경로 탐색 알고리즘)

ref.

http://www.gisdeveloper.co.kr/?p=3897 

최단 경로 탐색 – A* 알고리즘 – GIS Developer

 

 

Matlab으로 구현

 

https://youtu.be/Oh9JcldH2E8