Knowledge Representation - BKJackson/BKJackson_Wiki GitHub Wiki

Logic requirements for knowledge representation

It should be

  • expressive
  • concise
  • unambiguous
  • independent of context and
  • it should have an inference procedure

Our choice of language tends to lead to two important commitments

  • Ontological commitments: what does the world consist of?
  • Epistemological commitments: what are the allowable states of knowledge?

Source

Situation Calculus

Situation calculus uses a function:

Result(action, situation)

to denote the new situation arising as a result of performing the specified action in the specified situation.

Result(Grab, S1) = S2  
Result(Turn(left), S2) = S3
Result(Shoot, S3) = S4 
Result(Forward, S4) = S5

Effects of actions

Given that an action results in a new situation, we then specify the properties of the new situation.

effect axioms - describe the way the world changes
frame axioms - describe the way the world stays the same
planning systems - allow us to reason efficiently when actions change only a small part of the world
successor-state axioms - combine effect and frame axioms to describe the new state of the world. One successor-state axiom is needed for each predicate that can change over time.

Deducing properties of the world

causal rules - some properties of the world will produce percepts. Systems reasoning with such rules are known as model-based reasoning systems.
diagnostic rules - infer properties of the world from percepts, comprise diagnostic reasoning systems.

Example: Medical diagnosis can be done based on symptoms or based on a model of disease.

Separate facts about goals from facts about actions

Actions:

  • can be ranked
  • e.g., great, good, medium, risky, deadly
  • this produces an action-value system

Goals:

  • typically a desired end state
  • e.g., finding the gold
  • are conjunctions of literals where variables are assumed existentially quantified

Once a goal is defined, there are at least three ways to achieve it:

  • inference: ask the knowledge base for a sequence of actions to reach the goal (Computational complexity!)
  • search: best first search. This requires us to change the knowledge base into operators and a state representation
  • planning: finds a sequence of actions that makes the goal true when performed

States:

  • are conjunctions of ground literals with no functions

Using heuristics in planning

  • Example: h = number of unsatisfied preconditions - number satisfied by the start state
  • This can lead to under- or overestimates, particularly if actions can affect one another

Planning graphs

  • They apply only when it is possible to work entirely using propositional representations of plans.
  • Easy to construct
  • Can be used to compute more sensible heuristics

Constructing a planning graph in levels:

  • level 0 corresponds to the start state
  • at each level we keep approximate track of all things (states) that could be true at the corresponding time
  • at each level we keep approximate track of what actions could be applicable at the corresponding time

The approximation is due to the fact that not all conflicts between actions are tracked.

  • Mutual exclusion links track pairs of actions that could not occur together and if the effect of an action negates the precondition of another.

GraphPlan algorithm

Start at level 0;
while(true)
{
  if (all goal propositions appear in the current level AND no pair has a mutex link)
  { 
    attempt to extract a plan;
    if (a solution is obtained)
      return the solution;
    else if (graph indicates there is no solution)
      return fail;
    else 
      expand the graph to the next level;
  }
}

Resources

Symbolic Knowledge Representation - Lecture notes, Sean Holden, U. Cambridge