This thesis proposes a novel multi-objective evolutionary approach for on-line navigation of humanoid robots. The proposed approach helps a humanoid robot to optimize its footsteps with local information while walking in an unstructured environment. In humanoid robot navigation, it is required to consider the multiple objectives such as elapsed time, safety, and energy consumption at the same time, where two or more of them conflict with each other. Therefore, this kind of problem should be formulated as a multi-objective problem. In other words, multiobjective evolutionary algorithms (MOEAs) are necessary. In addition, the MOEAs should be able to take the priorities or the dependencies of the objectives into account and determine the relative merits of the nondominated solutions.
To deal with these issues, dual multi-objective particle swarm optimization (DMOPSO) is proposed. As a preliminary, multi-objective particle swarm optimization with preference-based sort (MOPSO-PS) is developed. And then, by extending the concept of preference-based sort into a secondary multi-objective optimization, DMOPSO is proposed. DMOPSO utilizes the secondary objectives, global evaluation value and crowding distance. The global evaluation value of a particle is calculated by the fuzzy integral that integrates the partial evaluation value of each objective with respect to the degree of consideration where the user’s preference is represented as the degree of consideration for each objective using the fuzzy measure. The crowding distance of a particle implies the crowdedness around the particle. Through the secondary objectives, the user’s preference can be properly reflected and thus the relative merits of the nondominated solutions can be clearly figured out as well as the interactions among the objectives can be considered. The effectiveness of the DMOPSO is demonstrated by the empirical comparison with the other algorithms. The results indicate that the user’s preference is properly reflected while maintaining the solution quality and the diversity. In addition, to reduce the computation time enough for online implementation, a homogeneous parallel computing (HPC) framework for MOEAs is designed and applied to DMOPSO. In this framework, every processor does the same task in parallel and thus the algorithm becomes faster and more fault-tolerant. Moreover, there is no need for communication among the processors and the number of processors can also be readily altered in each trial. The statistical analysis indicates that the computation time for the evolutionary optimization is reduced by about 70% through the incorporation of the HPC framework without meaningful degradation of solution quality and diversity.
Based on DMOPSO, the proposed approach mainly deals with the path planning with the local information of the environment provided by a virtual local vision system, the footstep optimization with multiple objectives, and the footstep following control of the robot. In general, humans take a look around intermittently while walking. Likewise, in the proposed approach, a humanoid robot is supposed to check environment out at every 4-footstep walking with a certain sight range. Also, as humans plan several footsteps in advance and walk as planned unless an unexpected event is occurred, the robot is supposed to plan the next 10 footsteps while walking 4 footsteps with the local information about the surroundings. Firstly, the robot acquires the localization data through the local vision rocessing. For simplicity, it is assumed that the local vision system is virtually implemented and can localize the robot itself and the nearby obstacles. After that, with the localization data, a continuous partial path is generated by the path planner. And then, with the generated partial path, the footstep optimizer produces the optimal footstep sequence. Finally, the robot is controlled to follow the optimized footstep sequence. Both the simulation and the hardware experiment with humanoid robot HanSaRam-X (HSR-X) verifies that, through the proposed approach, the robot navigates successfully to the goal with local information in an unstructured environment with various obstacles, satisfying the given objectives.
본 논문은 휴머노이드 로봇의 온라인 네비게이션을 위한 새로운 다목적 진화 접근법을 제안한다.
제안하는 접근법은 구조적이지 않은 환경에서 로봇이 걷는 도중에 로컬 정보를 활용하여 다음 걸음새를 다목적 진화 최적화 하는 방법이다. 휴머노이드 로봇 네비게이션에서는 소요시간, 안전성, 에너지 소모와 같은 서로 상충되는 목적들을 동시에 고려해야 한다. 그렇기 때문에 이 문제는다목적 최적화 문제로 정의되야한다. 다시 말해 다목적 진화 알고리즘이 꼭 필요하다. 뿐만아니라 이 때 사용하는다목적 진화 알고리즘은 목적들의 우선 순위나 목적들 간의의존도를 고려할 수 있어야 하고 비압도해 (Nondominated solution)들 사이의 상대적인 가치또한 판단할 수 있어야한다.
이를 위해 이중 다목적 입자 군집 최적화 (Dual MOPSO, DMOPSO)를 제안한다. 먼저 선행 단계로서 선호도 기반 정렬을 사용한 다목적 입자 군집 최적화 (MOPSO-PS)를 개발한다. 그리고 이를 부 목적 최적화 개념으로 확장하여, 최종적으로 DMOPSO를 제안한다. DMOPSO는 부 목적으로 광역평가치(Global evaluation value)와밀집거리(Crowding distance)를 이용한다. 광역평가치는 고려정도와 부분평가치 (Partial evaluation value)를 퍼지 적분 (Fuzzy integral) 하여 계산하는데 이 때 사용자의 선호도가 각각의 목표에 대한 고려 정도로 표시되고, 이는 퍼지 척도 (Fuzzy measure)를 통해 표현된다. 밀집거리는 해당 입자 주변이 얼마나 밀집되어 있는지를 나타낸다. 이러한 부 목적을 통해 사용자의 선호도가 반영되고 이로써 목적들 간의 관계나 비압도해들의 상대적인 가치도 충분히 고려할 수 있다. DMOPSO의 유효성은 다른 알고리즘들과의 실증적인 비교를 통해 보여지는데, 그 결과는 DMOPSO가 해의 질이나 다양성을 유지하면서 사용자의 선호도를 잘 반영하는 것을 보여준다. 추가로, 이러한 다목적 최적화 알고리즘을 수행하는데 걸리는 시간을 획기적으로 줄이기 위해, DMOPSO를 위한 동질 병렬 계산 (Homogeneous parallel computing, HPC) 프레임워크를 제안한다. 이 프레임워크에서 모든 프로세서는 병렬적으로 같은 작업을 수행한다. 그래서 알고리즘이 더욱 빠르면서도 오류없이 수행된다. 뿐만아니라프로세서 간 통신이 필요없고 사용 프로세서의 개수를 손쉽게 바꿀 수 있다는 점에서 이질 병렬 계산(Heterogeneous parallel computing) 보다 유리하다. 프로세서의 개수를 바꾸어가며 연산 시간을 측정해본 결과, 프로세서를 네 개까지 늘렸을 때 해의 질이나 다양성면에서 눈에 띄는 저하 없이 약 70%까지 연산시간이 줄일 수 있었다.
제안하는 접근법은 환경에 관한 로컬 정보를 이용한 경로 계획과,이렇게 생성된 부분 경로를 이용한 다목적 걸음새 최적화, 그리고 이 걸음새를 따라 로봇이 걷도록 하는 걸음새 추종제어로 구성된다. 일반적으로 사람은 걸으면서 주변 환경을 간헐적으로 둘러본다. 비슷하게 본 온라인 접근법에서도 로봇이 네 걸음을 걸을 때 마다 주변을 확인하도록 하였다. 또한 사람은 멀리 보고 걸음새를 미리 계획해두고 갑작스런 돌발 상황이 발생하기 전에는 계획한 대로 걷는다. 그래서 본 온라인 접근법은 로봇이 네 걸음 걷는 동안 다음 열 걸음을 계획하도록 하였다. 가장 먼저,로봇은로컬 영상처리를 통해 측위정보를 획득한다. 문제의 단순화를 위해 측위를 위한 로컬 영상 시스템은 가상으로 구현하였다. 이후, 측위정보를 이용해 경로 생성기가 부분 경로를 생성한다. 다음으로, 부분 경로를 이용해 걸음새 최적화기는 앞서 제안한 DMOPSO와 HPC 프레임 워크를 이용해 부분 걸음에 최적화된 걸음새를만든다. 마지막으로, 로봇이 계획한 걸음새대로 따라가도록 제어를 하게된다. 이 온라인 접근법의 실효성은 시뮬레이션과 실제 실험을 모두 거쳐 입증 되었는데, 성공적으로 로봇이 로컬 정보를 이용해 구조적이지 않은 환경내에서 장해물을 피해 도착지점 까지 네비게이션을 수행하였다.
