This thesis presents algorithms that can be inserted into the conventional A* or Lifelong Planning A* (LPA*) algorithms to facilitate accurate path finding for quasiholonomic (or holonomic) and nonholonomic mobile robots. For a mobile robot to safely avoid obstacles in complex environments that have many obstacles, its shape should be taken into account by path planners. However, prior works have problems that a mobile robot cannot pass through a narrow passage if it is rectangular in shape and its computed radius is larger than the width of the passage.
For quasiholonomic mobile robots, this thesis proposes an A* (and LPA*) based path planning method in which the forward movement of the mobile robot is favored over the reverse because cameras are generally installed on the mobile robot with forward motion in mind, and the shape of the mobile robot is more accurately taken into account. Further, this method is extended to LPA* such that it can cover both static and dynamic obstacle environments. Finally, this thesis shows via a series of simulations that the proposed algorithm provides feasible paths by accurately taking into account the unsymmetrical shape of mobile robots in static and dynamic obstacle environments. Consequently, this thesis demonstrates via a series of simulations that the proposed method can quickly replan a collision-free path while accurately taking into account the unsymmetrical shapes of the mobile robots with quasiholonomic constraint.
For nonholonomic mobile robots, this thesis presents a novel path planning method, Kinematicsaware A* (K*), for efficiently generating paths considering the kinematics, shape and turning space of
the mobile robots. The proposed method is based on a kinematics-aware node expansion method that also checks for collisions based on the shape of the mobile robots. This thesis presents two different heuristics considering the kinematics of the mobile robot simultaneously with and without obstacles. Especially for complex environments that have complex obstacles and even narrow passages, this algorithm recursively identifies intermediate goals and in-between nodes that allow the mobile robot to pass through the narrow passage for computing a path to the goal. This thesis has demonstrated benefits of the proposed method in various simulations and experimental results using a developed autonomous mobile robot. Furthermore, this thesis has shown that the proposed method efficiently generates collision-free paths that the mobile robots can follow even for complex environments with narrow passages.
본 논문에서는 복잡한 장애물 환경하에서 Holonomic 혹은 Nonholonomic 구속 조건을 가지는 Mobile Robot이 안전하게 장애물을 회피할 수 있도록 기존의 A* 혹은 Lifelong Planning A*(LPA*) 알고리즘에 그 형상을 정밀하게 고려한 알고리즘을 제안하였다.
첫 번째로, Holonomic 구속 조건을 가지는 Tank-like Mobile Robot에 대해서는 Camera Sensor 등이 전방을 향하여 장착되어 있는 경우가 많기 때문에 가능하면 전방을 향하도록 충돌 회피 경로를 생성하도록 하였다. 위의 특징을 최대한으로 반영하기 위해 Tank-like Mobile Robot의 기구학적 특징인 제자리 회전 특성을 활용하였다. 특히, Graphic 방법을 통한 장애물과의 간섭 확인을 하도록 하여 비대칭적인 형상을 갖는 Mobile Robot에 대해서도 정밀하게 충돌 회피 경로를 찾을 수 있다. 이는 기존에 제안되었던 방법인 Mobile Robot의 외형을 감싸는 원으로 그 형상을 단순화 시킨 방법에서는 Narrow Passage 문제를 해결할 수 없었으나 제안한 알고리즘을 통해 이를 해결 할 수 있게 되었다. 즉, Mobile Robot의 외형을 원으로 단순화 시키면 Mobile Robot의 실제 폭보다 큰 Narrow Passage이지만 단순화 시킨 원이 Narrow Passage의 폭보다 크게 계산되는 경우가 생기는 문제점이 생길 수 있다.
또한, 정적 장애물뿐만 아니라 동적 장애물을 고려한 LPA*에 위에서 설명한 알고리즘을 적용하기 위해 Virtual Obstacle을 도입하였다. 이는 LPA*는 발견한 경로 위에서 새로운 장애물의 발견이나 기존의 장애물이 사라지는 경우에 대해서만 경로 재생성이 가능한데, 고려한 Mobile Robot은 외형이 존재하기 때문에 기존의 LPA*만을 이용하게 되면 이를 반영할 수 없는 문제점이 생기게 된다. 이를 해결하기 위해 Mobile Robot의 형상을 고려하여 변경된 장애물 주변에 Virtual Obstacle을 생성한 후 경로를 재생성하도록 하였다. 이 Virtual Obstacle은 장애물의 상태를 갱신할 때에만 이용되고 경로를 재생성할 때에는 해당 Node의 원래 상태가 이용되도록 알고리즘을 구성하였다. 본 논문에서는 제안한 알고리즘의 유효성을 파악하기 위해 Narrow Passage를 포함한 장애물 환경 그리고 동적 장애물 환경하에서 장애물 회피 경로 생성 결과를 살펴보았다.
두 번째로, Nonholonomic 구속 조건을 가지는 Car-like Mobile Robot에 대해서는 Tank-like Mobile Robot에서 고려한 것과 같이 형상을 고려하였으며 추가적으로 Mobile Robot의 최소 회전반경도 고려하였다. 최소 회전반경을 Grid Map에서 Discrete하게 구현하기 위해 Kinematics-aware Node Expansion을 제안하였다. 추가적으로 사람의 운전 특성을 반영하기 위해 Orientation-driven Arc Cost를 제안하였다. 이는 Mobile Robot의 현 위치와 도착 위치의 Euclidean Distance가 차량의 1.5배 이상인 거리에서만 Mobile Robot의 후진에 해당하는 Arc Cost에 그 Euclidean Distance를 반영하여 현 위치와 도착 위치의 거리가 먼 경우에 후진을 가능하면 최소화 시키도록 알고리즘을 구성한 것이다. 또한, Mobile Robot의 형상을 정밀하게 고려하기 위해 Node Expansion과 Heuristic 계산 시 Mobile Robot의 회전을 고려하여 장애물과의 간섭을 확인하도록 하였다. 이는 Node 확장 시에 장애물 간섭을 확인 하기 때문에 경로 생성 후에 반복적으로 장애물 간섭을 확인 후 경로를 재 생성하는 기존의 방법에 비해 매우 효율적인 방법이다. 이 때, Heuristic 계산시 Obstacle-free 및 Obstacle-aware Kinematic Heuristic을 도입하여 경로 생성 시간을 단축 시킬 수 있었다. 즉, Obstacle-aware Kinematic Heuristic 계산 시 Dynamic Programming 이나 Voronoi Graph 계산 등의 시간이 많이 소요되는 기존의 방법 대신에 Obstacle-free Kinematic을 Modulation하여 그 효율성을 증대 시킨 것이다. 이는 추가적으로 기존의 방법과는 다르게 Kinematics도 반영하였기 때문에 Node Expansion 시 불필요한 영역으로의 Node Expansion을 최소화 하는 장점도 가지고 있다. 하지만, Car-like Mobile Robot의 경로는 최소 회전반경을 필요로 하기 때문에 전/후진의 조합을 통해서 경로 생성이 가능한 경우가 대부분이다. 전/후진의 조합이 필요한 경로 생성으로 위해서는 Node Expansion 시 중복이 필수적이나 기존의 A* 알고리즘은 이를 반영할 수 없는 문제점을 가지고 있다. 따라서 이를 해결하기 위해, Intermediate Goal과 In-between Node를 Shape-aware A*와 Heuristic-driven Search 알고리즘을 통해 반복적으로 찾아 최종 도착 위치까지의 경로를 생성하는 방법을 제안하였다.
본 논문에서는 제안한 알고리즘의 유효성을 파악하기 위해 Narrow Passage를 포함한 장애물 환경 및 복잡한 장애물 환경하에서 장애물 회피 경로 생성 결과를 살펴보았다. 특히, 좁은 공간을 전/후진 반복하여 빠져 나오는 경우와 좁은 공간에서 평행 주차를 하는 것에 대한 Simulation을 수행하였으며 KAIST Mobile Robot을 이용하여 Narrow Passage를 통과하는 것과 좁은 공간에서 전/후진을 반복하여 직각 후진 주차하는 것에 대한 실험을 수행하여 제안한 알고리즘의 유효성을 검증하였다.
