"Easy-Factors Heuristic"

Speaker: Liron Cohen, Hebrew University
Date: Wednesday, 28 December 2011
Time: 12noon
Place: Ross 201

Abstract:

The subject of automated planning -- devising a plan of action to
achieve a goal -- has long been one of the holy grails of artificial
intelligence. Classical planning, a subset of planning problems in
which the dynamics are deterministic, is known to be computationally
hard (PSPACE-complete). Nevertheless, In the last decade there has
been some remarkable achievements in that area, the International
Planning Competition, held biyearly since 1998, is a lively
evidence. Almost all state of the art planners are based on heuristic
search methods. In this talk I will describe a new heuristic that is
derived from the problem description (given in SAS) using various
tools from graph theory. I will quickly overview the concept of
automated planning for state transition systems, planning
representations (PDDL, SAS), knowledge compilation (CG, DTG), graph
theory tools (tree-decomposition, cycle-cutset, node-contraction),
factored planning as CSP, and how to abstract a problem along its
structure.