DOC PREVIEW
MIT 16 412J - Temporal Planning and Resource Allocation

This preview shows page 1-2-3-4-30-31-32-33-34-62-63-64-65 out of 65 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 65 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Temporal Planning and Resource Allocation Stefanie Chiou Rob Kochman and Gary Look Running Plans in the Real World Need to account for time and resources when creating plans Papers featured Executing Reactive Model Based Programs through Graph Based Temporal Planning by Phil Kim Brian C Williams and Mark Abramson IJCAI 01 Managing Multiple Tasks in Complex Dynamic Environments by Michael Freed AAAI 98 Paper Executing Reactive Model based Programs through Graph based Temporal Planning by Phil Kim Brian Williams and Mark Abramson Familiar Examples Mars Climate Orbiter 12 11 98 Mars Polar Lander 1 3 99 Motivation Embedded programming is hard Easier to reason about state when programming Overview Contributions RMPL provides a new programming paradigm for programming robust systems of cooperative autonomous agents TPN synthesis of temporal causal link and HTN planning A holy grail for autonomous agents Planner that implements these ideas RMPL Intro RMPL supports four types of reasoning about system interactions reasoning about contingencies scheduling inferring hidden state controlling hidden state This paper focuses on first two interaction types Model based Embedded Programs Embedded programs interact with plant sensors actuators Model based programs interact with plant state Read sensors Read state Set actuators Write state Model based Embedded Program Embedded Program Obs Cntrl S Plant Programmer must map between state and sensors actuators setState getState S Plant Model based executive maps between sensors actuators to states Model based Embedded Program Breakdown Model based Embedded Program setState getStat e Model based Executive Sensor data S Plant Model based executive maps between sensors actuators to states Actuator commands Example The model based program sets engine thrusting and the deductive controller Oxidizer tank Deduces that thrust is off and the engine is healthy Fuel tank Plans actions to open six valves Determines that valves on the backup engine will achieve thrust and plans needed actions Deduces that a valve failed stuck closed Time and Contingency Constructs in RMPL if c thennext A do A maintaining C A B concurrency A B serialization A l u temporal bounds Choose A B choose RMPL Code Example Group Enroute l u Path 2 A choose do Path 1 Group Fly Path PATH1 l 90 u 90 maintaining PATH1 OK do B Group Fly Path PATH2 l 90 u 90 maintaining PATH2 OK Choosing a route from A to B Group Transmit FAC ARRIVED TAI 0 2 do Group Wait TAI HOLD1 TAI HOLD2 0 u 10 watching PROCEED OK RMPL s Representation of Time and Contingencies Important to find a plan quickly Idea use a plan graph Generalization of Simple Temporal Network STN TPN defined STN conditionals choices STN example Start End Temporal Planning Networks TPN A temporal planning network is just a generalization of a STN Includes ability to represent conditionals and choices TPN Example Ask Proceed Ok RMPL TPN conversion A l u invoke activity A between l and u time units RMPL TPN conversion c l u Assert that condition c is true now until l u RMPL TPN conversion If c thennext A l u Execute A for l u if condition c is currently satisfied RMPL TPN conversion do A l u maintaining c Execute A for l u and ensure that condition c holds throughout RMPL TPN conversion A l1 u1 B l2 u2 Concurrently execute A for l1 u1 and B for l2 u2 RMPL TPN conversion A l1 u1 B l2 u2 Execute A for l1 u1 and then B for l2 u2 RMPL TPN conversion choose A l1 u1 B l2 u2 Reduces to l1 u1 or B l2 u2 non deterministically A Kirk Compiles RMPL program into a TPN Searches TPN for a temporally consistent plan Temporally consistent plan is embedded into the TPN Kirk Phase1 Select plan from TPN Essentially a graph traversal Check Start plan for temporal consistency Selecting the Plan Start Start Checking for Temporal Consistency Convert TPN to a distance graph Run Bellman Ford to check for negative cycles if any found inconsistent Converting TPNs to Distance Graphs The interval aij bij represents the statement a ij Tj Ti bij This is equivalent to Tj Ti bij and Ti Tj aij 10 20 1 30 40 40 2 10 20 0 3 40 50 60 70 4 1 20 10 0 70 2 30 20 10 50 3 40 60 4 Checking for Temporal Consistency Convert TPN to a distance graph Run Bellman Ford algorithm to check for negative cycles Bellman Ford Algorithm initializeCosts G s for i 1 to V G 1 for each edge u v in E G updateCost u v w for each edge u v in E G if cost v cost u w u v return false return true Bellman Ford Example 40 20 Source 10 0 70 30 20 10 50 40 60 Bellman Ford Example 40 20 20 Source 10 0 70 30 20 10 50 40 60 Bellman Ford Example 40 20 20 Source 10 0 70 60 30 20 10 50 40 60 Bellman Ford Example 40 20 20 Source 10 0 70 60 30 20 10 50 50 40 60 Bellman Ford Example 40 20 20 Source 10 0 70 60 30 20 10 50 50 100 40 60 Bellman Ford Example 40 20 20 Source 10 0 70 60 30 20 10 50 50 70 40 60 Bellman Ford Example 40 20 20 Source 10 0 70 60 30 20 10 50 30 70 40 60 Bellman Ford Example 40 20 20 Source 10 0 70 50 30 20 10 50 30 70 40 60 Kirk Phase 2 Resolve threats and open conditions Analogous to threats and open conditions in causal link planning Identify intervals of inconsistent constraints using Floyd Warshall Order intervals to resolve threats Close open conditions by making sure open conditions satisfied by some action in the plan Why This Paper It s useful for our term project Vision Managing Multiple Tasks in Complex Dynamic Environments by Michael Freed AAAI 98 Achieve goals in task environments Complex Time pressured Uncertain Co existing Interacting APEX Goal ATC Goal simulate human air traffic controllers Largely routine activity Complexity due to many simple tasks Interruptions necessary APEX Goal ATC APEX Goal ATC APEX Goal ATC Resource Conflicts Separate tasks make incompatible demands What to do Determine relative priority of tasks Assign control to winner Deal with the loser Conflict Resolution Strategies Shed Eliminate low importance tasks When Demand Availability Delay Interrupt Introduces complications Circumvent Select methods that use different resources APEX Architecture Two Parts Resource Architecture Set of resources Cognitive Perceptual Motor Action Selection Component Action Selection Component commands events Resource Architecture perception actuators World Procedure Definition Language PDL Example Turning on headlights Procedure Definition Language PDL Example Turning on headlights procedure index turn on headlights step s1 clear hand left hand step s2 determine loc headlight ctl loc


View Full Document

MIT 16 412J - Temporal Planning and Resource Allocation

Documents in this Course
Load more
Download Temporal Planning and Resource Allocation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Temporal Planning and Resource Allocation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Temporal Planning and Resource Allocation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?