Domain-Independent Cost-Optimal Planning in ASP. Issue 5 (September 2019)

• Record Type: Journal Article
• Authors: SPIES, DAVID; YOU, JIA-HUAI; HAYWARD, RYAN
• Is Part Of: Theory and practice of logic programming. Volume 19:Issue 5/6(2019)
• Page Start: 1124
• Page End: 1142
• Publication Date: 2019-09
• Subjects: Cost-Optimal Planning, -- Answer Set Programming, -- CORE-2 ASP Standard.; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068419000395
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: We investigate the problem of cost-optimal planning in ASP. Current ASP planners can be trivially extended to a cost-optimal one by adding weak constraints, but only for a given makespan (number of steps). It is desirable to have a planner that guarantees global optimality. In this paper, we present two approaches to addressing this problem. First, we show how to engineer a cost-optimal planner composed of two ASP programs running in parallel. Using lessons learned from this, we then develop an entirely new approach to cost-optimal planning, stepless planning, which is completely free of makespan. Experiments to compare the two approaches with the only known cost-optimal planner in SAT reveal good potentials for stepless planning in ASP.