CS计算机代考程序代写 prolog 8b_Logic_Applications.dvi

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