The Department of Computer Science at the University of Cyprus cordially invites you to the PhD Defense entitled:
Advances in SAT-Based Planning
Speaker: Mr. Andreas Sideris
Planning is a difficult problem. Even in its simplest forms it is computationally intractable. Although it is unlikely to be able to plan efficiently in the general case, good heuristics and strong constraint propagation methods are valuable techniques for tackling large planning problems. Indeed, some modern planners transform planning into a constraint satisfaction problem, such as a boolean formula, and then solve it by invoking a satisfiability, constraint or pseudo-boolean solver. Many other planners solve the problem by guiding the search using powerful heuristics that are automatically extracted from the planning domain. In the context of this work we first implemented SMP, a novel way of transforming a planning domain into a propositional boolean formula (SAT). We prove both theoretically and experimentally that the constraint propagation engines of the modern SAT solvers propagate the constraints much more efficiently in SMP than in previous transformations. We then use the SAT encoding of SMP in the PSP planner. PSP seeks to maximize the number of goals that can be achieved using the solving and expand method. Although PSP cannot guarantee optimality as SMP, it often generates sub-optimal plans of high quality for planning problems that are beyond the reach of SMP and other SAT-based planners. A drawback of the PSP planner is its limited scalability, as the instances that arise from large planning problems are often too hard for SAT solvers. This holds true for all planners based on the solve and expand method, as the size of the SAT instance grows monotonically with the planning horizon. To address this problem we developed the PSP-H planning system, that extends PSP by combining two powerful techniques that aim at decomposing a planning problem into smaller subproblems, so that the instances that need to be solved do not grow prohibitively large. The first technique turns planning into a series of boolean optimization problems, each seeking to maximize the number of goals that are achieved within a limited planning horizon. This is coupled with a second technique that directs search towards a state that satisfies all goals. Experimental results demonstrate that PSP-H is a competitive planning algorithm.
Andreas Sideris is a PhD candidate at the Department of Computer Science of the University of Cyprus under the supervision of associate professor Yannis Dimopoulos. He completed his undergraduate studies at the Department of Computer Science of the University of Cyprus in 2002 and his MSc studies at the same department in 2005. His research interests are in Artificial Intelligence, focusing on constraint programming (CP), constraint optimization, SAT and propositional planning. He works the last 12 years as a programmer/analyst (C & SQL developer) in the IT department of Hellenic bank.
|Other Presentations Web: https://www.cs.ucy.ac.cy/colloquium/presentations.php|
|Colloquia Web: https://www.cs.ucy.ac.cy/colloquium/|