[논문]Q-learning을 이용한 이동 로봇의 실시간 경로 계획

김호원; 이원창

doi:10.7471/ikeee.2020.24.4.991

Q-learning을 이용한 이동 로봇의 실시간 경로 계획
Real-Time Path Planning for Mobile Robots Using Q-Learning 원문보기

전기전자학회논문지 = Journal of IKEEE, v.24 no.4, 2020년, pp.991 - 997

김호원 (Dept. of Smart Robot Convergence and Application Engineering, Pukyong National University) , 이원창 (Dept. of Electronic Engineering, Pukyong National University)

초록
AI-Helper

강화학습은 주로 순차적인 의사 결정 문제에 적용되어 왔다. 특히 최근에는 신경망과 결합한 형태로 기존에는 해결하지 못한 분야에서도 성공적인 결과를 내고 있다. 하지만 신경망을 이용하는 강화학습은 현장에서 즉각적으로 사용하기엔 너무 복잡하다는 단점이 있다. 본 논문에서는 학습이 쉬운 강화학습 알고리즘 중 하나인 Q-learning을 이용하여 이동 로봇의 경로를 생성하는 알고리즘을 구현하였다. Q-table을 미리 만드는 방식의 Q-learning은 명확한 한계를 가지기 때문에 실시간으로 Q-table을 업데이트하는 실시간 Q-learning을 사용하였다. 탐험 전략을 조정하여 실시간 Q-learning에 필요한 학습 속도를 얻을 수 있었다. 마지막으로 실시간 Q-learning과 DQN의 성능을 비교하였다.

Abstract ▼ AI-Helper

Reinforcement learning has been applied mainly in sequential decision-making problems. Especially in recent years, reinforcement learning combined with neural networks has brought successful results in previously unsolved fields. However, reinforcement learning using deep neural networks has the disadvantage that it is too complex for immediate use in the field. In this paper, we implemented path planning algorithm for mobile robots using Q-learning, one of the easy-to-learn reinforcement learning algorithms. We used real-time Q-learning to update the Q-table in real-time since the Q-learning method of generating Q-tables in advance has obvious limitations. By adjusting the exploration strategy, we were able to obtain the learning speed required for real-time Q-learning. Finally, we compared the performance of real-time Q-learning and DQN.

주제어

표/그림 (7)

그림 Fig. 1. Agent-Environment interaction. 그림 1. 강화학습 모델
그림 Fig. 2. Unacceptable states. 그림 2. 허용되지 않는 상태
표 Table 1. Ε and rewards according to strategy.표 1. 전략에 따른 Ε과 보상
그림 Fig. 3. Episode-step graph. 그림 3. Episode-step 그래프
그림 Fig. 4. Episode-total step graph. 그림 4. Episode-total step 그래프
그림 Fig. 5. Episode-step graph of Cliff envirenment. 그림 5. Cliff 환경의 episode-step 그래프
그림 Fig. 6. Episode-step graph of Random environment. 그림 6. Random 환경 episode-step 그래프

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

이를 극복하기 위해 DQN과 같은 알고리즘을 쓸 수 있으나 간단한 문 제에 적용하기엔 상대적으로 큰 비용을 요구한다. 따라서 본 논문에선 Q-learning의 한계를 극복하기 위해 미리 Q-table을 만드는 것이 아닌 상태를 줬을 때 실시간으로 Q-table을 만드는 실시간 Q-learning을 구현하였다. 실시간으로 Q-table을 만들 수 있는 학습 속도를 얻기 위해 탐험 전략에 따른 학습 속도를 비교해보았으며, 시뮬레이션을 통해 얻은 최적 전략을 사용하여 DQN과 성능을 비교해보았다.
본 논문에서는 Q-learning의 한계를 극복하는 방법으로 실시간 Q-learning을 소개한다. 실시간 Qlearninge 단 하나의 Q-table만을 사용함으로써 기존의 방식이 가지는 상태의 가짓수만큼 Q-table이 필요하다는 한계를 극복할 수 있다.
본 논문에선 탐험 전략을 비교하기 위해 전략과 파라미터를 바꿔가며 결과를 비교한다.

가설 설정

∙시작 지점과 목표 지점은 연결돼야 한다.
∙학습을 할 수 없는 공간은 없어야 한다.
본 논문은 비영리 인공지능 연구회사인 OpenAI 에서 제공하는 강화학습 개발도구 Gym을 사용하여 시뮬레이션 환경을 구현하였다. 이 시뮬레이션은 이동 로봇이 무작위로 주어진 시작 지점에서 출발하여 장애물을 회피하며 무작위로 주어진 목표 지점으로 이동하는 상황이라 가정한다. 에이전트는 동, 서, 남, 북 네 방향으로만 움직일 수 있으며 움직일 때마다 step이 1 증가한다.

제안 방법

실시간 Q-learning과 DQN의 성능을 비교하기 위해 간단한 환경인 Cliff 환경과 복잡한 환경인 10 × 10 그리드 환경일 때 각각 비교해보았다. 1 episode마다 경로 찾기를 진행해 성능을 비교하였다. 복잡한 환경에서는 총 100개의 case를 학습했다.
본 논문은 비영리 인공지능 연구회사인 OpenAI 에서 제공하는 강화학습 개발도구 Gym을 사용하여 시뮬레이션 환경을 구현하였다. 이 시뮬레이션은 이동 로봇이 무작위로 주어진 시작 지점에서 출발하여 장애물을 회피하며 무작위로 주어진 목표 지점으로 이동하는 상황이라 가정한다.
실시간 Q-learning과 DQN의 성능을 비교하기 위해 간단한 환경인 Cliff 환경과 복잡한 환경인 10 × 10 그리드 환경일 때 각각 비교해보았다. 1 episode마다 경로 찾기를 진행해 성능을 비교하였다.
본 논문에서는 실시간 경로 생성을 위해 실시간 Q-learning을 사용하였다. 실시간 Q-learning에 필요한 학습 속도를 얻기 위해 Q-learning의 전략에 따른 학습 속도도 비교하여 보았다. 시뮬레이션 결과 가장 나은 전략은 ε이 0이고, 이동 시 음의 보상을 받는 것이었다.
따라서 본 논문에선 Q-learning의 한계를 극복하기 위해 미리 Q-table을 만드는 것이 아닌 상태를 줬을 때 실시간으로 Q-table을 만드는 실시간 Q-learning을 구현하였다. 실시간으로 Q-table을 만들 수 있는 학습 속도를 얻기 위해 탐험 전략에 따른 학습 속도를 비교해보았으며, 시뮬레이션을 통해 얻은 최적 전략을 사용하여 DQN과 성능을 비교해보았다.
이를 극복하기 위해 신경망을 사용하는 방법이 있으며 대표적인 방법으로는 Deep Q-Networks (DQN)가 있다. 알파고는 DQN을 사용하여 상태의 가짓수가 무한대에 가까운 바둑에서 정상급 인간 프로기사를 이겼다.
실시간 Q-learning을 사용하기 위해선 가능한 빠른 학습 속도가 필요하다. 이를 위해 Q-learning의 탐험 전략에 따른 학습 속도를 비교해보고, 가장 빠른 학습 속도를 지니는 탐험 전략을 이용하여 실시간 경로 계획을 구현하였다.
전략 2는 episode 당 step이 15 이하로 내려가는데 총 10,000번 이하의 step이 필요하였다. 전략 2를 최적 전략이라 생각하고 실시간 Q-learning을 시뮬레이션해보았다.

대상 데이터

1, 5, 6번의 경우 3,500 episode, 40,000 case 동안 유의미한 학습 결과를 내지 못하여 학습을 중단하였다. 2, 3, 4번의 경우 학습이 되는 것이 확인돼 3,500 episode, 400,000 case를 학습하였다.
1 episode마다 경로 찾기를 진행해 성능을 비교하였다. 복잡한 환경에서는 총 100개의 case를 학습했다. 경로 찾기의 성공과 실패는 step 수로 구분하였다.
시뮬레이션은 10 × 10 그리드 환경에서 진행하였다. 장애물의 개수는 25개이다.
시뮬레이션은 10 × 10 그리드 환경에서 진행하였다. 장애물의 개수는 25개이다. 장애물이 없는 경우 최소거리는 10이고 최대거리는 18이다.

이론/모형

강화학습은 순차적인 의사 결정 문제 에 적합하다는 점에서 경로 생성에 적합한 알고리즘이라 할 수 있고, 해당 연구도 활발히 진행되고 있다. 본 논문에서는 대표적인 강화학습 알고리즘인 Q-learning을 사용하여 경로 생성을 진행하였다 [4-7]. 일반적으로 Q-table을 생성하는 Q-learninge 상태의 가짓수가 많아지는 경우 모든 상태에 대한 학습 테이블을 저장할 수 없다는 한계를 가진 다.
본 논문에서는 실시간 경로 생성을 위해 실시간 Q-learning을 사용하였다. 실시간 Q-learning에 필요한 학습 속도를 얻기 위해 Q-learning의 전략에 따른 학습 속도도 비교하여 보았다.

성능/효과

또한, 30 × 30의 그리드 월드에서도 동작하는 것을 확인했다. 마지막으로 실시간 Q-learning과 DQN의 성능을 비교했을 때 DQN의 정확도가 더 우수한 것으로 나왔지만 학습 속도는 실시간 Q-learning이 더 우수함을 보였다. 또한 위에서 언급한 것처럼 실시간 Q-learning의 경우 10 × 10 환경에서 30 × 30 환경으로 즉시 변환하여 사용할 수 있었으나 DQNe 새로운 환경을 학습시키기 전까진 사용할 수 없다.
또한, 이동 도중 상태가 바뀌는 경우도 같은 결과를 보였다. 시뮬레이션 환경의 상태가 10 × 10의 그리드 월드에 25개의 장애물, 시작 지점, 목표 지점이 무작위로 생기는 것을 고려했을 때, 최대 1.9× 10²⁴개의 상태가 나와 Q-learning으로 해결할 수 없을 것으로 생각되지만, 실시간 Q-learning을 사용하는 경우 문제를 해결할 수 있었다. 또한, 30 × 30의 그리드 월드에서도 동작하는 것을 확인했다.
종합적으로 고려했을 때 기존의 Q-learning으로 해결할 수 없는 것으로 알려져서 과도한 성능의 알고리즘을 사용하고 있는 영역이 있다면 높은 유연 성과 낮은 비용을 사용하는 실시간 Q-learninge 이러한 영역에 사용할 수 있는 대안 알고리즘으로 보인다.

후속연구

ε이 탐색을 위해 사용되는 것을 생각했을 때, 이동 시 음의 보상을 주는 것이 그리드 월드에서 탐색을 유도한 것으로 보인다. 다른 환경에서도 보편적으로 쓰일 수 있을지는 추가연구가 필요하다고 판단된다. 이 전략을 사용하여 실시간 경로 생성에 실시간 Q-learning을 사용하였을 때, 목표 지점에 도착하는데 무리가 없었다.

참고문헌 (9)

H. T. Cormen, C. E. Leiserson, R. L. Rivest, and Clifford Stein, Introduction to Algorithms,. Second Edition, MIT Press and McGrawHill, 2001.
S. Koenig and M. Likhachev, "D* lite," National Conference on Artificial Intelligence, vol.18, pp. 476-483, 2002.
S. Koenig and M. Likhachev, "Incremental A*," Advances in Neural Information Processing Systems, vol.14, pp.1539-1546, 2002.
R. Sutton and A. Barto, Reinforcement learning, MIT Press, 1996.
Y. Li, C. Li and Z. Zhang, "Q-Learning Based Method of Adaptive Path Planning for Mobile Robot," IEEE International Conference on Information Acquisition, pp.983-987, 2006. DOI: 10.1109/ICIA.2006.305871
D. Tamilselve, S. M. Shalinie and G. Nirmala, "Q Learning for Mobile Robot Navigation in Indoor Environment," IEEE International Conference on Recent Trends in Information Technology, pp.324-329, 2011. DOI: 10.1109/ICRTIT.2011.5972477
J. Muhammad and I. O. Bucak, "An Improved Q-Learning Algorithm for an Autonomous Mobile Robot Navigation Problem," 2013 TAEECE, pp. 239-243, 2013. DOI: 10.1109/TAEECE.2013.6557278
Mnih, Volodymyr, et al, "Playing Atari with Deep Reinforcement Learning," NIPS Deep Learning Workshop 2013, pp.1-9, 2013.
Mnih, Volodymyr, et al, "Human-level control through deep reinforcement learning," Nature, Vol.518, No.7540, pp.529-533, 2015.

상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증