Classical Planners use the STRIPS (Stanford Research Institute Problem Solver)
language to describe states and operators. It is an efficient way to represent planning
algorithms.
Representation of States and Goals
States are represented by conjunctions of function-free ground literals, that is, predicates
applied to constant symbols, possibly negated.
An example of an initial state is:
At(Home)
/\ -
Have(Milk)
/\ -
Have(Bananas)
/\ -
Have(Drill)
/\ ...
A state description does not have to be complete. We just want to obtain a successful plan
to a set of possible complete states. But if it does not mention a given positive literal, then
the literal can be assumed to be false.
Goals are a conjunction of literals. Therefore the goal is
Saturday, November 27, 2010
Friday, November 26, 2010
ProblemSolving Vs Planning.
Problem Solving vs. Planning
A simple planning agent is very similar to problem-solving agents in that it constructs
plans that achieve its goals, and then executes them. The limitations of the problem-
solving approach motivates the design of planning systems.
To solve a planning problem using a state-space search approach we would let the:
• initial state = initial situation
• goal-test predicate = goal state description
• successor function computed from the set of operators
• once a goal is found, solution plan is the sequence of operators in the path from
the start node to the goal node In searches, operators are used simply to generate successor states and we
can not look "inside" an operator to see how it’s defined. The goal-test predicate also is used as a
"black box" to test if a state is a goal or not. The search cannot use properties of how a
goal is defined in order to reason about finding path to that goal.
Hence this approach is all algorithm and representation weak.
Planning is considered different from problem solving because of the difference in the
way they represent states, goals, actions, and the differences in the way they construct
action sequences. Remember the search-based problem solver had four basic elements:
• Representations of actions: programs that develop successor state descriptions which
represent actions.
• Representation of state: every state description is complete. This is because a
complete description of the initial state is given, and actions are represented by a program
that creates complete state descriptions.
• Representation of goals: a problem solving agent has only information about it's
goal, which is in terms of a goal test and the heuristic function.
• Representation of plans: in problem solving, the solution is a sequence of actions.
In a simple problem:
"Get a quart of milk and a bunch of bananas and a variable speed
cordless drill" for a problem solving exercise we need to specify:
Initial State: the agent is at home without any objects that he is wanting.
Operator Set: everything the agent can do.
Heuristic function: the # of things that have not yet been acquired.
Problems with Problem solving agent: It is evident from the above figure that the actual branching factor
would be in the thousands or millions. The heuristic evaluation function can only choose states to
determine which one is closer to the goal. It cannot eliminate actions from
consideration. The agent makes guesses by considering actions and the evaluation
function ranks those guesses. The agent picks the best guess, but then has no idea
what to try next and therefore starts guessing again. It considers sequences of actions beginning from the
initial state. The agent is
forced to decide what to do in the initial state first, where possible choices are to
go to any of the next places. Until the agent decides how to acquire the objects, it
can't decide where to go.Planning emphasizes what is in operator and goal representations. There are three
key ideas behind planning:to "open up" the representations
of state, goals, and operators so that a reasoner
can more intelligently select actions when they are needed
the planner is free to add actions to the plan
wherever they are needed, rather
than in an incremental sequence starting at the initial state
most parts of the world are independent of most other parts
which makes it feasible to take a conjunctive goal and solve it with a divide-and-conquer strategy
A simple planning agent is very similar to problem-solving agents in that it constructs
plans that achieve its goals, and then executes them. The limitations of the problem-
solving approach motivates the design of planning systems.
To solve a planning problem using a state-space search approach we would let the:
• initial state = initial situation
• goal-test predicate = goal state description
• successor function computed from the set of operators
• once a goal is found, solution plan is the sequence of operators in the path from
the start node to the goal node In searches, operators are used simply to generate successor states and we
can not look "inside" an operator to see how it’s defined. The goal-test predicate also is used as a
"black box" to test if a state is a goal or not. The search cannot use properties of how a
goal is defined in order to reason about finding path to that goal.
Hence this approach is all algorithm and representation weak.
Planning is considered different from problem solving because of the difference in the
way they represent states, goals, actions, and the differences in the way they construct
action sequences. Remember the search-based problem solver had four basic elements:
• Representations of actions: programs that develop successor state descriptions which
represent actions.
• Representation of state: every state description is complete. This is because a
complete description of the initial state is given, and actions are represented by a program
that creates complete state descriptions.
• Representation of goals: a problem solving agent has only information about it's
goal, which is in terms of a goal test and the heuristic function.
• Representation of plans: in problem solving, the solution is a sequence of actions.
In a simple problem:
"Get a quart of milk and a bunch of bananas and a variable speed
cordless drill" for a problem solving exercise we need to specify:
Initial State: the agent is at home without any objects that he is wanting.
Operator Set: everything the agent can do.
Heuristic function: the # of things that have not yet been acquired.
Problems with Problem solving agent: It is evident from the above figure that the actual branching factor
would be in the thousands or millions. The heuristic evaluation function can only choose states to
determine which one is closer to the goal. It cannot eliminate actions from
consideration. The agent makes guesses by considering actions and the evaluation
function ranks those guesses. The agent picks the best guess, but then has no idea
what to try next and therefore starts guessing again. It considers sequences of actions beginning from the
initial state. The agent is
forced to decide what to do in the initial state first, where possible choices are to
go to any of the next places. Until the agent decides how to acquire the objects, it
can't decide where to go.Planning emphasizes what is in operator and goal representations. There are three
key ideas behind planning:to "open up" the representations
of state, goals, and operators so that a reasoner
can more intelligently select actions when they are needed
the planner is free to add actions to the plan
wherever they are needed, rather
than in an incremental sequence starting at the initial state
most parts of the world are independent of most other parts
which makes it feasible to take a conjunctive goal and solve it with a divide-and-conquer strategy
Algorithem simple Planning Agent.
1. Generate a goal to achieve
2. Construct a plan to achieve goal from current state
3. Execute plan until finished
4. Begin again with new goal
The agent first generates a goal to achieve, and then constructs a plan to achieve it from
the current state. Once it has a plan, it keeps executing it until the plan is finished, then
begins again with a new goal.
Assumptions:
A simple planning agent create and use plans based on the following assumptions:
Atomic time :each action is indivisible
No concurrent actions : allowed
Deterministic actions : result of each actions is completely determined by the
definition of the action, and there is no uncertainty in performing it in the world.
Agent is the sole cause of change: in the world.
Agent is omniscient : has complete knowledge of the state of the world
2. Construct a plan to achieve goal from current state
3. Execute plan until finished
4. Begin again with new goal
The agent first generates a goal to achieve, and then constructs a plan to achieve it from
the current state. Once it has a plan, it keeps executing it until the plan is finished, then
begins again with a new goal.
Assumptions:
A simple planning agent create and use plans based on the following assumptions:
Atomic time :each action is indivisible
No concurrent actions : allowed
Deterministic actions : result of each actions is completely determined by the
definition of the action, and there is no uncertainty in performing it in the world.
Agent is the sole cause of change: in the world.
Agent is omniscient : has complete knowledge of the state of the world
LogicBasedPlanning.
Introduction to Planning
The purpose of planning is to find a sequence of actions that achieves a given goal when
performed starting in a given state. In other words, given a set of operator instances
(defining the possible primitive actions by the agent), an initial state description, and a
goal state description or predicate, the planning agent computes a plan.
What is a plan?
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.
Simple Planning Agent:
Earlier we saw that
problem-solving agents
are able to plan ahead - to consider the
consequences of sequences
of actions - before acting. We also saw that a knowledge-based agents can select actions based on explicit, logical representations of the current state and the effects of actions. This allows the agent to succeed in complex, inaccessible environments that are too difficult for a problem-solving agent
Problem Solving Agents + Knowledge-based Agents = Planning Agents
In this module, we put these two ideas together to build
planning agents.
At the most abstract level, the task of planning is the same as problem solving. Planning can be
viewed as a type of problem solving in which the agent uses beliefs about actions and
their consequences to search for a solution over the more abstract space of plans, rather than over the space of situations
Planning.!
The students should understand the formulation of planning problems
The student should understand the difference between problem solving and planning
and the need for knowledge representation in large scale problem solving
Students should understand the STRIPS planning language
Students should be able to represent a real life planning problem using STRIPS
operators
Students should understand planning using situation calculus and the related frame
problems
Students should understand the formulation of planning as a search problem
Students should learn the following planning algorithms
Situation space planning
Plan space planning
Progression planning
Regression planning
The student should understand the difficulties of full commitment planning
Students should understand the necessity of least commitment
Students should learn partial order planning algorithms
At the end of this lesson the student should be able to do the following:
Represent a planning problem in STRIPS language
Use a suitable planning algorithm to solve the problem.
The student should understand the difference between problem solving and planning
and the need for knowledge representation in large scale problem solving
Students should understand the STRIPS planning language
Students should be able to represent a real life planning problem using STRIPS
operators
Students should understand planning using situation calculus and the related frame
problems
Students should understand the formulation of planning as a search problem
Students should learn the following planning algorithms
Situation space planning
Plan space planning
Progression planning
Regression planning
The student should understand the difficulties of full commitment planning
Students should understand the necessity of least commitment
Students should learn partial order planning algorithms
At the end of this lesson the student should be able to do the following:
Represent a planning problem in STRIPS language
Use a suitable planning algorithm to solve the problem.
Subscribe to:
Posts (Atom)