The home page of the

 

AAAI-06 workshop on Heuristic Search, Memory Based Heuristics and Their applications (W9)

 

Page maintained by:  Ariel Felner – email:  felner@bgu.ac.il

 

Last modified: June 13, 2006

 

List of accepted papers below. Exact schedule below.

 

Heuristic Search, Memory-based Heuristics and Their Applications

 

Time and Place

 

The workshop will take place on July 17, 2006 in Boston during the AAAI-06 events. We are W9 in the AAAI-06 workshop list.

 

General

 

 

Heuristic search is a well established, fundamental field of research in Artificial Intelligence. Many hard problems in Artificial Intelligence can be modeled as pathfinding in a state-space graph. An intelligent search will be guided by heuristics so as to solve problems quickly.

 

In the past decade we have seen a large increase in the size of computer memories and disk storage. This has led to significant advances in heuristic search, with many new methods being introduced to better utilize the large memory and disk storage. Foremost among these are methods related to Pattern Databases, which are large lookup tables stored in memory that contain heuristic estimates based on exact solutions to subproblems of the original problem. Other methods were introduced to conduct search using disk space as a fast on-line working memory. This significantly increases the amount of available memory for the different tables and queues maintained by search algorithms and therefore larger problems can now be solved. All these new techniques greatly advance the strength of heuristic search and many problems can be solved orders of magnitude faster than before. 

 

Traditionally, heuristic search and pattern databases have been used to solve combinatorial puzzles. Recently we have seen a large expansion of their use, with applications in other fields of Artificial Intelligence and Computer Science such as planning, model checking, dynamic programming and weighted logical inference. 

 

The aim of this workshop is to discuss new achievements in heuristic search, their mutual influence, and their applicability to a large spectrum of problems and areas of Artificial Intelligence and Computer Science.

 

Topics

 

Topics include, but are not limited to the following:

v     Heuristic search algorithms

v     Admissible heuristics

v     Pattern databases -  new  understanding, advances and applications

v     Using disk space to speed up search

v     Applying these techniques to a broader spectrum of AI  and  computer science problems

v     Of particular interest are methods and applications that use heuristic-guided search in new fields of research such as planning, dynamic programming etc.

 

Format

 

The workshop will consist of invited speakers, presentations of selected submitted technical work, a poster session and a panel-led general discussion. One of the major intentions of this workshop is to create interaction between the participants. Therefore, a significant weight will be given to the poster session and the general discussion.

 

Invited speaker

 

Richard E. Korf, University of California Los-Angeles. Title of talk: "Recent Advances in Heuristic Search".

 

Attendance

 

We expect 25-50 attendees. Authors of accepted papers/posters will be automatically invited. Other invitations will be sent on a personal/request basis.

 

Workshop Chairs

 

Ariel Felner 
Ben-Gurion University of the Negev, Beer-Sheva, Israel, 84105
Telephone: +972-54-7548600. Fax: +972-3-9794213
E-mail:  felner@bgu.ac.il

 

Robert C. Holte

Computing Science Department, University of Alberta, Edmonton, Canada, T6G 2E8

Telephone +1-780-4923105. Fax: +1-780-4921071

E-mail:  holte@cs.ualberta.ca

 

Hector Geffner

UPF, Paseo de Circunvalacion 8,08003 Barcelona,  SPAIN

Telephone +34-93-5422563. Fax: +3- 93-5422451

Email: hector.geffner@upf.edu

 

Important dates

 

Submission deadilne:                            April 21, 2006
Notification of acceptance:                April 24,   2006

Camera-ready copy deadline:          May 17, 2006

Our  workshop:                                      July 17, 2006

AAAI main conference:                      July 18-20, 2006

 

Accepted papers

 

1) Sequential and Parallel Algorithms for Frontier A* with Delayed Duplicate Detection.  Robert Niewiadomski, Jose Nelson Amaral, and Robert C. Holte

2) Dual Search in Permutation State Spaces. Uzi Zahavi, Ariel Felner, Robert C Holte and Jonathan Schaeffer

3) Recent Advances in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem. Richard E. Korf and Ariel Felner

4) Domain Independent Structured Duplicate Detection. Rong Zhou and Eric A. Hansen

5) ITSA*: Iterative Tunneling Search with A*. David Furcy

6)  Conflict Directed Backjumping for MAX-CSP. Roie Zivan and Amnon Meisels

7) LAO*, RLAO* or BLAO*. Peng Dai and Judy Goldsmith

8) An Empirical Evaluation of Automated Knowledge Discovery in a Complex Domain. Jay H. Powell and John D. Hastings

9) Improving Relaxed Planning Graph Heuristics for Metric Optimization. Raquel Fuentetaja, Daniel Borrajo and Carlos Linares

10) And/Or Graph Search for Genetic Linkage Analysis. Radu Marinsecu and Rina Dechter

11) Integrating Action Preconditions Difficulty within the Relaxed Plan Heuristic Measure, Tomas de la Rosa and Raquel Fuentetaja

12) A memory Based RASH Optimizer. Mauro Brunato, Roberto Battitiand and Srinvas Pasupuleti

13) Automated Pattern Database Design. Stefan Edelkamp.

14) Parallel Breadth-First Heuristic Search on a Shared Memory Architecture. Yang Zhang and Eric Hansen

 

Workshop Schedule

Session 1.  Chair:  Ariel Felner

 

08:30-8:50 

Reception and gathering

 

8:50-9:05

Opening remarks.

Ariel Felner

09:05-9:55 

Invited Talk: Recent Advances in Heuristic Search

Richard E. Korf

9:55-10:20

Automated Pattern Database Design

Stefan Edelkamp

 

10:20-10:30

Dual Search in Permutation State Spaces

Uzi Zahavi, Ariel Felner, Robert C. Holte and Jonathan Schaeffer 

 

10:30-11:00      Coffee break

 

Session 2.  Chair:  Robert C. Holte

 

11:00-11:25

ITSA*: Iterative Tunneling Search with A*

David Furcy 

11:25-11:35

Domain Independent Structured Duplicate Detection

Rong Zhou and Eric Hansen

11:35-12:00

Parallel Breadth-First Heuristic Search on  a Shared Memory Architecture. 

Yang Zhang and Eric Hansen

12:00-12:10

Sequential and Parallel Algorithms for Frontier A*  with Delayed Duplicate Detection

Robert Niewiadomski, Jose Nelson Amaral, and Robert C. Holte

12:10-12:35

A memory Based RASH Optimizer

Mauro Brunato, Roberto Battitiand and Srinvas Pasupuleti   

12:35-14:00      Lunch break

Session 3.  Chair:  Hector Geffner

 

14:00-14:30

Tutorial: Coarse-to-Fine Dynamic Programming

Chris Raphael

14:30-14:55

And/Or Graph Search for Genetic Linkage Analysis

 Radu Marinsecu and Rina Dechter

14:55-15:20

LAO*, RLAO* or BLAO*.

Peng Dai and Judy Goldsmith  

 

15:20-15:30

An Empirical Evaluation of Automated Knowledge Discovery in  a Complex Domain

Jay H. Powell and John D. Hastings

 

15:30-16:00      Coffee break

 

Session 4.  Chair: Ariel Felner

 

16:00-16:25

Conflict Directed Backjumping for MAX-CSP

Roie Zivan and Amnon Meisels

16:25-16:35

Improving Relaxed Planning Graph Heuristics for    Metric Optimization

 Raquel Fuentetaja, Daniel Borrajo and Carlos Linares

16:35-16:45

Integrating Action Preconditions Difficulty within the  Relaxed Plan Heuristic Measure

Tomas de la Rosa and Raquel Fuentetaja

16:45-17:45

Closing discussion                                                      

 

Leader: Robert C. Holte.

 

 

Workshop Committee

 

Blai Bonet                   Universidad Simón Bolívar,  Venezuela

Stefan Edelkamp       Universität Dortmund, Germany       

Ariel Felner                Ben-Gurion University, Israel                            (co-chair)

Jeremy Frank            NASA Ames Research Center, USA

David Furcy                University of Wisconsin (Oshkosh), USA

Hector Geffner           UPF, Paseo de Circunvalacion,  SPAIN           (co-chair)

Eric Hansen                Mississippi State University, USA
Patrik Haslum              Linköping University, Sweden

Robert Holte               University of Alberta, Edmonton, Canada       (co-chair)

Richard Korf               University of California Los Angeles, USA 

Jonathan Schaeffer    University of Alberta, Edmonton, Canada
Rong Zhou                   Palo Alto Research Center, USA
Weixiong Zhang          Washington University, USA

 

Workshop URL

 

http://www.ise.bgu.ac.il/faculty/felner/workshop/

 

Related events

 

We would like to inform potential attendees that AAAI-06 will also have a separate related workshop on “learning for search”. That workshop will be held on another day to enable interested people to attend both workshops if they so wish.

 

Related links

 

A Tutorial about heuristics titled: "Where do heuristics come form" by Robert Holte.

 

If you want to add a relevant link to this page please email Ariel Felner.

 

Submission requirements

 

We welcome submissions of full technical papers as well as statements of interest – all describing work relevant to the topics of the workshop. Submissions are accepted in PDF format only, using the standard AAAI formatting guidelines . Technical papers are encouraged to be 6 pages in length but can be anything between 2 to 8 pages. Statements of interest should be either one or two pages. All submissions will be reviewed by multiple reviewers for quality and relevance. The review process is not blind so authors do not have to hide their identities.  The submission deadline was March 31, 2006 but to cope with the general policy of AAAI workshops it was postponed until after the AAAI-06 notification date so it is now set to April 17, 2006. However, we encourage submissions to be as early as possible.  Please submit your papers to Ariel Felner by email only to: felner@bgu.ac.il.

 

Multiple submission policy

 

We have no problem with multiple submissions to other venues such as conferences or journals as long as the paper describes new work related to the topics of the workshop.