Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 Search Spaces
- 3 Blind Search
- 4 Heuristic Search
- 5 Stochastic Local Search
- 6 Algorithm A* and Variations
- 7 Problem Decomposition
- 8 Chess and Other Games
- 9 Automated Planning
- 10 Deduction as Search
- 11 Search in Machine Learning
- 12 Constraint Satisfaction
- Appendix: Algorithm and Pseudocode Conventions
- References
- Index
2 - Search Spaces
Published online by Cambridge University Press: 30 April 2024
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 Search Spaces
- 3 Blind Search
- 4 Heuristic Search
- 5 Stochastic Local Search
- 6 Algorithm A* and Variations
- 7 Problem Decomposition
- 8 Chess and Other Games
- 9 Automated Planning
- 10 Deduction as Search
- 11 Search in Machine Learning
- 12 Constraint Satisfaction
- Appendix: Algorithm and Pseudocode Conventions
- References
- Index
Summary
In this chapter we lay the foundations of problem solving using first principles. The first principles approach requires that the agent represent the domain in some way and investigate the consequences of its actions by simulating the actions on these representations. The representations are often referred to as models of the domain and the simulations as search. This approach is also known as model based reasoning, as opposed to problem solving using memory or knowledge, which, incidentally, has its own requirements of searching over representations, but at a sub-problem solving retrieval level.
We begin with the notion of a state space and then look at the notion of search spaces from the perspective of search algorithms. We characterize problems as planning problems and configuration problems, and the corresponding search spaces that are natural to them. We also present two iconic problems, the Boolean satisfiability problem (SAT) and the travelling salesman problem (TSP), among others.
In this chapter we lay the foundations of the search spaces that an agent would explore.
First, we imagine the space of possibilities. Next, we look at a mechanism to navigate this space. And then in the chapters that follow we figure out what search strategy an algorithm can use to do so efficiently.
Our focus is on creating domain independent solvers, or agents, which can be used to solve a variety of problems. We expect that the users of our solvers will implement some domain specific functions in a specified form that will create the domain specific search space for our domain independent algorithms to search in. In effect, these domain specific functions create the space, which our algorithm will view as a graph over which to search. But the graph is not supplied to the search algorithm upfront. Rather, it is constructed on the fly during search. This is done by the user supplied neighbourhood function that links a node in this graph to its neighbours, generating them when invoked. The neighbourhood function takes a node as an input and computes, or returns, the set of neighbours in the abstract graph for the search algorithm to search in.
- Type
- Chapter
- Information
- Search Methods in Artificial Intelligence , pp. 29 - 46Publisher: Cambridge University PressPrint publication year: 2024