8b_Logic_Applications.dvi
COMP9414 Logic Applications 1
This Lecture
� Ontologies
◮ Taxonomies
◮ Roles and Groups
� Reasoning About Action
◮ Situation Calculus
◮ Domain Constraints
◮ Actions and the Frame Problem
UNSW ©W. Wobcke et al. 2019–2021
COMP9414: Artificial Intelligence
Lecture 8b: Logic Applications
Wayne Wobcke
e-mail:w. .au
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 3
Example Ontology
AfPak Ontology
� Ashraf Ghani is President Ghani – equality
� Ashraf Ghani is the President of Afghanistan – role
� Ashraf Ghani is in the government – member of
� Nangarhar is a province – a kind of
� Nangarhar is in Afghanistan – part of
� Bombing implies Attacking – linguistic meaning/semantics
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 2
Ontology
� General concepts and relationships between concepts
◮ Subclass relationships
◮ Part-whole relationships
◮ Role relationships
� Knowledge base of facts about objects
◮ Class membership
◮ Equality of objects
◮ Part-whole relationships
◮ Integrity constraints
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 5
Roles and Groups
� Every country has one (and only one) President
◮ ∀c(country(c)→∃p president(c, p))
◮ ∀c∀p∀q(president(c, p)∧ president(c, q)→ p = q)
◮ president(Afghanistan, Ashraf Ghani)
� Quetta Shura is a subgroup of Taliban
◮ ∀x(member(x, Quetta Shura)→ member(x, Taliban))
� Hibatullah is a member of Taliban
◮ member(Hibatullah,Taliban)
� If the target is Hibatullah then the target is Taliban
◮ ∀x∀y(target(e, x)∧member(x, y)→ target(e, y))
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 4
Taxonomies
� Type hierarchies p is-a q
◮ ∀x(p(x)→ q(x))
◮ ∀x(hospital(x)→ building(x))
� Transitivity
◮ {∀x(p(x)→ q(x)),∀x(q(x)→ r(x))} ⊢ ∀x(p(x)→ r(x))
� Part-whole relations x part-of y
◮ ∀x∀y(location(e, x)∧part-of(x, y)→ location(e, y))
� Transitivity
◮ ∀x∀y∀z(part-of(x, y)∧part-of(y, z)→ part-of(x, z))
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 7
Reasoning About Action
� Semantics: Divide the world into a sequence of (notional) time points
◮ Situation is a (complete) state of world at a time point
◮ Action is a transition between situations
◮ Nothing (of relevance) happens between situations
� Planner: Maintain an incomplete description of situations
◮ Confusingly, also called a state of the world
◮ Search for path from initial state to a goal state
◮ State transitions correspond to actions
◮ Major problem is to specify actions
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 6
Planning Agent
� Environment changes due to the performance of actions
� Planning scenario
◮ Agent can control its environment
◮ Only atomic actions, not processes with duration
◮ Only single agent in the environment (no interference)
◮ Only changes due to agent executing actions (no evolution)
� More complex examples
◮ Robocup dog
◮ Delivery robot
◮ Self-driving car
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 9
Specifying Actions (STRIPS)
� Action Description – name of action
� Preconditions – action can be performed in a situation only if
precondition holds in situation prior to action being performed
� Delete List – literals to be deleted from the state (description) after
action is performed
� Add List – literals to be added to the state (description) after action is
performed
� STRIPS Assumption – any literals in the state (description) not
contained in the delete list remain the same after the action is
performed (c.f. frame problem)
Assumes actions are executed perfectly (reasonable for planning?)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 8
The Blocks World
� Blocks can be placed on the table and can be stacked on one another
� All blocks the same size and table large enough to hold all blocks
A
C
B
Table
State: on(C, A), on(A, Table), on(B, Table), clear(B), clear(C)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 11
Problems in Reasoning About Action
� Frame Problem
◮ How to characterize what in the state does not change by
performing an action
• Problem is there are a lot of such facts
• Both “epistemological” and “computational” problem
� Ramification Problem
◮ What are the direct and indirect effects of performing an action?
• Problem is that indirect effects depend on initial situation
� Qualification Problem
◮ What preconditions are required in a specification of an action?
• Problem is that qualifications depend on context
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 10
Blocks World Actions (STRIPS)
� Action Description: move(x, y, z) (x 6= y 6= z?)
� Preconditions: on(x, y), clear(x), clear(z)
� Delete List: clear(z), on(x, y)
� Add List: on(x, z), clear(y), clear(Table)
◮ Add clear(Table) to ensure table is always clear
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 13
Blocks World States
� State – Here a description of what holds in a situation
◮ More like the “state” of a planning agent
� Method 1: Add situation argument to each predicate
on(C, A, S1), on(A, Table, S1), on(B, Table, S1)
clear(B, S1), clear(C, S1)
� Method 2: Special “holds” predicate (predicates become functions)
holds(on(C, A), S1), holds(on(A, Table), S1), holds(on(B, Table), S1)
holds(clear(B), S1), holds(clear(C), S1)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 12
Situation Calculus
� First-order logic formalism for describing states and change
◮ Situation is a (complete) state of world at a time point
� Reify situations: terms denote situations, e.g. S0, S1, · · ·
� Actions are arguments of a special “do” function
◮ Situation do(A, S) denotes the result of doing A in situation S
◮ Assumes world is deterministic (but agent knowledge incomplete)
� Propositions (assertion that some fact holds in a situation)
◮ Add situation argument to each predicate, or
◮ Special “holds” predicate (predicates become functions)
� Axioms for domain constraints and performing actions
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 15
Actions
do(A, S) – “Result of doing action A in situation S”
� Example: “move block x from y to z” and “clear y”
◮ ∀x∀y∀z∀s(on(x, y, s)∧ clear(x, s)∧ clear(z, s)∧ (x 6= z) →
on(x, z, do(move(x, y, z), s)))
◮ ∀x∀y∀z∀s(on(x, y, s)∧ clear(x, s)∧ clear(z, s)∧ (x 6= z) →
¬on(x, y, do(move(x, y, z), s)))
◮ ∀x∀y∀z∀s(on(x, y, s)∧ clear(x, s)∧ clear(z, s)∧ (x 6= z)∧
(y 6= z)→ clear(y, do(move(x, y, z), s)))
◮ ∀x∀y∀z∀s(on(x, y, s)∧ clear(x, s)∧ clear(z, s)∧ (x 6= z)∧
(z 6= Table)→¬clear(z, do(move(x, y, z), s)))
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 14
Domain Constraints
� Also known as state constraints
� True at all (legal) states, though involve state-dependent relations
� Examples
◮ x is on the table iff it is not on top of another block
• ∀x∀s(on(x, Table, s)↔¬∃y(on(x, y, s)∧ (y 6= Table)))
◮ x is clear iff there is no block on top of it
• ∀x∀s(clear(x, s)↔¬∃yon(y, x, s))
◮ if y is a block and there is another block on it, then y is not clear
• ∀x∀y∀s(on(x, y, s)∧ (y 6= Table)→¬clear(y, s))
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 17
Planning with the Situation Calculus
� To determine a plan to achieve goal Γ(s), prove ∃sΓ(s) using action
theory and initial state
� For example, ∃son(B, Table, s) using
on(B, A, S0)
on(A, C, S0)
on(C, Table, S0)
clear(B, S0)
clear(Table, S0)
on(x, y, s)∧clear(x, s)∧clear(z, s)∧(x 6= z)→ on(x, z, do(move(x, y, z), s))
� Also require equality axioms: A = A, ¬(A = B), etc.
� Obtain s = do(move(B, A, Table), S0)
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 16
The Frame Problem
� Previous action descriptions are not “complete”
◮ They describe what changes
◮ They do not specify what stays the same
� Proposal: Frame Axioms
on(x, y, s)∧ (x 6= u)→ on(x, y, do(move(u, v, z), s))
¬on(x, y, s)∧ ((x 6= u)∨ (y 6= z))→¬on(x, y, do(move(u, v, z), s))
clear(u, s)∧ (u 6= z)→ clear(u, do(move(x, y, z), s))
¬clear(u, s)∧ (u 6= y)→¬clear(u, do(move(x, y, z), s))
UNSW ©W. Wobcke et al. 2019–2021
COMP9414 Logic Applications 18
Conclusion
� Ontologies
◮ Description Logic more restrictive and efficient
◮ Standard ontologies in various domains
◮ Tools for ontology construction and maintenance
� Reasoning About Action
◮ Interesting from philosophical point of view
◮ Lack concise solution to the frame problem
◮ Event calculus is another formalism more like Prolog
UNSW ©W. Wobcke et al. 2019–2021