CS Other Presentations

Department of Computer Science - University of Cyprus

Besides Colloquiums, the Department of Computer Science at the University of Cyprus also holds Other Presentations (Research Seminars, PhD Defenses, Short Term Courses, Demonstrations, etc.). These presentations are given by scientists who aim to present preliminary results of their research work and/or other technical material. Other Presentations serve as a forum for educating Computer Science students and related announcements are disseminated to the Department of Computer Science (i.e., the csall list):

RSS Directions

Presentations Coordinator: Demetris Zeinalipour

PhD Defense: Advances in SAT-Based Planning, Mr. Andreas Sideris (University of Cyprus, Cyprus), Thursday, February 19, 2015, 09:30-10:30 EET.

The Department of Computer Science at the University of Cyprus cordially invites you to the PhD Defense entitled:

Advances in SAT-Based Planning

Abstract:
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.

Short Bio:
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/
	Calendar: https://www.cs.ucy.ac.cy/colloquium/schedule/cs.ucy.pres.2015.sideris.ics