Search in Artificial Intelligence and Robotics
Papers from the 2008 AAAI Workshop
David Furcy, Sven Koenig, Wheeler Ruml, Rong ZhouProgram Cochairs
Technical Report WS-08-10 published by The AAAI Press, Menlo Park, California
This technical report is also available in book and CD format.
Contents
Organizing Committee / vii
David Furcy, Sven Koenig, Wheeler Ruml, Rong Zhou
Full Papers
Search Strategies for Scheduling Problems with Optional Activities / 1
Roman Barták
Informed and Probabilistically Complete Search for Motion Planning under Differential Constraints / 3
Kostas E. Bekris, Lydia E. Kavraki
A Fresh Look at Sensor-Based Navigation: Navigation with Sensing Costs / 11
Zahy Bnaya, Ariel Felner, Eyal Shimony, Gal A. Kaminka, Efi Merdler
Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order / 18
Blai Bonet
Recent Results from Analyzing the Performance of Heuristic Search / 24
Teresa M. Breyer, Richard E. Korf
Practical Search Techniques in Path Planning for Autonomous Driving / 32
Dmitri Dolgov, Sebastian Thrun, Michael Montemerlo, James Diebel
Search Techniques for Fourier-Based Learning / 38
Adam Drake, Dan Ventura
Planning in the Face of Frequent Exogenous Events / 45
Christian Fritz, Sheila A. McIlraith
Online Search Cost Estimation for SAT Solvers / 53
Shai Haim, TobyWalsh
Combining Lookahead and Propagation in Real-Time Heuristic Search / 61
Carlos Hernández, Pedro Meseguer
Applying Probabilistic Inference to Heuristic Search by Estimating Variable Bias / 68
Eric I. Hsu, Christian J. Muise, Sheila A. McIlraith, J. Christopher Beck
Heuristic Search for Target Value Path Problem / 76
Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleer, Rong Zhou, Minh Do
Using Swamps to Improve Optimal Pathfinding / 84
Nir Pochter, Aviv Zohar, Jeffrey S. Rosenschein
Multiple Symmetries in Sliding-Tile Puzzles: First Experiments / 92
César Romero, Julio Castillo, Blai Bonet
Learning from Multiple Heuristics / 100
Mehdi Samadi, Ariel Felner, Jonathan Schaeffer
Using Inconsistent Heuristics on A* Search / 106
Nathan R. Sturtevant, Zhifu Zhang, Robert Holte, Jonathan Schaeffer
T_FSP: Forward Stochastic Planning using Probabilistic Reachability / 114
Florent Teichteil-Königsbuch, Guillaume Infantes
Fast and Loose in Bounded Suboptimal Heuristic Search / 120
Jordan T. Thayer, Wheeler Ruml, Ephrat Bitton
On Heavy-tailed Runtimes and Restarts in Rapidly-exploring Random Trees / 127
Nathan A. Wedge, Michael S. Branicky
Exploring Infeasibility for Abstraction-Based Heuristics / 134
Fan Yang
MAP Search in Bayesian Networks Using Joint Bounds / 140
Changhe Yuan, Eric A. Hansen
Predictions and Bounds of IDA* with Conditional Distributions / 147
Uzi Zahavi, Ariel Felner, Neil Burch, Robert C. Holte
Learned Value-Ordering Heuristics for Constraint Satisfaction / 154
Zhijun Zhang, Susan L. Epstein
Combining Breadth-First and Depth-First Strategies in Searching for Treewidth / 162
Rong Zhou, Eric A. Hansen
Research Statements
The Effect of Planning State Space Topology on Search Performance / 169
Blazej Bulka, Marie desJardins, Fusun Yaman
Using Sampling to Dynamically Reconfigure Problem-Solvers / 171
Santiago Franco, Mike Barley
AI Planning Search Time and Space Reduction Technique for the Problem of Web Service Composition / 173
Hossein Rahmani