최적 계획생성을 위한 동작비용 기반의 휴리스틱
Action Costs-based Heuristics for Optimal Planning
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
Highly informative admissible heuristics can help to conduct more efficient search for optimal solutions. However, in general, more informative ones of heuristics from planning problems requires lots of computational effort. To address this problem, we propose an Delete Relaxation based Action Costs-based Planning Graph(ACPG) and Action Costs-based Heuristics for solving optimal planning problems more efficiently. The ACPG is an extended one to be applied to can find action costs between subgoal & goal conditions from the Relaxed Planning Graph(RPG) which is a common means to get heuristics for solving the planning problems, Action Costs-based Heuristics utilizing ACPG can find action costs difference between subgoal & goal conditions in an effective way, and then consider them to estimate the goal distance. In this paper, we present the heuristics algorithm to compute Action Costs-based Heuristics, and then explain experimental analysis to investigate the efficiency and the accuracy of the Action Costs-based Heuristics.
Abstract
Highly informative admissible heuristics can help to conduct more efficient search for optimal solutions. However, in general, more informative ones of heuristics from planning problems requires lots of computational effort. To address this problem, we propose an Delete Relaxation based Action Costs-based Planning Graph(ACPG) and Action Costs-based Heuristics for solving optimal planning problems more efficiently. The ACPG is an extended one to be applied to can find action costs between subgoal & goal conditions from the Relaxed Planning Graph(RPG) which is a common means to get heuristics for solving the planning problems, Action Costs-based Heuristics utilizing ACPG can find action costs difference between subgoal & goal conditions in an effective way, and then consider them to estimate the goal distance. In this paper, we present the heuristics algorithm to compute Action Costs-based Heuristics, and then explain experimental analysis to investigate the efficiency and the accuracy of the Action Costs-based Heuristics.
참고문헌 (12)
- B. Bonet, "Planning as Heuristic Search", pp.5~33 (2001), Artificial Intelligence
- J. Hoffmann, "The FF Planning System: Fast Plan Generation through Heuristic Search", Journal of AI Research, 14, pp.253~302 (2001)
- 김현식, "최적 계획수립을 위한 확장된 그래프 기반의 휴리스틱", 정보과학회 컴퓨팅의 실제 논문지, 17(12), pp.667~671 (2011), 한국정보과학회
- 김현식, "효율적인 계획 수립을 위한 동작-기반의 휴리스틱", 한국산학기술학회논문지, 16(9), pp.6290~6296 (2015), 한국산학기술학회[DOI]
- D. Bryce, "A Tutorial on Planning Graph-Based Reachability Heuristics", AI Magazine, 28(1), pp.47~83 (2006)
- Improving Relaxed Plan-Based Heuristics via Simulated Execution of Relaxed-Plans, "D. Cai", ICAPS, ~ (2009)
- P. Haslum, "Admissible Heuristics for Optimal Planning", AIPS2000, pp.140~149 (2000)
- S. Russell, "Artificial Intelligence: A modern Approach" (2010), PeasonEducation
- E. Keyder, "Set Additive and TSP Heuristics for Planning with Action Costs and Soft Goals", ICAPS (2007)
- 김태경, "보안 및 효율성을 고려한 관광 예약 정보 시스템", (사)디지털산업정보학회 논문지, 11(2), pp.67~72 (2015), (사)디지털산업정보학회[DOI]
- 차시호, "서비스 오케스트레이션 기반 사용자 맞춤형 IoT 서비스의 설계 및 구현", (사)디지털산업정보학회 논문지, 11(3), pp.21~29 (2015), (사)디지털산업정보학회[DOI]
- A. Blum, "Fast Planning through Planning Graph Analysis", Artificial Intelligence, 90, pp.281~300 (1997)