The problem of navigating a bipedal robot to a desired destination in various environments is very important. However, it is very difficult to solve the navigation problem in real time because the computation time is very long due to the nature of the biped robot having a high degree of freedom. In order to overcome this, many scientists suggested navigation through the footstep planning. Usually footstep planning use the shortest distance or angles as the objective function based on the A * algorithm. Recently, the energy required for human walking, which is widely used in human dynamics, approximated by a polynomial function is proposed as a better cost function that explains the bipedal robot’s movement. In addition, for the real time navigation, using the action set of the $A^*$ algorithm not fixed, but the number changing according to the situation, so that the computation time does not increase much and the methods of considering the collision with the external environment are suggested as a practical method. In this thesis, polynomial function approximating the energy required for human walking is adopted as a cost function, and heuristic function considering the angular difference between the robot and the destination which is not shown in the previous studies is newly proposed and proved. In addition, a new method to integrate the adaptive behavior set and energy related to human walking is proposed. Furthermore, efficient collision avoidance method and a method to reduce the local minimum problem is proposed in this framework. Finally, footstep planning algorithm with all of these features into the mapping algorithm and the walking algorithm to solve the navigation problem is validated with simulation and real robot.
2 족 보행 로봇이 다양한 환경에서 원하는 목적지까지 이동하는 네비게이션 문제는 굉장히 중요하다. 그러나 자유도가 높은 2 족 보행 로봇의 특성상 연산 시간이 굉장히 오래 걸리기 때문에 실시간으로 네비게이션 문제를 푸는 것은 매우 어려운 일이다. 이를 극복하고자 많은 학자들이 제시한 방법이 발자국 계획을 통한 네비게이션이다. 기존의 발자국 계획들은 $A^*$ 알고리즘을 기반으로 목적함수를 단순히 최단 거리나 각도들을 활용한 값을 사용하였으나, 최근 들어 인체 역학 분야에서 널리 쓰이는 인간의 보행 시 소요되는 에너지를 다항 함수로 근사 하여 이를 목적함수화해서 사용하는 방안들이 제시되었다. 또한 실시간 네비게이션을 위하여 A* 알고리즘의 행동 집합을 고정하지 않고 유동적이게 상황에 맞게 개수를 변화시켜가며 사용하여, 연산 시간은 많이 늘리지 않으며 외부 환경과의 충돌 고려는 더 정확히 할 수 있는 방법들이 제시되었다. 본 학위논문에서는 인간의 보행 시 소요되는 에너지를 근사한 다항 함수를 목적 함수로 채택하였으며, 기존 연구들에서는 제시되지 않은 로봇과 목적지와의 각도 차이를 고려한 휴리스틱 함수를 새로 제시하였으며, 그 타당성을 수학적으로 증명하였다. 또한 적응형 행동 집합과 인간 보행 관련 에너지를 통합하는 방법을 새로 제안하고자 하며, 이 두가지 특성을 모두 가진 체 효율적인 충돌회피 방법과 극소점 문제를 줄이는 방법도 제시하고자 한다. 이후 이 모든 특징을 담은 발자국 계획 알고리즘을 매핑 알고리즘과 보행 알고리즘에 통합하여 시뮬레이션 및 실제 로봇으로 네비게이션 문제를 풀고자 한다.
