Name
Abstract | ||
|---|---|---|
Complex features, such as temporal dependencies and numerical cost constraints, are hallmarks of real-world planning problems. In this article, we consider the challenging problem of cost-sensitive temporally expressive (CSTE) planning, which requires concurrency of durative actions and optimization of action costs. We first propose a scheme to translate a CSTE planning problem to a minimum cost (MinCost) satisfiability (SAT) problem and to integrate with a relaxed parallel planning semantics for handling true temporal expressiveness. Our scheme finds solution plans that optimize temporal makespan, and also minimize total action costs at the optimal makespan. We propose two approaches for solving MinCost SAT. The first is based on a transformation of a MinCost SAT problem to a weighted partial Max-SAT (WPMax-SAT), and the second, called BB-CDCL, is an integration of the branch-and-bound technique and the conflict driven clause learning (CDCL) method. We also develop a CSTE customized variable branching scheme for BB-CDCL which can significantly improve the search efficiency. Our experiments on the existing CSTE benchmark domains show that our planner compares favorably to the state-of-the-art temporally expressive planners in both efficiency and quality. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2542182.2542200 | ACM TIST |
Keywords | Field | DocType |
parallel planning semantics,mincost sat,cste customized variable,optimize temporal makespan,mincost sat problem,real-world planning problem,challenging problem,cste planning problem,existing cste benchmark domain,temporally expressive planning,sat-based approach,temporal dependency,planning,satisfiability | Concurrency,Computer science,Satisfiability,Planner,Theoretical computer science,Artificial intelligence,Branching (version control),Expressivity,Conflict-Driven Clause Learning,Mathematical optimization,Job shop scheduling,Machine learning,Semantics | Journal |
Volume | Issue | ISSN |
5 | 1 | 2157-6904 |
Citations | PageRank | References |
1 | 0.35 | 65 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qiang Lu | 1 | 11 | 2.37 |
| Ruoyun Huang | 2 | 111 | 7.24 |
| Yixin Chen | 3 | 4326 | 299.19 |
| You Xu | 4 | 246 | 10.63 |
| Weixiong Zhang | 5 | 1458 | 119.03 |
| Guoliang Chen | 6 | 305 | 46.48 |