!
CMP2020M
ARTIFICIAL INTELLIGENCE
Dr. Marc Hanheide
Lincoln School of Computer Science University of Lincoln
goto already: http://lncn.eu/cmp2020m
!
http://lncn.eu/cmp2020m
AI QUIZ
AI QUIZ
‣ What is a semantic network composed of? A. nodes representing concepts
B. arcs representing relations
C. nodes representing propositions
D. arcs representing properties E. nodes representing objects
!
AI QUIZ
‣ Why are hierarchical representations like semantic networks believed to be a model of humans’ knowledge representation?
A. There is evidence about the response time from empirical experiments
B. There is evidence about the
correct association of concepts
from empirical experiments
C. Brain surgery suggests a
hierarchical decomposition
of knowledge into concepts
!
PLANNING
needs to avoid invalid solutions
Difficult:What is good?
In particular, needs to take successor states and options into account!
PLANNING
should prefer good solutions
Initial
State
Goal State
CONSIDERING ACTIONS
Applicable action
Successor states
Precondition
Postcondition
Actions
A SEARCH TREE
Nodes: States
Edges: Actions
Path – a sequence of states and valid actions Solution – a path from the initial state to the goal state
State space
all states reachable from the initial state via a sequence of valid actions
SO WHY IS SEARCH AI?
Intelligence is doing the right thing at the right time
A problem with 10 applicable actions with a solution that is 10 steps long, will require checking 1010 alternative action sequences.
317 years at 1 solution a second
•
•
WHY IS PLANNING AI?
Because the planner has to take decisions: is the action valid?
what path is better?
•
?
? ?
WHY IS PLANNING INSIDE AI?
• Because the possibilities are exponential and we need an “intelligent / fast” way of finding a solution:
…
…
…
3
20
For a plan of 20 actions with 3 possible successors for each action we will need to check 3486784401 paths!!
dynamic world, search graphs
static world
specific (path) planning generic knowledge representation
dynamic world
universal planning
using logic
!
THE FIRST AI ROBOT
‣ From 1966 through 1972, the Artificial Intelligence Center at SRI International (then Stanford Research Institute) conducted research on a mobile robot system nicknamed “Shakey.” Endowed with a limited ability to perceive and model its environment, Shakey could perform tasks that required planning, route-finding, and the rearranging of simple objects.
‣ http://www.ai.sri.com/shakey/
!
AI PLANNING
‣ AI is basically search in the space of possible actions ‣ STRIPS: Stanford Research Institute Problem Solver ‣ a Strips Problem:
‣ P is a set of conditions (i.e., predicates);
‣ I is the initial state, given as the set of conditions that are initially true
(all others are assumed false);
‣ G is the specification of the goal state
‣ O is a set of operators (i.e., actions); each operator defines the pre- conditions and effects.
!
REPRESENTATION
‣ We need a way to represent actions and states in a way a computer can understand and manipulate.
‣ A simple language is STRIPS (STanford Research Institute Problem Solver).
‣ STRIPS uses predicate logic (remember : ProLOG!) to represent problems
‣ We use the more modern PDDL language which subsumes STRIPS
BLOCKS WORLD (SLIDES PARTIALLY BY STAVROS VASSOS)
HOW TO REPRESENT THIS?
(THIS IS ONE SOLUTION!)
ontable(A) ^
ontable(B) ^
ontable(C)
on(A,B) ^
on(B,C) ^
ontable(C)
clear(A) ^
clear(B) ^
clear(C)
clear(A)
A PDDL DOMAIN DESCRIPTION
(define (domain BLOCKS)
(:requirements :strips)
(:predicates (on ?x ?y)
Header PDDL submodules
Declaration of all predicates
(ontable ?x)
(clear ?x)
(handempty)
(holding ?x)
)
additional predicates describing the status of the hand
!
THE INITIAL STATE
‣ Using predicate (or first-order) logic literals to describe the world as it is.
‣ has to be completely specified
(on ?x ?y) based on closed world assumption: (ontable ?x)
‣ assumes every literal not present to
be false!
(clear ?x)
(handempty)
(holding ?x)
PDDL PROBLEM AND INITIAL STATE
Problem name (arbitrary)
reference to domain definition objects in this problem Initial state (implicit conjunction)
(define
(problem BLOCKS-3)
(:domain BLOCKS)
(:objects A B C )
(:INIT
(CLEAR A)
(CLEAR B)
(CLEAR C)
(ONTABLE A)
(ONTABLE B)
(ONTABLE C)
(HANDEMPTY))
… )
Implicitly by closed world assumption: ¬(on(A,B)) and others
THE GOAL STATE
‣ Using predicate (or first-order) logic literals to describe the world as it should be.
‣ is only partially specified
‣ we don’t care about the outcome in other predicates that
the ones defined in the goal state
(on ?x ?y)
(ontable ?x)
(clear ?x)
(handempty)
(holding ?x)
PDDL GOAL DEFINITION
(define
(problem BLOCKS-3)
(:domain BLOCKS)
(:objects A B C )
(:INIT
(CLEAR A)
(CLEAR B)
(CLEAR C)
(ONTABLE A)
(ONTABLE B)
(ONTABLE C)
(HANDEMPTY))
(:goal (AND
(ON A B) (ON B C)
)
)
Goal state: underspecified, only constraints are defined.
)
!
SOLVING A PROBLEM, DEFINING ACTIONS
‣ Actions change the state of the world
‣ they can be applicable only if their preconditions are fulfilled ‣ they have an effect in the world
Applicable action
Successor states
!
ACTIONS IN BLOCKSWORLD
(:action pick-up
:parameters (?x)
:precondition (and (clear ?x)
(ontable ?x)
(handempty))
:effect
(and (not (ontable ?x))
(not (clear ?x))
(not (handempty))
(holding ?x)))
make sure to list ALL conditions
make sure to list ALL effects
!
ACTIONS IN BLOCKSWORLD
(:action put-down
:parameters (?x)
:precondition (holding ?x)
:effect
(and (not (holding ?x))
(clear ?x)
(handempty)
(ontable ?x)))
!
ACTIONS IN BLOCKSWORLD
(:action stack
:parameters (?x ?y)
:precondition (and (holding ?x
(clear ?y))
:effect
(and (not (holding ?x))
(not (clear ?y))
(clear ?x)
(handempty)
(on ?x ?y)))
!
ACTIONS IN BLOCKSWORLD
(:action unstack
:parameters (?x ?y)
:precondition (and (on ?x ?y) (clear ?x)
(hand empty))
:effect
(and (holding ?x)
(clear ?y)
(not (clear ?x))
(not (handempty))
(not (on ?x ?y)))))
!
APPLYING EFFECTS
(CLEAR A)
(CLEAR B)
(CLEAR C) (ONTABLE A) (ONTABLE B) (ONTABLE C) (HANDEMPTY)
(pick-up B)
(:action pick-up
:parameters (?x)
:precondition (and (clear ?x)
(ontable ?x)
(handempty))
:effect
(and (not (ontable ?x))
(not (clear ?x))
(not (handempty))
(holding ?x)))
(CLEAR A)
(CLEAR C)
(ONTABLE A)
(ONTABLE C)
(HOLDING B)
APPLYING EFFECTS
!
(stack B C)
(:action stack
:parameters (?x ?y)
:precondition (and (holding ?x
(clear ?y))
:effect
(and (not (holding ?x))
(not (clear ?y))
(clear ?x)
(handempty)
(on ?x ?y)))
(CLEAR A)
(CLEAR C)
(ONTABLE A)
(ONTABLE C)
(HOLDING B)
what are next applicable actions?
(CLEAR A)
(CLEAR B)
(ONTABLE A) (ON B C) (ONTABLE C) (HANDEMPTY)
!
FINDING A PATH
(pick-up B)
(stack B C)
(pick-up A)
(stack A B)
‣ Chaining actions with “matching preconditions and effects”…
‣ This is search in the vast space of possible states that are
reachable
‣ How the best solution among all the possible ones is found efficiently we’ll discuss next week.
!
SUMMARY
‣ Planning is about finding an (optimal) path from an initial state to a goal state ‣ Classical planning is based on
‣ closed-world assumption
‣ discrete and finite belief states
‣ can solve any problem defined in first order predicate logic (if tractable)
‣ We didn’t touch yet
‣ heuristics (they only make planning tractable)
‣ planning under uncertainty (if the state space is not discrete) ‣ continual planning (dealing with unplanned changes)
!
RECOMMENDED READING
‣ Artificial Intelligence:
A Modern Approach
mainly chapter 3
(excerpt on blackboard)