마이크로 마우스를 이용한 다수의 미로 경진대회가 개최되어 미로 탐색 알고리즘의 성능이 비교되고 있으며, 미로 탐색 알고리즘은 좌(우)수법, 구심법, 언덕오르기 등을 기본으로 하여 다양한 형태로 적용되어 사용되고 있다. 하지만 미로 탐색알고리즘을 적용하여 테스트하기 위한 소프트웨어 플랫폼이 없어서 프로그램을 직접 개발하거나 하드웨어를 통해 알고리즘의 성능을 테스트해야 하는 불편함을 겪는다. 본 연구에서는 하드웨어로 구현이 어려운 다양한 형태의 미로 제작과 알고리즘의 손쉬운 적용이 가능하고, 스텝, 연산 횟수, 탐색 시간의 평가가 가능한 미로 탐색 알고리즘을 위한 플랫폼을 개발하였다. 플랫폼은 메인 레이어, 인터페이스 레이어, 사용자 레이어의 분리 구조로 되어 알고리즘을 쉽게 교체적용 할 수 있는 장점이 있다. 플랫폼의 실험을 통하여 미로 탐색 알고리즘들의 성능을 평가하고 분석하여 알고리즘의 개발 및 실험에도 적용할 수 있음을 확인하였다.
마이크로 마우스를 이용한 다수의 미로 경진대회가 개최되어 미로 탐색 알고리즘의 성능이 비교되고 있으며, 미로 탐색 알고리즘은 좌(우)수법, 구심법, 언덕오르기 등을 기본으로 하여 다양한 형태로 적용되어 사용되고 있다. 하지만 미로 탐색알고리즘을 적용하여 테스트하기 위한 소프트웨어 플랫폼이 없어서 프로그램을 직접 개발하거나 하드웨어를 통해 알고리즘의 성능을 테스트해야 하는 불편함을 겪는다. 본 연구에서는 하드웨어로 구현이 어려운 다양한 형태의 미로 제작과 알고리즘의 손쉬운 적용이 가능하고, 스텝, 연산 횟수, 탐색 시간의 평가가 가능한 미로 탐색 알고리즘을 위한 플랫폼을 개발하였다. 플랫폼은 메인 레이어, 인터페이스 레이어, 사용자 레이어의 분리 구조로 되어 알고리즘을 쉽게 교체적용 할 수 있는 장점이 있다. 플랫폼의 실험을 통하여 미로 탐색 알고리즘들의 성능을 평가하고 분석하여 알고리즘의 개발 및 실험에도 적용할 수 있음을 확인하였다.
Many contests by micro mouse was celebrated of which maze search algorithms performance are compared. That is used in various forms based on left(right) weight method, euclidean algorithm method, hill climbing method. However we feel uncomfortable to test algorithms performance through direct develo...
Many contests by micro mouse was celebrated of which maze search algorithms performance are compared. That is used in various forms based on left(right) weight method, euclidean algorithm method, hill climbing method. However we feel uncomfortable to test algorithms performance through direct development of programs or hardwares as no software platform to test in maze search algorithms. In this research we develop of a platform for maze search algorithms that is easily to produce various forms of maze that are hard to be realized by hardware, to apply algorithms, and evaluate the seek time, operation count, steps and performance. The platform is consist of main layer, interface layer, user layer which has merit to apply and replace easily algorithms. We verified that the maze search algorithm can be applied even in the development and experiment of algorithm by evaluating and analyzing its performance through the experiment of platform.
Many contests by micro mouse was celebrated of which maze search algorithms performance are compared. That is used in various forms based on left(right) weight method, euclidean algorithm method, hill climbing method. However we feel uncomfortable to test algorithms performance through direct development of programs or hardwares as no software platform to test in maze search algorithms. In this research we develop of a platform for maze search algorithms that is easily to produce various forms of maze that are hard to be realized by hardware, to apply algorithms, and evaluate the seek time, operation count, steps and performance. The platform is consist of main layer, interface layer, user layer which has merit to apply and replace easily algorithms. We verified that the maze search algorithm can be applied even in the development and experiment of algorithm by evaluating and analyzing its performance through the experiment of platform.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 다양한 알고리즘을 적용하고 성능을 평가하기 위한 플랫폼을 설계하고 구현하였다.
본 논문에서는 이러한 불편을 해소하기 위해서 미로 탐색 알고리즘 테스트를 위한 플랫폼을 설계하고 구현하였다. 플랫폼은 현실에서는 구현하기 어려운 장애물이나 미로의 출발점 및 도착점을 간단한 마우스 클릭만으로 자유롭게 설치할 수 있도록 도와주며, C++언어를 사용하여 알고리즘을 작성하거나 불러와 생성된 미로에 적용시킬 수 있다.
본 플랫폼은 Windows XP 환경에서 Visual Studio 2008, C++, Windows API를 이용하여 개발하였으며, 테스트 미로는 그림 7과 같이 마이크로 마우스 대회에서 사용하는 미로와 유사하게 작성하였다. 본 연구에서는 좌수법, 확장좌수법, A* 알고리즘 등을 대상으로 장애물이 있는 경우와 없는 경우에 대하여 시간과 스텝 수를 평가하였다. 시간은 캐릭터가 도착점에 도달할 때가지 소요된 시간(초), 스텝 수는 캐릭터가 이동하거나 제자리에서 방향을 변경할 때 마다 1씩 증가하여 얻어진 수치이다.
본 연구에서는 하드웨어로 구현이 어려운 다양한 형태의 미로 제작과 알고리즘의 손쉬운 적용이 가능하고, 스텝, 연산 횟수, 탐색 시간의 평가가 가능한 미로 탐색 알고리즘을 평가하기 위한 플랫폼을 개발하였다. 플랫폼은 메인 레이어, 인터페이스 레이어, 사용자 레이어의 3개 레이어로 구성되어 알고리즘을 쉽게 교체적용 할 수 있는 특징이 있다.
제안 방법
시간은 캐릭터가 도착점에 도달할 때가지 소요된 시간(초), 스텝 수는 캐릭터가 이동하거나 제자리에서 방향을 변경할 때 마다 1씩 증가하여 얻어진 수치이다. 그리고 장애물로는 늪지대와 문을 사용하였고, 늪지대를 통과할 경우 2초의 시간 가중치가 더해지고, 문은 5초마다 열리고 닫히는 걸 반복하도록 설계하였다. 실험에서는 시간에 우선순위를 두어 평가 결과를 판단하였다.
미로 탐색 알고리즘을 연구하기 위해서 플랫폼을 직접 제작하거나 하드웨어로 성능을 테스트해야 하는 불편함을 해결하고, 실험에서 동일한 조건을 제공하기 위해 미로 탐색 알고리즘 테스트를 위한 플랫폼은 그림 1과 같이 메인 레이어, 인터페이스 레이어, 사용자 레이어의 3개 레이어 구조로 설계했다. 각 레이어의 분할을 통해 사용자는 쉽게 사용자 레이어에 찾아가 알고리즘을 교체하거나 적용할 수 있고 적용된 알고리즘이 메인 레이어의 미로 정보 모듈에 영향을 끼치는 것을 미연에 방지하는 것도 가능하게 되었다.
본 플랫폼을 이용하여 좌수법, 확장좌수법, 언덕오르기 알고리즘, A* 알고리즘 등의 미로 탐색 알고리즘을 테스트하여 다음과 같은 결과를 확인하였다. 첫째, 여러 가지 미로 탐색 알고리즘을 동일한 조건에서 적용하여 테스트 할 수 있었다.
사용자 미로 정보 모듈은 메인 레이어의 미로 정보 모듈에서 미로의 정보를 상속 받아 사용자가 알고리즘의 구현에 필요한 정보들을 허용된 범위에서 추가하거나 수정하여 사용자 알고리즘의 완성도를 높일 수 있는 정보를 제공한다. 미로의 정보는 구성된 미로의 형태에는 영향을 주지 않으며, 사용자가 알고리즘을 구성할 때 사용자에 맞게 정보를 가공할 수 있다.
그 다음 도착점을 찾으면 다시 출발점에서부터 캐릭터를 한 칸씩 이동하게 된다. 이때 메모리에 저장된 타일에 대한 평가값에 따라 이동하고, 장애물의 유무에 따라 이동 경로를 달리하여 최단 경로를 탐색하였다. 하지만 문과 같은 가변형 장애물이 있는 경우에는 문을 벽으로 인식하여 반드시 최단 경로를 탐색할 수는 없었다.
플랫폼은 현실에서는 구현하기 어려운 장애물이나 미로의 출발점 및 도착점을 간단한 마우스 클릭만으로 자유롭게 설치할 수 있도록 도와주며, C++언어를 사용하여 알고리즘을 작성하거나 불러와 생성된 미로에 적용시킬 수 있다. 적용된 알고리즘은 경로 및 움직임을 애니메이션 효과로 확인할 수 있고 가중치가 적용된 탐색 시간, 연산 횟수, 스텝 등의 성능 비교 또한 가능하도록 제작되었다. 본 플랫폼에 기존에 알려진 다양한 미로 탐색 알고리즘을 적용하여 성능을 평가하고 분석함으로써, 미로 탐색 알고리즘을 연구하기 위한 통합 플랫폼으로써의 사용될 수 있을 것이다.
확장좌수법은 테스트 미로가 아일랜드 형 미로이기 때문에 단일 폐곡선을 한번 이동하고 다른 길을 탐색하여 도착점을 찾았다. 또한 장애물의 인식 여부와 관계없이 장애물을 피하지 못하고 통과하기 때문에 시간이 더욱 증가하게 된다.
데이터처리
그리고 장애물로는 늪지대와 문을 사용하였고, 늪지대를 통과할 경우 2초의 시간 가중치가 더해지고, 문은 5초마다 열리고 닫히는 걸 반복하도록 설계하였다. 실험에서는 시간에 우선순위를 두어 평가 결과를 판단하였다.
성능/효과
첫째, 여러 가지 미로 탐색 알고리즘을 동일한 조건에서 적용하여 테스트 할 수 있었다. 둘째, 하드웨어 상에서 구현하기 어려운 장애물을 쉽게 설치하여 다양한 형태의 미로를 생성하고 테스트 할 수 있었다. 향후 다양한 알고리즘의 적용과 미로의 3차원 확장에 대한 연구를 진행할 예정이다.
그림 7은 테스트 미로의 출발점, 도착점, 장애물과 A* 알고리즘을 적용한 캐릭터의 이동 경로를 보여준다. 이 테스트 미로에 언덕오르기 알고리즘을 적용했을 때에도 A* 알고리즘과 동일한 이동 경로를 보여주었고, 두 알고리즘 모두 장애물을 회피하여 경로를 찾았다.
본 플랫폼을 이용하여 좌수법, 확장좌수법, 언덕오르기 알고리즘, A* 알고리즘 등의 미로 탐색 알고리즘을 테스트하여 다음과 같은 결과를 확인하였다. 첫째, 여러 가지 미로 탐색 알고리즘을 동일한 조건에서 적용하여 테스트 할 수 있었다. 둘째, 하드웨어 상에서 구현하기 어려운 장애물을 쉽게 설치하여 다양한 형태의 미로를 생성하고 테스트 할 수 있었다.
표 5 알고리즘 평가 결과에서 보듯이 장애물이 있는 경우와 없는 경우 모두 A* 알고리즘과 언덕오르기 알고리즘이 확장좌수법보다 빠른 결과를 보였다.
후속연구
적용된 알고리즘은 경로 및 움직임을 애니메이션 효과로 확인할 수 있고 가중치가 적용된 탐색 시간, 연산 횟수, 스텝 등의 성능 비교 또한 가능하도록 제작되었다. 본 플랫폼에 기존에 알려진 다양한 미로 탐색 알고리즘을 적용하여 성능을 평가하고 분석함으로써, 미로 탐색 알고리즘을 연구하기 위한 통합 플랫폼으로써의 사용될 수 있을 것이다.
둘째, 하드웨어 상에서 구현하기 어려운 장애물을 쉽게 설치하여 다양한 형태의 미로를 생성하고 테스트 할 수 있었다. 향후 다양한 알고리즘의 적용과 미로의 3차원 확장에 대한 연구를 진행할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
미로 탐색 알고리즘은 무슨 방법을 말하는가?
미로 탐색 알고리즘은 출발점에서 도착점까지의 경로를 찾아내기 위한 방법을 말한다[1]. 미로 탐색 알고리즘은 일반적인 미로 탐색 방법, 최단 경로를 찾는 방법, 최소 비용을 찾는 방법으로 나뉜다.
미로 탐색 방법 중 일반적인 알고리즘은 무엇을 찾기 쉽지 않은가?
일반적인 알고리즘들은 미로에 대해 많은 정보를 가지고 있지 않은 상황에서 적은 연산만으로도 미로의 특징을 파악 할 수 있고, 상황에 따라 경로를 변환하며 도착점을 찾아 갈 수 있다. 하지만 최단 경로를 찾기란 쉽지 않다.
미로 탐색 알고리즘은 무엇을 기본으로 하여 사용되고 있는가?
마이크로 마우스를 이용한 다수의 미로 경진대회가 개최되어 미로 탐색 알고리즘의 성능이 비교되고 있으며, 미로 탐색 알고리즘은 좌(우)수법, 구심법, 언덕오르기 등을 기본으로 하여 다양한 형태로 적용되어 사용되고 있다. 하지만 미로 탐색알고리즘을 적용하여 테스트하기 위한 소프트웨어 플랫폼이 없어서 프로그램을 직접 개발하거나 하드웨어를 통해 알고리즘의 성능을 테스트해야 하는 불편함을 겪는다.
참고문헌 (6)
윤지녕, "마이크로로봇바이블", 성안당, 2000.
이상용, "인공지능의 세계", 21세기사, pp. 77-79, 2008.
S. Rabin 외, "AI Game Programing Wisdom", 정보문화사, pp. 189-199, 2003.
M. Deloura 외, "Game Programing Gems", 정보문화사, 2000.
E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik, pp. 269-271, 1959.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.