08 Planning and acting Flashcards

1
Q

Classical planners assume…

…but in the real world…

A

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!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Time, schedules, and resources

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Scheduling - No resource constraints

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Scheduling with resource constraints

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Reduce complexity by decomposition

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Planning in nondeterministic domains

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Sensorless planning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Contingent planning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Online replanning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Contingent planning vs. online replanning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Continuous spectrum of planners

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Continuous planning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Multi-agent planning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Coordination of multi-agent planning

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly