State Space Exploration: Foundations, Algorithms and Applications (SSX)
Third-party funded project
Project title State Space Exploration: Foundations, Algorithms and Applications (SSX)
Principal Investigator(s) Helmert, Malte
Project Members Heusner, Manuel
Keller, Thomas
Eriksson, Salomé
Pommerening, Florian
Röger, Gabriele
Organisation / Research unit Departement Mathematik und Informatik / Artificial Intelligence (Helmert)
Project Website
Project start 01.02.2014
Probable end 31.01.2019
Status Completed

State-space search, i.e., finding paths in huge, implicitly given graphs, is a fundamental problem in artificial intelligence and other areas of computer science. State-space search algorithms like A*, IDA* and greedy best-first search are major success stories in artificial intelligence. However, despite their success, these algorithms have deficiencies that have not been sufficiently addressed in the past:

  1. They explore a monolithic model of the world rather than applying a factored perspective.
  2. They do not learn from mistakes and hence tend to commit the same mistake repeatedly.
  3. For satisficing (i.e., suboptimal) search, the design of the major algorithms like greedy best-first search has been based on rather ad-hoc intuitions.

In this project, we target these three deficiencies. We develop a theory of factored state-space search, a theory of learning from information gathered during search, as well as a decision-theoretic foundation for satisficing search algorithms. Based on these insights, the project aims at designing new state-space search algorithms that improve on the current state of the art.

Keywords state-space search, heuristic search, AI
Financed by Commission of the European Union

MCSS v5.8 PRO. 0.475 sec, queries - 0.000 sec ©Universität Basel  |  Impressum   |