CSE 3521: Intro to Artificial Intelligence

CSE 3521: Intro to Artificial Intelligence

Last time: Search Today: Logic Search vs Logic Search What is the best action sequence to achieve a goal? Space of atomic states Successor function defined for each state Fully enumerates each possible successor Guided by knowledge about the goal

Search vs Logic Logic Reason about the world to identify good actions Space of attributive states Successor function defined over attribute values Successors effectively partial states (what has changed?) Guided by knowledge about the world Pos: [1,1] Dot1: True Dot2: True

Pos: [1,2] Dot4: False Pos: [2,1] Dot8: False Logical agents Agent Percepts ?

Actuators Environment Sensors + Actions Knowledge Base Contains sentences describing the state of the world

Supports inference and derivation Dynamic; changes as a result of agent interactions with the environment! Logical Agent Control Flow TELL (Percept) ASK Agent TELL (Action)

Knowledge reasoning... Base Knowledge Bases Agent models what the agent knows about the world Store different kinds of knowledge Background knowledge the rules of the world Note that if this is an unknown problem, the agent may need to discover the rules! Typically does not change due to agent actions

Situational knowledge what is currently true Describes the current state of the world Remember: KB sentences are Remember: Change from state to state, as a result of agent actions KB sentences are agents agents model model of of the the world,

world, not not (successor function) the the true true world world state! state! Filling Knowledge Bases KBs have sentences complete statements about one aspect of the

world Exact form depends on the knowledge representation language Two kinds of sentences Derived follow logically from other sentences in the KB Axiomatic cannot be derived from the KB, must be given Axioms 1+1=2 2+1=3 3+1=4 Derived

2+2=4 Filling Knowledge Bases Two ways to pre-populate KB with starting info Declarative at startup, TELL the KB all the facts it needs to model the rules of the world Procedural bake the rules of the world into the program In practice, use a mix of both Example: Wumpus World

Wumpus World World: cave with rooms connected by passageways Rooms may contain: Gold, a Bottomless Pit, or The Terrible Wumpus PIT Agent: intrepid explorer, armed with a single arrow Arrow continues until it hits the Wumpus (and kills it) or a wall. Goal: escape alive with the gold! The PEAS of Wumpus World

Performance Measure +1000 for climbing out with the gold -1000 for dying (pit or wumpus) -1 for each action taken -10 for using up your only arrow The PEAS of Wumpus World Environment 4x4 grid of rooms Agent always starts in [1,1] facing Right

Gold, wumpus, and pit locations chosen randomly The PEAS of Wumpus World Actuators Move Forward, Turn Left, or Turn Right Death if enter a square with a pit or live Wumpus No change if walk into a wall Grab gold if in same square Shoot arrow in direction Agent is facing Continues in straight line until hits

Wumpus (=dead Wumpus) or wall Only 1 arrow! Climb to escape the cave (only from [1,1]) The PEAS of Wumpus World Sensors Stench if in square adjacent to Wumpus square Breeze if in square adjacent to Pit square Glitter if in square where Gold is Bump if walked into a wall

Scream heard if Wumpus is hit by Arrow and dies Wumpus World Example Configuration PIT PIT Wumpus World Example Play ???

??? PIT ??? Propositional Logic and Inference Infer ence Logic Basics Representation language specifies the syntax to determine which sentences are valid

x + y = 4 x4y + = Semantics define the truth of sentences under possible worlds x + y = 4 True if x = y = 2; False if x = y = 1 Possible worlds (models) specified by assignment to all variables Each model determines truth of every sentence Assignment m to variables such that sentence S is True m satisfies S Logical Entailment

Sentence A entails sentence B iff in every model where A is true, B is also true All humans are mortal Socrates is human Socrates is mortal Propositional Logic

Atomic sentence: single Boolean variable Connectives Negation And (conjunction) Or (disjunction) Implies/entails (left: antecedent, right: consequent) If and only if (biconditional) Propositional Logic BNF Grammar Sentence AtomicSentence AtomicSentence

ComplexSentence ComplexSentence | | | | | || | |

AtomicSentence | ComplexSentence True True || False False || P P || Q Q || R R || (Sentence) (Sentence) || [Sentence] [Sentence]

Specifies all syntactically valid sentences in Prop Logic Wumpus Propositional Logic Immutable aspects of Wumpus can be expressed as: is True if there is a pit in [x,y] is True if the wumpus is in [x,y] is True if there is a breeze in [x,y] is True if there is a stench in [x,y] Wumpus World Current KB Background knowledge

??? Situational knowledge Inference Question: ? Inference algorithm must be

Consistent Only derives sentences that are entailed Complete Can derive any sentence that is entailed Inference Question: ? One option: exhaustive search 1. Enumerate all possible models 2. Verify that wherever KB is true, is as well Consistent (uses definition of entailment)

Complete (finitely many models, checks them all) Exponential time! n variables yield possible models Pit-only wumpus has 32 variables! Better: Theorem Proving Important concepts A and B are logically equivalent if they are true in the same set of worlds A is valid if it is true in all worlds Aka tautologies

A is satisfiable if there is some world in which it is true The original NP-complete problem! A is valid iff is unsatisfiable A is satisfiable iff is invalid Inference Rules Modus Ponens If both and A are in the KB, then B can be inferred

And Elimination If the conjunct is true, each element is true De Morgans Rule Proof by Resolution General idea: 1. Apply inference rules 2. Use complementary literals to simplify clauses

3. Rinse, repeat Wumpus World Resolving PIT ???

Next Time Forward-backward chaining for efficient inference First-order logic

Recently Viewed Presentations

  • Structural Members

    Structural Members

    * INTRODUCTION Concrete slabs are similar to beams in the way they span horizontally between supports and may be simply supported, continuously supported or cantilevered. Unlike beams, slabs are relatively thin structural members which are normally used as floors and...
  • Tor: The Second-Generation Onion Router

    Tor: The Second-Generation Onion Router

    An onion router uses a long-term identity key for signing TLS certificates to other onion routers, the router descriptor, which contains information like address, bandwidth, exit policy, and sign directories. It is not used for negotiating shared keys. Instead, the...
  • Opiate Risk Mitigation in Primary Care

    Opiate Risk Mitigation in Primary Care

    Respiratory depression leading to an opioid-related death is exacerbated by the presence of additional substances, including alcohol, illicit drugs, and other prescription medications, particularly benzodiazepines. Benzodiazepine use has been found to contribute to life threatening sleep-disordered breathing
  • PARADOXO GLOBAL O Século do Dragão O commonwealth chinês ...

    PARADOXO GLOBAL O Século do Dragão O commonwealth chinês ...

    Confúcio Confucio nació en el año 551 y murió en 479, antes de nuestra era, una época caracterizada por el paso de una religiosidad de carácter mágico a una religiosidad racional.
  • Policing practices and HIV risk among people who

    Policing practices and HIV risk among people who

    Originating from 9 different countries (Russia, Mexico, USA, Canada, Ukraine, Thailand, Malaysia, China and India) No longitudinal data (all cross-sectional) Studies with HIV seroprevalence data (n=6) Studies with risky injection behavior data (n=21) Studies with HIV prevention program data (n=9)
  • Building Coaches Legal Side of Supervision Human Resources

    Building Coaches Legal Side of Supervision Human Resources

    [Intranet/HR/ Benefits] HIPAA requirements extended to Business Associates. Security breach notification (stronger enforcement) Portability - Move from job to job even with pre-existing condition. PHI - Protect the privacy to health information.
  • Mechanical Service Contractors of Canada *Membership *Education *

    Mechanical Service Contractors of Canada *Membership *Education *

    Contact Mechanical Contractors Association of Manitoba, 860 Bradford Street R3H 0N5. 774-2404. [email protected] www.mca-mb.com. Membership fees are $750.00 for the first year and $1500.00 each year thereafter. This entitles the service contractor to all of the benefits the Association has...
  • NLP & Coaching Institut Berlin Nandana & Karl Nielsen

    NLP & Coaching Institut Berlin Nandana & Karl Nielsen

    The map is not the territory: People respond to their ideas of reality, and NLP can change these ideas - thus reactions can be changed. Behind every symptom and every behavior lies a positive intention: Every issue contains at least...