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.