08 Planning and acting Flashcards
Classical planners assume…
…but in the real world…
Classical planners assume:
• Fully observable, static and deterministic domains
• Correct and complete action descriptions
• . . . allowing a “plan-first-then-act” planning approach
But in the real world:
• The world is dynamic, and time cannot be ignored
• Information on the world is incomplete and incorrect
• …so the agent must be prepared for unexpected events
Plus - scaling up to real-world problem size!
Time, schedules, and resources
The PDDL (Planning Domain Definition Language) language allows events (actions) and ordering of events, but not time duratio. In real-life planning, we must take duration, delays, etc. into account (not just ordering). Job shop scheduling:
• The problem is to complete a set of jobs
• Each job consists of a set of actions, with given duration and resource requirements
• Determine a schedule that minimizes total time (makespan) needed while respecting resource constraints
Must extend representation language to express duration and resource constraints
Scheduling - No resource constraints
Scheduling - No resource constraints
- Partial order plan produced by e.g. POP (Partial Order Planning)
- To create a schedule, we must place actions on a timeline
- Can use critical path method (CPM): the longest path, no slack - determines total duration
- Shortest duration schedule, given partial-order plan:
85 minutes
Scheduling with resource constraints
Actions typically require resources:
• Consumable resources - e.g. LugNuts
• Reusable resources - e.g. EngineHoists
Resource constraints make scheduling more complex because of interaction between actions. AI and OR (Operations Research) methods can be used to solve scheduling problems with resources
The approach shown here is common in real-world AI applications for manufacturing scheduling, airline scheduling, etc.:
• First generate partial-order plan without timing information (planning)
• Then use separate algorithm to find optimal (or satisfactory) time behavior (scheduling)
In some cases it may be better to interleave planning and scheduling, e.g. to consider temporal constraints
already at the planning stage
Reduce complexity by decomposition
It is often possible to reduce problem complexity by decompose to subproblems, solve independently, and assemble solution.
Hierarchical Task Networks (HTN):
• Planner keeps library of subplans
• Extend planning algorithm to use subplans
• Can reduce time&space requirements considerably
Most real-world planners use HTN variants
Planning in nondeterministic domains
Nondeterministic worlds:
• Bounded nondeterminism: Effects can be enumerated, but agent cannot know in advance which one will occur
• Unbounded nondeteminism: The set of possible effects is unbounded or too large to enumerate
Planning for bounded nondeterminism:
• Sensorless planning
• Contingent planning
Planning for unbounded nondeterminism:
• Online replanning
• Continuous planning
Sensorless planning
Agent has no sensors to tell which state it is in, therefore each action might lead to one of several possible outcomes. Must reason about sets of states (belief states), and make sure it arrives in a goal state regardless of where it comes from and results of actions. Nondeterminism of the environment does not matter - the agent cannot detect the difference anyway.
The required reasoning is often not feasible, and sensorless planning is therefore often not applicable
Contingent planning
Constructs conditional plans with branches for each (enumerable) possible situation. Decides which action to choose based on special sensing actions that become parts of the plan. Can also tackle partially observable domains by including reasoning about belief states (as in sensorless planning).
Planning algorithms have been extended to produce conditional branching plans
Online replanning
Monitors situation as plan unfold, detects when things go wrong. Performs replanning to find new ways to reach goals, if possible by repairing current plan
Example:
• Agent proceeds from S, and next expects E following original whole-plan
• Detects that it’s actually in O
• Creates a repair plan that takes it from O to a state
P in original plan
• New plan to reach G becomes repair +
continuation
Contingent planning vs. online replanning
Contingent planning:
• All actions in the real world have additional outcomes
• Number of possible outcomes grows exponentially with plan size, most of them are highly improbable
• Only one outcome will actually occur
Replanning:
• Basically assumes that no failure occurs
• Tries to fix problems as they occur
• May produce fragile plans, hard to fix if things go wrong
Continuous spectrum of planners
Contingent planning and replanning are extremes of a spectrum, where intermediate solutions exist
• Disjunctive outcomes for actions where more than one outcome is likely
• Agent can insert sensing action to detect what happened and construct corresponding conditional plan
• Other contingencies dealt with by replanning
More generally, agents in complex domains and with incomplete/incorrect information should: • Assess likelihood and costs of various outcomes
• Construct plan that maximizes probability of success and minimizes cost
• Ignore contingencies that are unlikely or easy to deal with
Continuous planning
The planner persists over time - never stops, and interleaves planning, sensing and execution. The continuously planning agent must:
• Execute steps of current plan (even if not complete) • Refine plan if not applicable or in conflict
• Modify plan in light of new information
• Formulate new goals when required
Planners, e.g. partial-order planning (POP) can be extended to provide required functionality
Multi-agent planning
Single-agent planning works against “nature”, but in many cases the environment includes other agents with their own goals. Multi-agent environments can be:
• Cooperative: Agents work together to achieve some common goal
• Competitive: Agents have conflicting goals
Multi-agent architectures and applications, incl. planning, represent very active AI research area
Coordination of multi-agent planning
Cooperative planning can produce joint plans. For each agent, the joint plan tells what to do. If each follows its plan, overall goal will be achieved. Problems arise if several joint plans are possible. Each agent must know which plan to follow. Requires some form of coordination.
Coordination can be by:
• Convention or social law
• Inter-agent communication
