Continuing Plan Quality Improvement by Local Optimisation
Fazlul Hasan Siddiqui
ARTIFICIAL INTELLIGENCE SEMINAR PhD monitoringDATE: 2013-05-29
TIME: 12:30:00 - 13:00:00
LOCATION: NICTA CRL Boardroom (level 2)
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Solution quality and solver efficiency are of particular interest in automated planning. Much progress has been made separately on those two targets, but few planners have the flexibility to trade-off between the efficiency of the solvers and the quality of their solutions. Planners that are able to find plans quickly (for example, greedy heuristic search based planners), usually find plans of poor quality. In contrast, the planners that guarantee solution optimality, or bounded sub-optimality, do not scale up to large problems. Therefore, a gap exists between the capabilities of these two classes of planners. Anytime planners try to strike a balance between (slow) optimal and fast (but non-optimal) planning methods, by finding an initial plan, possibly of poor quality, quickly and then continually finding better plans the more time they are given. But current anytime planners often are not effective at making use of increasing runtime beyond the first few minutes. As an example, the current best approach to anytime planning, LAMA, is based on restarting weighted A* search with a schedule of decreasing weights. However, as the weight used in WA* decreases, it fairly quickly consumes all memory by degenerating into a plain A* search. Therefore, this method does not quite live up to the promise of continually improving plans over time. Therefore, our challenge is to design a planning system that can continue to improve the plan quality even when the current best planners stop improving. We are inspired by the power of local search, in particular, the large neighborhood search for anytime solution quality improvement, and aim to apply this in domain independent planning. The main challenge of identifying good subplans to re-optimise is overcomed by block decomposition of plans, which is a new form of plan decomposition that allows to identify coherent subplans, which are optimised locally.
BIO:
