PhD Seminar Course on

Heuristic Search

Cagliari, Tuesday, June 10/12, 2008

Instructor: Carlos Linares Lopez
University Carlos III of Madrid
Enhancing Pattern Databases with Perimeter Search
Duration: 2
Schedule: Tuesday, June 10, 2008, h15.00-17.00
Venue: AULA V
Topics: Pattern databases were a major breakthrough in heuristic search by solving hard combinatorial problems various orders of magnitude faster than state-of-the-art techniques at that time. Since then, they have received a lot of attention. Moreover, pattern databases are also researched in conjunction with other domain-independent techniques for solving planning tasks. However, they are not the only technique for improving heuristic estimates. Although more modest, perimeter search can also lead to significant improvements in the number of nodes expanded and overall running time. Therefore, whether they can be combined or not is a natural and interesting issue. While other researchers have recently proven that a joint application of both ideas (termed as multiple goal) leads to no progress at all, it will be shown in this talk that there are other alternatives for putting both techniques together. In this talk, multi-valued pattern databases will be discussed for the first time and it will be shown that they can still improve the performance of standard (or single-valued) pattern databases in practice.
Heuristic Hill-Climbing as Markov Processes
Duration: 2
Schedule: Thursday, June 12, h10.00-12.00
Venue: AULA Z
Topics: The purpose of this research is twofold: on the one hand, modelling the hill-climbing heuristic search algorithm as a stochastic process serves for deriving interesting properties about its expected performance; on the other hand, the probability that a hill-climbing
search algorithm ever fails when approaching the target node (i.e., it does not find a descendant with a heuristic value strictly lower than the current one) can be considered as a pesimistic measure of the accuracy of the heuristic function guiding it. Thus, in this talk, it is suggested to model heuristic hill-climbing search algorithms with Markov chains in order to fulfill these goals. Empirical results obtained in various sizes of the (n,m)-Puzzle domain prove that this model leads to outstanding predictions.
Assessment: to be defined
Organizer: Prof. Giuliano Armano
Dep. of Electrical and Electronic Engineering
University of Cagliari, Italy