Journal of Korea Society of Digital Industry and Information Management (디지털산업정보학회논문지)

Korea Society of Digital Industry and Information Management (디지털산업정보학회)
권호 표지
DOI QR코드

DOI QR Code

Action Costs-based Heuristics for Optimal Planning

최적 계획생성을 위한 동작비용 기반의 휴리스틱

  • 김완태 (서일대학교 정보통신공학과) ;
  • 김현식 (서일대학교 소프트웨어공학과)
  • Received : 2017.05.18
  • Accepted : 2017.06.08
  • Published : 2017.06.30
Download PDF
⟨ Previous Next ⟩

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.

Keywords

References

  1. B. Bonet and H. Geffner, "Planning as Heuristic Search," Artificial Intelligence, 2001, pp.5-33.
  2. J. Hoffmann and B. Nebel, "The FF Planning System: Fast Plan Generation through Heuristic Search," Journal of AI Research, vol14, 2001, pp.253-302.
  3. 김현식.김인철, "최적 계획수립을 위한 확장된 그래프 기반의 휴리스틱," 한국정보과학회, 정보과학회논문지, 제17권 제12호, 2011, pp.667-671.
  4. 김현식, "효율적인 계획 수립을 위한 동작-기반의 휴리스틱," 한국산학기술학회, 한국산학기술학회논문지, 제16권 제9호, 2015, pp.6290-6296. https://doi.org/10.5762/KAIS.2015.16.9.6290
  5. D. Bryce and S. Kambhampati, "A Tutorial on Planning Graph-Based Reachability Heuristics," AI Magazine, vol.28, no.1, 2006, pp.47-83
  6. D. Cai, M. Yin and J. Wang, "Improving Relaxed Plan-Based Heuristics via Simulated Execution of Relaxed-Plans," ICAPS, 2009.
  7. P. Haslum and H. Geffner, "Admissible Heuristics for Optimal Planning," AIPS2000, 2000, pp.140-149.
  8. S. Russell and P.Norving, Artificial Intelligence: A modern Approach, 3nd Edition, PeasonEducation, 2010.
  9. E. Keyder and H. Geffner, "Set Additive and TSP Heuristics for Planning with Action Costs and Soft Goals," ICAPS, 2007.
  10. 김태경, "보안 및 효율성을 고려한 관광 예약 정보 시스템," 디지털산업정보학회, 디지털산업정보학회 논문지, 제11권 제2호, 2015, pp.67-72.
  11. 차시호.류민우, "서비스 오케스트레이션 기반 사용자 맞춤형 IoT 서비스의 설계 및 구현," 디지털산업정보학회, 디지털산업정보학회 논문지, 제11권 제3호, 2015, pp.28-29.
  12. A. Blum and M. Furst, "Fast Planning through Planning Graph Analysis," Artificial Intelligence, vol.90, 1997, pp.281-300. https://doi.org/10.1016/S0004-3702(96)00047-1