효율적인 계획생성을 위한 그래프 기반의 혼합 휴리스틱
Graph-based Mixed Heuristics for Effective Planning
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Highly informative heuristics in AI planning can help to a more efficient search a solutions. However, in general, to obtain informative heuristics from planning problem specifications requires a lot of computational effort. To address this problem, we propose a Partial Planning Graph(PPG) and Mixed Heuristics for solving planning problems more efficiently. The PPG is an improved graph to be applied to can find a partial heuristic value for each goal condition from the relaxed planning graph which is a means to get heuristics to solve planning problems. Mixed Heuristics using PPG requires size of each graph is relatively small and less computational effort as a partial plan generated for each goal condition compared to the existing planning graph. Mixed Heuristics using PPG can find partial interactions for each goal conditions in an effective way, then consider them in order to estimate the goal state heuristics. Therefore Mixed Heuristics can not only find interactions for each goal conditions more less computational effort, but also have high accuracy of heuristics than the existing max and additive heuristics. In this paper, we present the PPG and the algorithm for computing Mixed Heuristics, and then explain analysis to accuracy and the efficiency of the Mixed Heuristics.
Abstract
Highly informative heuristics in AI planning can help to a more efficient search a solutions. However, in general, to obtain informative heuristics from planning problem specifications requires a lot of computational effort. To address this problem, we propose a Partial Planning Graph(PPG) and Mixed Heuristics for solving planning problems more efficiently. The PPG is an improved graph to be applied to can find a partial heuristic value for each goal condition from the relaxed planning graph which is a means to get heuristics to solve planning problems. Mixed Heuristics using PPG requires size of each graph is relatively small and less computational effort as a partial plan generated for each goal condition compared to the existing planning graph. Mixed Heuristics using PPG can find partial interactions for each goal conditions in an effective way, then consider them in order to estimate the goal state heuristics. Therefore Mixed Heuristics can not only find interactions for each goal conditions more less computational effort, but also have high accuracy of heuristics than the existing max and additive heuristics. In this paper, we present the PPG and the algorithm for computing Mixed Heuristics, and then explain analysis to accuracy and the efficiency of the Mixed Heuristics.
참고문헌 (15)
- 이석준, "행위 온톨로지로부터 로봇 작업 계획 생성", 제어.로봇.시스템학회 논문지, 23(8), pp.650~660 (2017), 제어·로봇·시스템학회[DOI]
- 최병관, "인공지능 객체인식에 관한 파라미터 측정 연구", (사)디지털산업정보학회 논문지, 15(3), pp.15~28 (2019), (사)디지털산업정보학회
- 송호정, "어댑티드 회로 배치 유전자 알고리즘의 설계와 구현", (사)디지털산업정보학회 논문지, 17(2), pp.13~20 (2021), (사)디지털산업정보학회
- B. Bonet, "Planning as Heuristic Search", pp.5~33 (2001), Artifical Intelligence
- J. Hoffmann, "The FF Planning System: Fast Plan Generation through Heuristic Search", Journal of AI Research, 14, pp.253~302 (2001)
- D. Bryce, "A Tutorial on Planning Graph-Based Reachability Heuristics", AI Magazine, 28(1), pp.47~83 (2006)
- D. Cai, "Improving Relaxed Plan-Based Heuristics via Simulated Execution of Relaxed-Plans" (2009), ICAPS
- 김현식, "최적 계획수립을 위한 확장된 그래프 기반의 휴리스틱", 정보과학회 컴퓨팅의 실제 논문지, 17(12), pp.667~671 (2011), 한국정보과학회
- 김현식, "효율적인 계획 수립을 위한 동작-기반의 휴리스틱", 한국산학기술학회논문지, 16(9), pp.6290~6296 (2015), 한국산학기술학회[DOI]
- P. Haslum, "Admissible Heuristics for Optimal Planning", AIPS2000, 140~149 (2000)
- S. Russell, "Artificial Intelligence:A Modern Approach, 3nd Edition" (2010), PeasonEducation
- E. Keyder, "Set Additive and TSP Heuristics for Planning with Action Costs and Soft Goals" (2007), ICAPS
- 김완태, "최적 계획생성을 위한 동작비용 기반의 휴리스틱", (사)디지털산업정보학회 논문지, 13(2), pp.27~34 (2017), (사)디지털산업정보학회[DOI]
- O. Marom, "Utilising Uncertainty for Efficient Learning of Likely-Admissible Heuristics", ICAPS2020, 560~568 (2020)
- A. Blum, "Fast Planning through Planning through Planning Graph Analysis", Artificial Intelligence, 90, pp.281~300 (1997)