We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 30 April 2024
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.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
