03 Logical agents Flashcards
Knowledge-based agents
Knowledge-based agents are able to:
• Maintain a description of the environment
• Deduce a course of action that will achieve goals
Knowledge-based agents have:
• A knowledge base
• Logical reasoning abilities
The performance of a knowledge-based agent is determined by its knowledge base. A knowledge base is a set of representations of facts about the world, called sentences, expressed in a knowledge representation language.
Knowledge base (KB) interface:
• TELL(KB,fact) - Add a new fact
• fact <= ASK(KB,query) - Retrieves a fact
• RETRACT(KB,fact) - Removes a fact
A knowledge-based agent can be built by TELLing it what it needs to know (declarative approach). The agent can be used to solve problems by ASKing questions.
Knowledge representation languages should be…
Knowledge representation languages should be:
• Expressive and concise
• Unambiguous and independent of context
• Able to express incomplete knowledge
• Effective inference of new knowledge
Existing languages not suited:
• Programming languages - precise descriptions and recipes for machines
• Natural languages - flexible communication between humans
In AI, logic is used for knowledge representation.
Aspects of knowledge representation languages
Syntax
– How are legal sentences in the language composed?
Semantics
– What do the sentences mean?
– What is the truth of every sentence with respect to each possible world (model)?
Entailment
The fact that sentences logically follow from other sentences
Inference
How to derive new sentences that are entailed by known ones?
Logical entailment
Logical entailment between two sentences: a |= B
- **B follows logically from a
- **In every model (possible world) in which a is true, B is also true.
We can also say that an entire KB (all sentences in the knowledge base) entails a sentence: KB |= B
- B follows logically from KB
- In every model (possible world) in which KB is true, B is also true.
Model checking: Can check entailment by reviewing all possible models.
Logical inference
Logical inference between two sentences: a |- B
means that B can be derived from a by following an inference algorithm (can also say KB |- B). Model checking is an example of an inference algorithm.
Properties of inference algorithms
Sound inference
The inference algorithm only derives entailed sentences
• Required property
• Model checking is sound
Complete inference
The inference algorithm can derive any entailed sentence
• Desirable property
• Not always possible
Types of logic in AI
In AI, both propositional and and first-order logic are heavily used
Propositional logic
• Symbols represent true or false facts
• More complex sentences can be constructed with Boolean connectives (and, or, . . . )
First-order logic
• Symbols represent objects and predicates on objects
• More complex sentences can be constructed with connectives and quantifiers (for-all, there-is, …)
Propositional logic
Semantics
Semantics defines the rules for determining the truth of a sentence with respect to a certain model. A model in propositional logic fixes the truth (true or false) of every propositional symbol. The truth of a complex sentence is given by the truth value of its parts and the connectives used
Complexity of propositional inference
The checking algorithm is sound and complete, but
• Time complexity is O(2^n)
• Space complexity is O(n)
All known inference algorithms for propositional logic have worst-case complexity that is exponential in the size of inputs
Equivalence, validity and satisfiability
Two sentences are equivalent if they are true in the same models.
A sentence is valid (necessarily true, tautological) if it is true in all possible models.
A sentence is satisfiable if it true in some model. A sentence that is not satisfiable is unsatisfiable (contradictory)
Inference by applying rules
An inference rule is a standard pattern of inference that can be applied to drive chains of conclusions leading to goal. A sequence of applications of inference rules is called a proof. Searching for proofs is similar (or in some cases identical) to problem-solving by search. Using rules for inference is an alternative to inference by model checking.
Forward and backward chaining
Forward chaining
• Start with sentences in KB and generate consequences
• Uses inference rules in forward direction
• Also called data-driven procedure
Backward chaining
• Start with goal to be proven and look for premises
• Uses inference rules in backward direction
• Also called goal-directed procedure
Specialized search algorithms for propositional logic can be very efficient
Keeping track of state of the world
Knowledge base contains general knowledge of how the world works plus specific percept history. All percept need to be indexed by time t to capture changes in percepts: ¬Stench3, Stench4… The term fluent is used for any state variable that changes over time. Effect axioms are used to describe outcome of an action at the next time step. Frame problem: Effect axioms fail to state what does not change as a result of an action. Solved by writing successor-state axioms for fluents, e.g. HaveArrow^{t+1} <=> (HaveArrow^t ^ ¬Shoot^t).
Propositional agent requires very large number of rules.
Wumpus agent
Refer to this for examples of everything
