$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

[국내논문] 휴리스틱 유전 알고리즘 경로 탐색에 광선 추적 알고리즘을 활용한 경로 최적화 연구
Path Optimize Research used Ray-Tracing Algorithm in Heuristic-based Genetic Algorithm Pathfinding 원문보기

한국게임학회 논문지 = Journal of Korea Game Society, v.19 no.6, 2019년, pp.83 - 90  

고정운 (공주대학교 게임디자인학과) ,  이동엽 (공주대학교 게임디자인학과)

초록
AI-Helper 아이콘AI-Helper

휴리스틱 기반의 유전 알고리즘 경로 탐색(H-GAP)은 노드, 에지 정보를 필요로 하지 않기 때문에 기존 경로 탐색 알고리즘의 단점을 보완하고 빠른 속도로 경로 탐색을 수행할 수 있다. 하지만 H-GAP를 이용해 탐색한 경로는 비 노드 기반이기 때문에 불필요한 경로 정보가 포함되어 탐색된 경로가 최적의 경로가 아닐 때도 있다. 본 논문에서는 H-GAP를 이용해 탐색한 경로를 최적화하는 알고리즘을 제안한다. 제안하는 알고리즘은 H-GAP의 경로 탐색이 완료된 후 광선 추적 알고리즘을 이용해 불필요한 경로 정보를 제거하여 경로를 최적화한다.

Abstract ▼ AI-Helper 아이콘AI-Helper

Heuristic based Genetic Algorithm Pathfinding(H-GAP), a method without the need for node and edge information, can compensate the disadvantages of existing pathfinding algorithm, and perform the path search at high speed. However, because the pathfinding by H-GAP is non-node-based, it may not be an ...

주제어

#휴리스틱   #유전 알고리즘   #경로 탐색   #경로 최적화   #광선 추적  

표/그림 (13)

AI 본문요약
AI-Helper 아이콘 AI-Helper

문제 정의

  • 본 논문에서는 휴리스틱 유전 알고리즘 경로 탐색을 이용해 탐색한 경로를 최적화하는 알고리즘을 제안한다. 제안하는 알고리즘은 H-GAP의 경로 탐색이 완료된 후 광선 추적 알고리즘을 이용해 이동 경로 사이에 장애물이 존재하는지 검사하여 장애물이 존재하지 않으면 불필요한 이동 경로 정보를 제거하여 경로를 최적화한다.
본문요약 정보가 도움이 되었나요?

질의응답

핵심어 질문 논문에서 추출한 답변
A* 알고리즘의 특징은? 그 중 게임에서 주로 활용되는 경로 탐색 알고리즘은 경로에 대한 비용을 기반으로 최단거리를 탐색하는 A* 알고리즘이다. A* 알고리즘은 출발노드로부터 현재노드까지의 거리 g(goal)값과 현재노드로부터 목표노드까지의 추정된 거리 h(heuristic)값의 합이 가장 적게 나온 경로를 선택하는 알고리즘으로 최단거리의 탐색 경로 를 제공한다. 하지만 이와 같은 경로 탐색 알고리즘들은 맵에 존재하는 노드, 에지 정보를 데이터 공간으로 구성해야한다.
경로 탐색 알고리즘의 종류는? 경로 탐색 알고리즘은 BFS, DFS, Dijkstra, A*와 같은 것들이 있다. 그 중 게임에서 주로 활용되는 경로 탐색 알고리즘은 경로에 대한 비용을 기반으로 최단거리를 탐색하는 A* 알고리즘이다.
경로 탐색 알고리즘에서 크기가 큰 맵이 적절하지 않은 이유는? 하지만 이와 같은 경로 탐색 알고리즘들은 맵에 존재하는 노드, 에지 정보를 데이터 공간으로 구성해야한다. 또한 맵의 크기가 크면 리스트에 많은 양의 노드들을 저장하고 사용해야 되기 때문에 월드의 크기가 방대하거나 가변적일 때 사용하기 용이하지 않다[5,6,7].
질의응답 정보가 도움이 되었나요?

참고문헌 (12)

  1. Xiaoxiao Guo, Satinder Singh, Honglak Lee, Richard Lewis, Xiaoshi Wang, "Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning", 2014 NIPS, 2014. 

  2. Simon M Lucas, Jialin Liu, Diego Perez-Liebana, "The N-Tuple Bandit Evolutionary Algorithm for Game Agent Optimisation", 2018 Computer Science, 2018. 

  3. Carlos Fuentes, "Hierarchical Path Finding to Speed up Crowd Simulation using Navigation Meshes", 2015LAJC. 2015. 

  4. Sunglok Choi, Jae-Yeong Lee, Wonpil Yu, "Fast Any-angle Path Planning on Grid Maps with Non-collision Pruning", 2010 IEEE International Conference, Dec 2010. 

  5. Rudiger Ebendt, Rolf Drechsler, "Weighted A* search-unifying view and application", 2009 Artificial Intelligence, Vol.173, pp.1310-1342, 2009. 

  6. Sung-hyun Cho, "Reducing Search Space of A* Algorithm Using Obstacle Information", Journal of Korea Game Society 2015, pp.179-188, Aug 2015. 

  7. A. Nash, K. Daniel, S. Koenig, A. Felner, "Theta*: Any-angle path planning on grids", in Proceedings of AAAI Conference on Artificial Intelligence(AAAI), 2007. 

  8. Jung-Woon Ko, Dong-Yeop Lee, "Path-finding Algorithm using Heuristic-based Genetic Algorithm", Journal of Korea Game Society 2017, pp.123-132, Oct 2017. 

  9. Hak-su Lee, Don-jung Choi, Hye-wuk Jung, Jee-hyong Lee, "Intelligent Tutoring System based on Genetic Algorithm", Proceedings of Korea Institute of Intelligent Systems Fall Conference 2010, pp67-69, Nov 2010. 

  10. Chang Wook Ahn, R.S. Ramakrishna, "A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations", IEEE Transactions of Evolutionary Computation 2002, Vol.6, 2002. 

  11. H. Scharsach, "Advanced GPU Raycasting", Proc. of SCCG, 2005. 

  12. Jeong-won Ko, Sung-jun Park, "Path-Plan Algorithm using Collision Line Search Process", Proceedings of Korea Game Society Spring Conference 2012, pp.249-254, June 2012. 

저자의 다른 논문 :

관련 콘텐츠

오픈액세스(OA) 유형

FREE

Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문

이 논문과 함께 이용한 콘텐츠

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로