Computer Science notes ⇒ Logic Programming and Artificial Intelligence

There are different factors to consider when considering environments, such as:

• Fully vs. Partially Observable - the completeness of the information about the state of the environment
• Deterministic vs. Non-deterministic - Do actions have a single guaranteed effect (dependent on the state?)
• Episodic vs. Sequential - Is there a link between agent performance in different episodes?
• Static vs. Dynamic - Does the environment remain unchanged except by agent actions?
• Discrete vs. Continuous - is there a fixed finite number of actions and percepts?
• Single agent vs. Multi-agent

A problem representation implicitly defines a search tree. Root is a node containing the initial state. If a node contains s, then for each state s′ in Successors, the node has one child node containing the state s′. Each node in the search tree is called a search node. In practice, it can contain more than just a state, e.g., the path cost from the initial node. Search trees are not just state spaces, as two nodes in a tree can contain the same state.

Search trees could contain infinite paths, which we need to eliminate. This could be due to an infinite number of states, or where the state space contains a cycle. Search trees are always finitary (each node has a finite number of children), since a problem representation has a finite number of operators.

See ADS.

BFS works by expanding the shallowest unexpanded node and is implemented using a FIFO queue.

It is complete, has a time complexity of Ο(b^{d + 1}), space complexity of Ο(b^{d + 1}) and is optimal is all operators have the same cost.

The space complexity is a problem, however, and additionally we can not find the optimal solution if operators have different costs.

This works by expanding the least-cost unexapanded node and is implemented using a queue ordered by increasing path cost. If all the step costs are equal, this is equivalent to BFS.

It is complete if the step cost ≥ ε, has a time complexity where the number of nodes with g ≤ the cost of the optimal solution, Ο(b^ceil(C*/ε)), where C* is the cost of the optimal solution, or Ο(b^d). The space complexity is where the number of nodes with g ≤ cost of the optimal solution Ο(b^ceil(C*/ε)), or Ο(b^d). This is optimal since nodes are expanded in an increasing order of g(n).

This still uses a lot of memory, however.

This works by expanding the deepest unexpanded node, and is implemented using a stack/LIFO queue.

It is not complete, as it could run forever without ever finding a solution is the tree has an infinite depth. It does complete in finite spaces, however. The time complexity is Ο(b^m), which is terrible if m >> d, but if solutions are dense, this may be faster than BFS. The space complexity if Ο(bm), i.e., linear space. It is not optimal.

Depth limited search is DFS with depth limit l. That is, nodes deeper than l will not be expanded.

This solution is not complete, as a solution will only be found if d > l. It has a time complexity Ο(b^l) and a space complexity Ο(bl). Also, the solution is not optimal.

Depth limited search can be made complete using iterative deepening. The implementation of this is:

set l = 0
do
 depth limited search with limit l
 l++
until solution found or no nodes at depth l have children

This does have a lot of repetition of the nodes at the top of the search tree, so it's a class memory vs. CPU trade-off - this is CPU intensive, but only linear in memory. However, with a large b, the overhead is not too great, for example, when b = 10 and d = 5 the overhead is 11%.

IDS is complete, has a time complexity of (d + 1)b⁰ + db¹ + (d - 1)b² + ... + b^d, or Ο(b^d) and a space complexity of Ο(bd). Like BFS, it is optimal if step cost = 1.

Failure to detect repeated states can turn a linear space into an exponential one. Any cycles in a state space will always produce an infinite search tree.

Sometimes, repeated states can be reduced or eliminated by changing the problem representation, e.g., by adding a precondition saying that the inverse of the previous operation is not allowed will eliminate cycles of length 2.

Another way of handing repeated states is by checking whether or not a node is equal to one of its ancestors, and don't add it if it is. For DFS-type algorithms, this is relatively easy to implement as all ancestors are already on the node list, however for other algorithms, this takes Ο(d) to traverse up the node list, or keeping a record of all the ancestors of a node, which consumes a lot of space.

A better way to solve this is to use graph search, which keeps track of all generated states. When a node is removed from the node list (the open list), it is stored on another list (the closed list). The basic version is the same as tree search, but you don't expand a node if it has the same state as one on the closed list. A more sophisticated version is required to retain optimality: If the new node is "cheaper" than its duplicate on the closed list, then the one on the closed list and its descendants must be deleted.

Siblings can still be created, however, so another way would be compare the node to all nodes - this is very expensive, so the normal solution to repeated states is to rewrite the problem representation.

In Greedy Best-First Search, the evaluation function ƒ(n) = h(n), our heuristic (an estimate of cost from n to the nearest goal). In our distance-finding example, this could be the straight line distance. Greedy Best-First Search therefore works by expanding the node that appears to be closest to the goal.

Greedy Best-First Search is not complete, as there a variety of cases where completeness is lost, e.g., it can get stuck in loops. The time complexity is Ο(b^m), but a good heuristic can give dramatic improvement. The space complexity is also Ο(b^m), as all nodes are kept in memory. Greedy best-first search is also not optimal.

Greedy Best-First Search ignores the cost to get to the goal, which loses optimality. We therefore need to consider the cost to get to the node we are at. The basic idea of this is to avoid expanding paths that are already expensive. For this, we update our evaluation function to be ƒ(n) = g(n) + h(n), where g(n) is the cost so far to reach the node n - this is the same as uniform-cost search, therefore we can consider A* search to be a mixture of uniform-cost and greedy best-first search.

Even though the goal may be expanded by a previous expansion, it is never actually considered until it reaches the front of the list, as a more optimal path to the goal may be expanded from a node with a lower current cost.

A* search is sometimes referred to as A-search, however A* does have extra conditions for optimality compared to A. In A*, h(n) must be admissible, which guarantees optimality.

Using A* search, nodes are expanded in order of f value, which gradually adds so-called f-contours of nodes. A contour i has all nodes where f = f_i, where f_i < f_{i + 1}.

A* is complete (unless there are infinitely many nodes with f ≤ ƒ(G) - as in uniform cost search). It also has a time complexity that is exponential in relative error in h and the length of the solution, and the space complexity is that of keeping all nodes in memory. It is also optimal.

A heuristic h(n) is admissible if ∀n h(n) ≤ h*(n), where h*(n) is the true cost to reach the nearest goal state from n, i.e., an admissible heuristic never overestimates the cost to reach the goal (i.e., it is optimistic).

For proof of optimality,
see lecture slides.

Theorem: If h(n) is admissible, A* using tree-search is optimal. That is, there is no goal node that has less cost than the first goal node that is found.

A heuristic is consistent if, for every node n, a successor n′ of n generated by any action a, h(n) ≤ c(n, a, n′) + h(n′), where c(n, a, n′) is the cost of getting from node n to n′ via action a. Using the triangle inequality (that is, the combined length of any two sides is always longer than the length of the remaining side), we have ƒ(n′) ≥ ƒ(n), i.e., ƒ(n) is non-decreasing along any path.

Theorem: If a heuristic is consistent, then it is admissible. The reverse is not strictly true, but it is very hard to come up with admissible heuristic that is not admissible.

Theorem: If h(n) is consistent, A* using graph-search is optimal. The proof for this is similar to that for uniform cost.

Admissible heuristics can be discovered by relaxing the problem to a simpler form (i.e., removing some constraints so it becomes easier to solve). If we have two heuristics where h₁ is a relaxed form of h₂ and both are admissible, then ∀n h₂(n) ≥ h₁(n), then we can say that h₂ dominates h₁.

Theorem: If h₂ domaintes h₁ then A* with h₁ expands at least every node expanded by A* with h₂.

As discussed above, we can discuss a declarative representation language using a syntax and a semantics. For propositional logic, our syntax consists of a lexicon and a grammar.

The lexicon (non-logical symbols) of propositional logic consists of a set of proposition symbols. Throughout the examples, we can assume that, P, Q, R, S and T are among the propositional symbols. The logical symbols of propositional logic are ¬, ∨, ^, →, ↔. We can then define the sentences of propositional logic as:

• If α is a proposition letter, then α is an atomic sentence
• If α and β are sentences, then (¬α), (α ∨ β), (α ^ β), (α → β) and (α ↔ β) are molecular sentences.

The above is an official definition, but we can take certain shortcuts to reduce clutter and to make writing logical statements easier. We can assign to connectives, from high to low, ¬, &or, ∧, →, ↔. We can then take advantage of this to omit paranthesis when no ambiguity results. Additionally, we can take the connectives ^ and ∨ to have an arbitary arity of two or more.

We call a sentence of the form α ∨ β a disjunction, where α and β are its disjuncts. A sentence of the form α ^ β is a conjunction, where α and β are its conjuncts.

We also need to consider the semantics of propositional logic. In propositional logic, a model is a function that maps every proposition letter to a truth value, either TRUE or FALSE. If α is a sentence, and I is a model, then [[α]]^I is the semantic value of α relative to model I. [[α]]^I is then defined as follows:

• If α is an atomic sentence, then [[α]]^I = I(α)
• If α is (¬β) then [[α]]^I = { TRUE if [[β]]^I = FALSE, FALSE otherwise
• If α is (β ∨ γ) then [[α]]^I = { TRUE if [[β]]^I or [[γ]]^I, FALSE otherwise
• If α is (β ^ γ) then [[α]]^I = { TRUE if [[β]]^I = TRUE and [[γ]]^I = TRUE, FALSE otherwise
• If α is (β → γ) then [[α]]^I = { TRUE if [[β]]^I = FALSE or [[γ]]^I = TRUE, FALSE otherwise
• If α is (β ↔ γ) then [[α]]^I = { TRUE if [[β]]^I = [[γ]]^I, FALSE otherwise

An alternate way of thinking is if one thinks of the logical connectives as truth functions, which maps a pair of arguments to true or false in every model (which is why it is considered a logical symbol). Thus, we could define: [[(α ^ β)]]^I = [[^]]([[α]]^I, [[β]]^I).

Theorem 1: Let A and A′ be two equivalent formulas. If B is a formula that contains A as a subformula, then B is logical equivalent to the formula that results from substituting A′ for A in B.

Theorem 2: Two sentences, A and B, are logically equivalent if and only if then sentence A ↔ B is valid.

Theorem 3: Let A, A₁, ..., A_n be sentences. Then {A₁, ..., A_n} entails A if and only if the sentence A₁ ^ ... ^ A_n → A is valid.

Again, we start by considering the syntax of FOPC. The lexicon (non-logical symbols) of FOPC consist of the disjoint sets of a set of predicate symbols, each having a specified arity ≥ 0 (we often refer to symbols with arity 0 as proposition symbols - propositional logic is where all predicates have no arguments), and a set of function symbols, each having a specified arity ≥ 0 (function symbols of arity 0 are often called individual symbols, or often a a misnomer, constants), and finally a set of variables.

The logical symbols of FOPC consist of the quantifiers ∀ and ∃, and the logical connectives ¬, ^, ∨, → and ↔.

We can define the terms of FOPC as individual symbols, variables, and function symbols, where if ƒ is a function symbol of arity n and t₁, ..., t_n are terms then ƒ(t₁, ..., t_n) is a term.

The formulas of FOPC are defined as atomic formulas, where if P is a predicate symbol of arity n and t₁, ..., t_n are terms, then P(t₁, ..., t_n) is an atomic formula, and as molecular formulas, where if α and β are formulas, then ¬α, (α ∨ β), (α ^ β), (α → β) and (α ↔ β) are molecular formulas. Additionally, if x is a variable and α is a formula, then (∀xα) and (∃xα) are molecular formulas.

We can consider variables to be either bound or free. We say that a variable x occuring in a formula α is bound in α if it occurs within α as a subformula of the form ∀xβ or ∃xβ. Otherwise we call the variable free. We call a formula α a sentence if there is no free occurance of a variable.

Sentences have truth values, as FOPC is based on compositional semantics, where the total truth value is equal to the sum of its parts.

Like with propositional logic, we can drop paranthesis if no ambiguity results, and we often give connectives and quantifiers precedence from high to low (¬, ∨, ^, →, ↔, ∀, ∃). We often specifiy ∀x₁, x₂, ..., x_n as a shorthand for ∀x₁, ∀x₂, ..., ∀x_n, and similarly for ∃.

If a term or formula contains no variables, we refer to it as ground. α ∨ β is a disjunction, where α and β are its disjuncts and α ^ β is a conjunction, where α and β are its conjuncts.

We can also consider first order propositional logic, which is first order predicate calculus with equality. The equality symbol "=" is both a logical symbol and a binary predicate symbol. Atomic formulas using this predicate symbol are usually written as (t₁ = t₂), instead of =(t₁, t₂). Also, we usually write (t₁ ≠ t₂) instead of ¬(t₁ = t₂).

To consider the semantics of FOPC, we define a pair (D, A), where D is a potentially infinite non-empty set of individuals called the domain and A is a function that maps each n-ary function symbol to a function from Dⁿ to D and each n-ary predicate symbol to a function Dⁿ to {TRUE, FALSE}. Individual symbols (function symbols of 0-arity) always map to an element of D and a predicate symbol of arity 0 (i.e., a proposition symbol) is mapped to TRUE or FALSE.

When we are considering formula with free variables, the truth value depends not only on what model we are considering, but what values we give to these variables. For this purpose, we will consider the value of an expression relative to a model and a function from variables to D. Such a function is called a value assignment.

For a full semantic
definition of all symbols
see lecture notes.

If α is an expression or a symbol of the language, then [[α]]^{I, g}is the semantic value of α relative to model I and value assignment g. If g is a value assignment, then g[x ↵ i] is the same value assignment, with the possible exception that g[x → i](x) = i.

Many proof systems for propositional logic employ a wide variety of rules. Commonly used rules include and-introduction - from any two sentences α and β, derive α ^ β - and modus ponens - from any two sentences of the form α and α → β, derive β.

If we consider the following argument, we can show that the conclusion is derived from the premises:

A
A → B
A → C
B ^ C

Then we can derive the result as follows:

1. A - premise
2. A → B - premise
3. A → C - premise
4. B - modus ponens from 1 and 2
5. C - modus ponens from 1 and 3
6. B ^ C - and-introduction from 4 and 5

Derivations can also be represented as trees and as directed, acyclic graphs, e.g.,

We can say a proof system is sound if every sentence that can be derived from a set of premises is entailed by the premises, and that a proof system is complete if every sentence that is entailed by a set of premises can be derived from the set of premises. Therefore, we can consider soundness and completeness when the set of sentences derivable from a set of premises is identical to the set of sentences entailed by the premises. This is obviously a desirable property.

An inference rule of the form: From α₁, ..., α_n derive β, is sound if {α₁, ..., α_n} entails β. Modus ponens and and-introduction are sound.

Some proofs are linear, that is when the shape of their tree looks as follows:

We can also reason backwards, where a proof can be turned upside down and we start from the conclusion and work towards [], the truth condition.

Each premise in a propositional Horn clause argument is a definite clause (α₁ ^ ... ^ α_n) → β, where n ≥ 0 and each α_i and β is atomic. If n = 0, then we have that → β is a definite clause, and we usually write this as simply β.

The conclusion in a propositional Horn clause argument is a conjunction of atoms α₁ ^ ... ^ α_n. As a special case, we can consider [] when n = 0. We call this the empty conjunction and it is true in all models.

The SLD resolution inference rule is used to derive a goal clause from a goal clause and definite clause.

From the goal clause G₁ ^ ... ^ G_{i - 1} ^ G_i ^ G_{i + 1} ^ ... ^ G_n (n ≥ 1) and the definite clause B₁ ^ ... ^ B_m → H (m ≥ 0) we can derive the goal clause G₁ ^ ... ^ G_{i - 1} ^ B₁ ^ ... ^ B_m ^ G_{i + 1} ^ ... ^ G_n, provided that H and G_i are identical.

Because of their special form, SLD proofs are often shown simply as:

A ^ C
B ^ D ^ C (4)
E ^ D ^ C (3)
E ^ C (2)
C (1)
[] (5)

Where the number following is the number of the premise that SLD resolution was applied to.

The element of the goal clause that is chosen to have SLD resolution applied to it is chosen using a selection function, and the most common selection functions are the leftmost and rightmost selection functions.

We have the following properties about SLD inference:

1. The SLD inference rule is sound and complete for propositional Horn-clause arguments
2. Selection function independence - Let S₁ and S₂ be selection functions and let A be a Horn-clause argument. Then, there is an SLD resolution proof for A that uses S₁ if and only if there is one that uses S₂.

The goal here is to generalise SLD resolution for propositional Horn-clause arguments to handle first order Horn-clause arguments (i.e., a subset of predicate calculus).

If we let Φ be a forumla whose free (unbound) variables are x₁, ..., x_n, then ∀Φ is the universal closure of Φ, which abbreviates ∀x₁, ..., x_n Φ. Furthermore, ∃Φ is the existential closure of Φ and abbreviates ∃x₁, ..., x_n Φ.

Each premise in a first order Horn-clause argument is a definite clause∀((α₁ ^ ... ^ α_n) → β), where n ≥ 0 and where each α_i and β are atomic formulas of first order predicate calculus. If n = 0, then we have that ∀(→ β), which is a definite clause and we simply write this as ∀β.

The conclusion in a propositional Horn-clause argument is a goal clause ∃(α₁ ^ ... ^ α_n), where each α_i is an atomic formula of first-order predicate calculus. As a special case when n = 0, we can write [] - this is the empty conjunction which is true in all models.

Since all variables in the definite clause are univerally quantified, and all those in the goal clause are existentially quantified, the closures are often not written, so in such cases, it is important to bear in mind that they are there implicitly.

Substitutions

Instances

Herbrand's Theorem

Unifiers

With this, we can apply SLD-resolution for first order Horn clause arguments. From the goal clause G₁ ^ ... ^ G_{i - 1} ^ G_i ^ G_{i + 1} ^ ... ^ G_n (n ≥ 1) and the definite clause B₁ ^ ... ^ B_m → H (m ≥ 0) we can derive the goal clause (G₁ ^ ... ^ G_{i - 1} ^ B₁ ^ ... ^ B_m ^ G_{i + 1} ^ ... ^ G_n)θ, provided that H and G_i are unifiable and θ is the most general unifier of the two.

The SLD-resolution inference rule is sound and complete for first-order Horn clause arguments, and selection function independence also applies in the first-order case.

Answer Extraction

To find a solution by partial assignment search, a space of partial assignments is searched, looking for a goal state which is a total assignment that satisfies all the constraints.

In partial assignment search, you start at the initial state with an assignment to no variables. Operators are then applied, each of which extends the assignment to cover an additional variable. Some reasoning is then performed at each node to simplify the problem and to prune nodes that can not extend to reach a solution.

Partial assignment uses a method called backtrack. If all the variables of a constraint are assigned and the constraint is not satisfied then the node containing that constraint is pruned.

Partial assignment search for an instance I of the CSP can be shown as a problem representation:

• States: A state consists of a CSP instance and a partial assignment
• Initial State: The CSP instance I and the empty assignment. Problem reduction is often performed to simplify the initial state
• Goal States: Any state that has not been pruned and the assignment is total
• Operators: A variable selection function (heuristic) is used to choose an unassigned variable, X_i. Then, for every value v in the domain of X_i, there is an operator that produces a new state by:
  • Extending the assignment by assigning v to X_i
  • Setting D _i to {v}
  • Performing problem reduction to reduce the domains
  • Pruning the new node if any domain is the empty set
• Path Cost: This is constant for each operator application

There are issues in partial assignment search, however - how do we know what problem reductions should be performed, how are variables selected, how the search space is searched and how the values are ordered.

Consistency techniques are a class of reduction techniques that vary in how much reduction they achieve and how much time they take to compute. In the extreme, there are some consistency techniques that are so powerful that they solve a CSP by themselves, but these are too slow in practice. At the other extreme, one could also solve by search with little or no simplifcation, which is also ineffective.

For many applications, generalised arc consistency (GAC) provides an effective trade-off for a wide class of problems. Node consistency is a special case of GAC for unary constraints and arc consistency is a special case for binary constraints. Other consistency techniques could also be effective for specific problems.

Node Consistency

Arc Consistency

Generalised Arc Consistency

There are three main techniques for applying domain reduction during search:

• Backtracking: When all variables of a constraint are assigned, then check if the constraint is satisfied - if not, then prune. This is almost always ineffective as it does not perform enough pruning.
• Forward Checking: When all variables are assigned, but one variable of a constraint C is assigned, then achieve generalised arc consistency from the unassigned variable to the other variables and prune if a domain becomes empty.
• Maintaining Arc Consistency: Achieve GAC at each node, and prune if a domain becomes empty.

Variable ordering can affect the size of the search space dramatically. There are two main techniques to variable ordering: static, which is satisfied before the search begins and is the same down every path; and dynamic, where the choice depends on the current state of the search, and hence can vary from path to path.

The most common type of variable ordering is based on the fail-first principle. A variable with the smallest domain is chosen, and ties can be broken by choosing a variable that participates in most constraints. This is static if no simplification is done and is dynamic if simplification reduces domain sizes. This method often works well and is built into many toolkits.

Other methods sometimes work better for particular problems, such as in laying out a PCB to place the largest components first, and in class timetabling to timetable the longest continuous sessions.

Situation calculus is one method of representing change in the world. Situation calculus works by maintaining an up-to-date version of the state of the world, by tracking changes within it. The language of situation calculus is first order logic.

Situation calculus consists of:

• domain predicates, which represent information about the state of the world
• actions
• atemporal axioms, which consist of general facts about the world
• intra-situational axioms, which are facts about situations
• causal axioms, which describe the effects of actions

Predicates that can change depending on the world state need an extra argument to say in what state they are true, e.g., in the blocks world, held(x) becomes held(x, s), etc... Predicates that do not change do not need the extra argument, e.g., block(x).

We also have a function called result(a, s), which is used to describe the situation that results from performing an action a in a situation s.

Causal axioms model what changes in a situation that results from executing some action, not what stays the same. Therefore, we need to define frame axioms which define what stay the same in a situation. This necessity causes the frame problem, as in a complex domain, a lot of things stay the same after an action has been executed.

Finding a sequence of actions that leads to a goal state can be formulated as an entailment problem in first order predicate calculus. For situation calculus planning, the steps to take are to specify an initial state (as state s₀), specify a goal (a formula that contains one free variable S) and then find a situational term such that the goal is a logical consequence of the axioms and the initial state. A situation term is a ground term of nested result expression that denotes a state.

We can formally state this as: Given a set of axioms D, an initial state description I and a goal condition G, find a situation term t such that G {S → t} is a logical consequence of D ∪ I.

Situation calculus does have limitations, however - it has a high time complexity, does not support simultaneous actions, does not handle external actions, or other changes than those brought about as a direct result of the actions, it assumes that all actions are instantaneous, and there is no way to represent time.

STRIPS is the Stanford Research Institute Problem Solver, and also the formal language that the problem solver uses. It provides a representation formalism for actions and has the idea that everything stays the same unless explicitly mentioned - this avoids the frame problem.

Again, STRIPS uses propositional or first order logic, and the state of the world is represented by a conjunction of literals. There is one restriction, and that is that first-order literals must be ground and function-free. STRIPS uses the closed world assumption, that is, everything that is not mentioned in a state is assumed to be false. In STRIPS, the goal is represented as a conjunction of positive (that is, non negated) literals. In the propositional case, the goal is satisfied if the state of the world contains all the propositional atoms. In the first-order case, the goal is satisfied if the state contains (all) positive literals in the goal.

The STRIPS representation consists of a state (a conjunction of function-free literals), a goal (a conjunction of positive function-free literals - they can however contain variables, which are assumed to be existentially qualified) and an action (represented by a set of pre-conditions that must hold before it can be executed and a set of post-conditions, i.e., effects that happen when it is executed). It is common practice to seperate the effects (post-conditions) of an action in STRIPS into an add list, which contains the positive literals, and a delete list which contain the negative literals, for the sake of readability.

An action is said to be applicable if in some state, the state satisfies the actions preconditions (i.e., all literals in the preconditions are part of the state). To establish applicability for first-order actions (action schemas), we need to find a substitution for the varibles that make the action applicable.

The results of an action are that the positive literals in the effect are added to the state, and any negative literals in the effect that match existing positive literals in the state make the positive literals disappear, with the exceptions of positive literals already in the state are not added again, and negative literals that match with nothing in the state are ignored.

Planning in STRIPS can be seen as a search problem. We can move from one state of a problem to another in both a forward and backward direction because the actions are defined in terms of both preconditions and effects. We can use either forward search, called progression planning, or backward search, known as regression planning.

Forward planning is equivalent to forward search, and as such is very inefficient and suffers from all of the same problems as the underlying search mechanism. A better way to solve the planning problem is through backwards state-space search, i.e., starting at the goal and working our way back to the initial state. With backwards search, we need to only consider moves that achieve part of the goal, and with STRIPS, there is no problem in finding the predecessors of a state.

To do regression planning, all literals from the goal description are put into a current state S (the state to be achieved). A literal is then selected from S, and an action selected that contains the selected literal in its add list. The preconditions of the selected action are added to the current state S and literals in the add list are removed from S. When the start state is a subset of the current list of literals of S, we can return success.

Whilst doing regression planning, we must insist on consistency (i.e., that the actions we select do not undo any of the desired goal literals).

This state space search method is still inefficient however, so we should consider whether or not we can perform A* search with an admissible heuristic.

Subgoal Independence

Empty Delete List

The Sussman Anomaly is a situation in the blocks world that can be solved effectively using the planning methods discussed above.

The initial state is On(C, A), Ontable(A), Ontable(B), Handempty and the goal state is On(A, B), On(B, C).

One way of solving this anomaly is to add the condition Ontable(C), however another way is to use another method of planning known as partial order planning.

Up until now, plans have been totally ordered, i.e., the exact temporal relationships between the actions are known. In partially ordered plans, we don't have to specify the temporal relationships between all the actions, and in practice this means that we can identify actions that happen in any order.

Above, we have searched from the intial state to the goal or the vice versa. A complete plan is one which provides a path from the initial state to the goal, and a partial plan is one which is not complete, but could be extended to be complete by adding actions at the end (forwards) or at the beginning (backwards) of it. We then need to consider whether or not we can search this space of partial plans.

Doing planning as search happens in the space of partially ordered partial plans, where the nodes are the partially ordered partial plans. The edges denote refinements of the plans, i.e., adding a new action and constraining the temporal relationships between two actions. The root (initial) node is the empty plan, and a goal is a plan that, when executed, solves the original problem.

We represent a plan as a tuple (A, O, L) where:

• A is a set of actions
• O is a set of orderings on actions, e.g., A < B means that action A must take place before action B
• L is a set of causal links which represent dependencies between actions, e.g., (A_add, Q, A_need) means that Q is a precondition of A_need and also an effect of A_add. Obviously we still have to maintain that A_add < A_need.

We also need to consider threats - we say that an action threatens a causal link when it might delete the goal that the link satisfies. The consequences of adding an action that breaks a causal link into the plan are serious. We have to make sure to remove the threat by demotion (move earlier) or promotion (move later).

The partial order planning (POP) algorithm works as follows:

• Create two fake actions, start and finish
• start has no preconditions and its effects are the literals of the intial state
• finish has no effects and its preconditions are the literals of the goal state
• an agenda is created which contains pairs (precondition, action) and initially contains only the preconditions of the finish action
• while the agenda is not empty:
  • select an item from the agenda (i.e., a pair (Q, A_need))
  • select an action A_add whose effects include the selected precondition Q
  • If A_add is new, add it to the plan (i.e., to the set of actions A)
  • Add the ordering A_add < A_need
  • Add the causal link (A_add, Q, A_need)
  • Update the agenda by adding all the pre-conditions of the new action (i.e., all the (Q_i, A_add)) and remove the previously selected agenda item
  • Protect causal links by checking whether A_add threatens any existing links, and check existing actions for threats towards the new causal links. Demotion and promotion can be used as necessary to remove threats
  • Finish when there are no open precondition

Reactive agents are baed on the physical grounding hypothesis and this is sometimes referred to as Nouvelle AI or situated activity (Brooks, 1990).

Here, intelligent systems necessarily have their interpretations grounded in the physical world, and agents map sensory input directly to output (no typing on the input and output occurs). Nouvelle AI takes the view that it is better to start with the development of simple agents in the real world than complex agents in simplified environments.

Reactive agents are built with a subsumption architecture, where organisation is by behavioural units (or layers), and decomposition is by activity, rather than decomposition by function. Each layer connects sensory input to effectors, and each layer is a reactive rule (originally implemented as an augmented finite state machine). Intelligent behaviour then emerges from the interation of many simple behaviours.

We can therefore say that the decision making of a reactive agent is realised through a set of task accomplishing behaviours. These behaviours are implemented as simple rules that map perceptual input directly to actions (state → action). As many rules can fire simultaneously, we need to consider a priority mechanism to choose between different actions.

We can formally specify a behaviour rule as a pair (c, a), where c ⊆ P is a condition and a is an action. A behaviour (c, a) will then fire when the environment is in state s ∈ S and c ⊆ See(s), that is, the agents' percepts in state s. We also let R be the set of an agents' behaviour rules, and we let '<' be a preference relation over R (a total ordering). We say that b₁ < b₂ is that b₁ inhibits b₂, i.e., that b₁ will get priority over b₂.

Reactive agents are therefore very efficient - there is a very small time lag between perception and action, simple and robust in noisy domains. We also say that they have cognitive adequacy. Humans have no full monolithic internal models, that is, no internal model of the entire visible scene, and they even have multiple internal representations that are not necessarily consistent. Additionally, humans have no monolithic control, and humans are not general purpose - they perform poorly in different contexts (especially abstract ones).

On the other hand, reactive agents require that the local environment has sufficient information for an agent to determine an acceptable action. They are hard to engineer, as there is no principled methodology for building reactive agents, and they are especially difficult to develop for complex environments.

Layered architectures work by creating a subsystem (layer) for each type of behaviour (i.e., logic-based, reactive, etc) and these subsystems are arranged into a hierarchy of interacting layers. Horizontal layering is where each layer is directly connected to sensors and effectors, and vertical layering is where sensory input and output is dealt with by at most one layer each. Horizontal layering is shown below:

Vertical layering also comes in two varieties, one-pass control and two-pass control.

Multi-agent systems come with the idea that "there is no single agent system". This is different to traditional distributed systems in that agents may be designed by different individuals with different goals, and agents must be able to dynamically and autonomously co-ordinate their activities and co-operate (or compete) with each other.

One methodology for multi-agent systems is co-operative distributed problem solving (CDPS). This is where a network of problem solvers work together to solve problems that are beyond their individual capabilities; no individual node has sufficient expertise, resources and information to solve the problem by themselves. CDPS works on the benevolence assumption that all agents share a common goal. Self-interested agents (agents designed by different individuals or organisations to represent their interests) can exist, however.

Multi-agent systems can be evaluated using two main criteria: coherence - that is, the solution quality and resource efficiency; and the co-ordination, the degree to which the agents can avoid interfering with each other, and having to explicitly synchronise and align their activities.

Issues in CDPS include dividing a problem into smaller tasks for distribution among agents, synthesising a problem solution from sub-problem results, optimising problem solving activities to achieve maximum coherence and avoiding unhelpful interactions and maximising the effectiveness of existing interactions.

Task and result sharing comes in three main phases: problem decomposition, where sub-problems (possibly in a hierarchy) are produced to an appropriate level of granuality; sub-problem solution, which includes the distribution of tasks to agents; and solution synthesis.

One way of accomplishing this is using a method known as contract net. This is a task sharing mechanism based on the idea of contracting in the business world. Currently, contract net is the most implemented and best studied framework for distributed problem solving.

Contract net starts by task announcement - an agent called a task manager advertises the existance of a task (either to a specific audience, or all), and agents listen to announcements, evaluate them and decide whether or not to submit a bid. A bid indicates the capabilities of the bidder with regard to the task. The announcer receives the bids and chooses the most appropriate agent (the contractor) to execute the task. Once a task is completed, a report is sent to the task manager.

The agents co-operatively exchange information as a solution is developed, and result sharing improves group performance in the following ways:

• confidence: independently derived solutions can be cross-checked
• completeness: agents share their local views to achieve a better global view
• precision
• timeliness: a quicker problem solution is achieved

A co-ordination mechanism is necessarily to manage inter-dependencies between the activities of agents. We can consider a hierarchy of co-ordination relationships:

There are multiple types of positive, non-requested relationships:

• action equality relationship: two agents plan to perform an identical action, so only one needs to perform it
• consequence relationship: a side-effect of an agent's action achieves an explicit goal of another
• favour relationship: a side-effect of an agent's plan makes it easier for another agent to achieve his goals

In partial global planning, the idea is that agents exchange information in order to reach common conclusions about the problem-solving process. It is partial as the system does not generate a plan for the entire problem, and is global as agents form non-local plans by exchanging local plans to achieve a non-local view of problem solving.

There are three stages in partial global planning. In the first, each agent decides what its own goals are and generates plans to achieve them. Agents then exchange information to determine where plans and goals interact. Agents then alter their own local plans in order to better co-ordinate their own activities.

A meta-level structure guides the co-operation process within the system. It dictates which agents an agent should exchange information with, and under what conditions information exchanges should take place.

A partial global plan contains: an objective which the multi-agent system is working towards; activity maps, which are a representation of what agents are actually doing, and what results will be generated by the activities; and a solution construction graph, which represents how agents ought to interact, what information ought to be exchanged, and when.