ITT63 ARTIFICIAL INTELLIGENCE UNIT IV
Academic Year 2016-2017(EVEN SEM)
Planning and Learning: Planning with state space search - conditional planning-continuous
planning - Multi-Agent planning. Forms of learning - inductive learning - Reinforcement Learning -
learning decision trees - Neural Net learning and Genetic learning
1.What is Planning in AI?Explain the Planning done by an agent?
Planning problem
– Find a sequence of actions that achieves a given goal when executed from a given initial
world state. That is, given
– a set of operator descriptions (defining the possible primitive actions by the agent),
– an initial state description, and
– a goal state description or predicate,
compute a plan, which is
– a sequence of operator instances, such that executing them in the initial state will change the
world to a state satisfying the goal-state description.
– Goals are usually specified as a conjunction of goals to be achieved
An Agent Architecture
Planning vs. problem solving
– Planning and problem solving methods can often solve the same sorts of problems
– Planning is more powerful because of the representations and methods used
– States, goals, and actions are decomposed into sets of sentences (usually in first-order logic)
III YR /VI SEM Page 1
,ITT63 ARTIFICIAL INTELLIGENCE UNIT IV
– Search often proceeds through plan space rather than state space (though there are also state-
space planners)
– Subgoals can be planned independently, reducing the complexity of the planning problem
Typical assumptions
– Atomic time: Each action is indivisible
– No concurrent actions are allowed (though actions do not need to be ordered with respect to
each other in the plan)
– Deterministic actions: The result of actions are completely determined—there is no
uncertainty in their effects
– Agent is the sole cause of change in the world
– Agent is omniscient: Has complete knowledge of the state of the world
– Closed World Assumption: everything known to be true in the world is included in the state
description. Anything not listed is false.
Blocks world
The blocks world is a micro-world that consists of a table, a set of blocks and a robot hand.
Some domain constraints:
– Only one block can be on another block
– Any number of blocks can be on the table
– The hand can only hold one block
Typical representation:
ontable(a)
ontable(c)
on(b,a)
handempty
clear(b)
clear(c)
General Problem Solver
III YR /VI SEM Page 2
, ITT63 ARTIFICIAL INTELLIGENCE UNIT IV
– The General Problem Solver (GPS) system was an early planner (Newell, Shaw, and Simon)
– GPS generated actions that reduced the difference between some state and a goal state
– GPS used Means-Ends Analysis
– Compare what is given or known with what is desired and select a reasonable thing to do
next
– Use a table of differences to identify procedures to reduce types of differences
– GPS was a state space planner: it operated in the domain of state space problems specified by
an initial state, some goal states, and a set of operations
Situation calculus planning
• Intuition: Represent the planning problem using first-order logic
– Situation calculus lets us reason about changes in the world
– Use theorem proving to “prove” that a particular sequence of actions, when applied to the
situation characterizing the world state, will lead to a desired result
Situation calculus
– Initial state: a logical sentence about (situation) S0
At(Home, S0) ^ ~Have(Milk, S0) ^ ~ Have(Bananas, S0) ^ ~Have(Drill, S0)
– Goal state:
(s) At(Home,s) ^ Have(Milk,s) ^ Have(Bananas,s) ^ Have(Drill,s)
– Operators are descriptions of how the world changes as a result of the agent’s actions:
(a,s) Have(Milk,Result(a,s)) <=> ((a=Buy(Milk) ^ At(Grocery,s)) (Have(Milk, s) ^
a~=Drop(Milk)))
– Result(a,s) names the situation resulting from executing action a in situation s.
– Action sequences are also useful: Result'(l,s) is the result of executing the list of actions (l)
starting in s:
(s) Result'([],s) = s
(a,p,s) Result'([a|p]s) = Result'(p,Result(a,s))
Basic representations for planning
– Classic approach first used in the STRIPS planner circa 1970
III YR /VI SEM Page 3
Academic Year 2016-2017(EVEN SEM)
Planning and Learning: Planning with state space search - conditional planning-continuous
planning - Multi-Agent planning. Forms of learning - inductive learning - Reinforcement Learning -
learning decision trees - Neural Net learning and Genetic learning
1.What is Planning in AI?Explain the Planning done by an agent?
Planning problem
– Find a sequence of actions that achieves a given goal when executed from a given initial
world state. That is, given
– a set of operator descriptions (defining the possible primitive actions by the agent),
– an initial state description, and
– a goal state description or predicate,
compute a plan, which is
– a sequence of operator instances, such that executing them in the initial state will change the
world to a state satisfying the goal-state description.
– Goals are usually specified as a conjunction of goals to be achieved
An Agent Architecture
Planning vs. problem solving
– Planning and problem solving methods can often solve the same sorts of problems
– Planning is more powerful because of the representations and methods used
– States, goals, and actions are decomposed into sets of sentences (usually in first-order logic)
III YR /VI SEM Page 1
,ITT63 ARTIFICIAL INTELLIGENCE UNIT IV
– Search often proceeds through plan space rather than state space (though there are also state-
space planners)
– Subgoals can be planned independently, reducing the complexity of the planning problem
Typical assumptions
– Atomic time: Each action is indivisible
– No concurrent actions are allowed (though actions do not need to be ordered with respect to
each other in the plan)
– Deterministic actions: The result of actions are completely determined—there is no
uncertainty in their effects
– Agent is the sole cause of change in the world
– Agent is omniscient: Has complete knowledge of the state of the world
– Closed World Assumption: everything known to be true in the world is included in the state
description. Anything not listed is false.
Blocks world
The blocks world is a micro-world that consists of a table, a set of blocks and a robot hand.
Some domain constraints:
– Only one block can be on another block
– Any number of blocks can be on the table
– The hand can only hold one block
Typical representation:
ontable(a)
ontable(c)
on(b,a)
handempty
clear(b)
clear(c)
General Problem Solver
III YR /VI SEM Page 2
, ITT63 ARTIFICIAL INTELLIGENCE UNIT IV
– The General Problem Solver (GPS) system was an early planner (Newell, Shaw, and Simon)
– GPS generated actions that reduced the difference between some state and a goal state
– GPS used Means-Ends Analysis
– Compare what is given or known with what is desired and select a reasonable thing to do
next
– Use a table of differences to identify procedures to reduce types of differences
– GPS was a state space planner: it operated in the domain of state space problems specified by
an initial state, some goal states, and a set of operations
Situation calculus planning
• Intuition: Represent the planning problem using first-order logic
– Situation calculus lets us reason about changes in the world
– Use theorem proving to “prove” that a particular sequence of actions, when applied to the
situation characterizing the world state, will lead to a desired result
Situation calculus
– Initial state: a logical sentence about (situation) S0
At(Home, S0) ^ ~Have(Milk, S0) ^ ~ Have(Bananas, S0) ^ ~Have(Drill, S0)
– Goal state:
(s) At(Home,s) ^ Have(Milk,s) ^ Have(Bananas,s) ^ Have(Drill,s)
– Operators are descriptions of how the world changes as a result of the agent’s actions:
(a,s) Have(Milk,Result(a,s)) <=> ((a=Buy(Milk) ^ At(Grocery,s)) (Have(Milk, s) ^
a~=Drop(Milk)))
– Result(a,s) names the situation resulting from executing action a in situation s.
– Action sequences are also useful: Result'(l,s) is the result of executing the list of actions (l)
starting in s:
(s) Result'([],s) = s
(a,p,s) Result'([a|p]s) = Result'(p,Result(a,s))
Basic representations for planning
– Classic approach first used in the STRIPS planner circa 1970
III YR /VI SEM Page 3
