Backjump from V7 to V4. Nothing left to try! Session of V4 = {V4, V5, V6, V7}. R(V4) = {V4, V7} ind(V4) = {V2, V3} As expected, we back jump to V3 instead of V2. Hooray! Gaschnigs algorithm and graph-based backjumping can be combined to produce conflict-directed backjumping. We will not explore conflict-directed backjumping in this course. 164 Varieties of CSP We have only looked at discrete CSPs with finite domains. These are the simplest. We could also consider: 1. Discrete CSPs with infinite domains: We need a constraint language. For example V3 V10 + 5 Algorithms are available for integer variables and linear constraints. There is no algorithm for integer variables and nonlinear constraints. 2. Continuous domainsusing linear constraints defining convex regions we have linear programming. This is solvable in polynomial time in n. 3. We can introduce preference constraints in addition to absolute constraints, and in some cases an objective function. 165

Artificial Intelligence Knowledge representation and reasoning Reading: AIMA, chapters 7 to 10. 166 Knowledge representation and reasoning We now look at how an agent might represent knowledge about its environment, and reason with this knowledge to achieve its goals. Initially well represent and reason using first order logic (FOL). Aims: To show how FOL can be used to represent knowledge about an environment in the form of both background knowledge and knowledge derived from percepts. To show how this knowledge can be used to derive non-perceived knowledge about the environment using a theorem prover. To introduce the situation calculus and demonstrate its application in a simple environment as a means by which an agent can work out what to do next. Using FOL in all its glory can be problematic. Later well look at how some of the problems can be addressed using semantic networks, frames, inheritance and rules. 167

Knowledge representation and reasoning Earlier in the course we looked at what an agent should be able to do. It seems that all of usand all intelligent agentsshould use logical reasoning to help us interact successfully with the world. Any intelligent agent should: Possess knowledge about the environment and about how its actions affect the environment. Use some form of logical reasoning to maintain its knowledge as percepts arrive. Use some form of logical reasoning to deduce actions to perform in order to achieve goals. 168

Knowledge representation and reasoning This raises some important questions: How do we describe the current state of the world? How do we infer from our percepts, knowledge of unseen parts of the world? How does the world change as time passes? How does the world stay the same as time passes? (The frame problem.) How do we know the effects of our actions? (The qualification and ramification problems.) Well now look at one way of answering some of these questions. FOL (arguably?) seems to provide a good way in which to represent the required kinds of knowledge: it is expressive, concise, unambiguous, it can be adapted to different contexts, and it has an inference procedure, although a semidecidable one. In addition is has a well-defined syntax and semantics. 169