In this thesis we develop an efficient path planning algorithm for mobile robot in the two dimensional space. Using the visibility polygon concept and raster representation of the objective world, we can reduce computational cost in two respects, expansion of only necessary portion of the search graph and efficient exploration of a node.
Among child nodes of a node some nodes can not be included in the shortest path. In the proposed algorithm are generated only the portion of child nodes that have possibility to be included in the shortest path. Due to this restricted generation of child nodes, considerable reduction of the search graph is achieved.
In spite of intrinsic error, raster representation is useful for path planning and has two advantages : fast determination of visibility of two points and no restriction on the shape of obstacle. Utilizing the first we can construct a visibility polygon from a point very efficiently. This means fast generation of child nodes. By the second advantage we can handle complicated environment with small effort.
본 논문에서는 이차원 평면상에서 움직이는 로보트를 위한 효과적인 경로 결정 알고리즘을 연구하였다. Visibility polygon 개념을 이용하고 환경을 raster로 표현함으로써 두가지 측면에서 계산 능률을 향상시켰다. 탐색 그래프 상에서 필요한 부분만의 생성과 효과적인 개별 노드의 확장이 그 두가지이다.
각 노드의 자식 노드들 중 최단 경로에 포함될 수 없는 노드들이 존재할 수 있다. 제안된 알고리즘에서는 자식 노드들 중 최단 경로에 포함될 가능성이 있는 노드들만을 생성시킨다. 이 제한된 자식 노드의 생성으로 인하여 상당한 탐색그래프의 축소를 이룰 수 있었다.
내재된 오차에도 불구하고 raster 표현은 경로 결정에 매우 유용하며 다음과 같은 두가지 장점을 가진다. 두 점이 서로 보이는가 여부를 신속히 결정할 수 있다는 것과 표현 가능한 장애물의 형태에 제한이 없다는 사실이다. 첫째의 장점을 이용함으로써 Visibility polygon을 효과적으로 구할 수 있으며 이것은 개별 노드의 신속한 확장을 의미한다. 둘째의 장점으로 인하여 복잡한 환경을 큰 어려움 없이 다룰 수 있다.
