---------------------------------------------------------------------------- Notetaker - Eric Date - March 6 2000 Subject - Resources (Smith's 4.1) Exchange with Megan ---------------------------------------------------------------------------- Announcements: Exam will be given out after Spring Break Projects proposed so far Eric - Planning in Dynamic Environments [Added by Megan: Rao summary: If I tell my agent to cross the road and the next time I look my agent is road kill is my action stochastic or did another agent kill my agent. Assume my action was not at fault. That is make plans and start execution. If something goes wrong deal with it.] Megan - ILP Encodings [Added by Megan: Issues to look at: If a problem can be represented with SAT encoding why do you need ILP and If some features of the problem can not be represented in SAT and others can how do you split the problem between SAT and ILP.] Nie - Information gathering actions [Added by Megan: You have environments that support causative (Blocks World), observational (Yahoo) and both (Wumpus World, OS) actions. One of the questions that comes up is that some actions give knowledge while others take away knowledge. How do you track this information, because otherwise you will oversense, which is costly, (without full observability.] Tuan - "Stable models for Scheduling" (non-monotonic logic) Binhminh - PCP scheduling Long - UCPOP search control This lead to a small review of Dynamic vs Static, Stochastic vs Deterministic, and Partially vs Fully observable environments. Dynamic environments involve those in which an external force (another agent) can change the state. Stochastic environments include those where the effects of an action are not completely known (only the probability of those effects). Partially observable means that the agents is not able to sense all information about the environment. [Added by Megan: also briefly talked about causative (planning) vs. observational (web) actions] Class Discussion Smith's Paper Resources (4.1) -We already know how to handle resources -Planning - good action selection -Scheduling - good resource allocation -Smith suggests that we need to combine the two to take advantage of both attributes. There are 3 methods that are possible: 1) Get a planner to consider aspects of scheduling (resources & time) [Added by Megan: this is Smith's suggestion] 2) Get a scheduler to consider action selection 3) Make planners and schedulers interact -(Ex. remove resources & time from the problem and plan. Then add resource & time constraint and give the plan to a scheduler. If the scheduler fails, then re-plan) -This runs the risk of ignoring vital information [Added by Megan: In order for this to work effectively both the planner and scheduler need to have an abstract idea of what the other one does. Without this element to many iterations between the planner and scheduler will occur.] -Planning (in theory) can handle resources, but more resources lead to greater complexity (Especially if resources are not scarce). -For multi-capacity resources, resolution of conflict has multiple possibilities -add disjunctive ordering constraints [Added by Megan: this would replace splitting up the disjunction in to the search space, which would reduce the number of nodes created and explored. The example Rao showed was: Suppose S1 < S2 or S3 < S4. If you kept the disjunctive constraint and eventually S2 < S1 then you would get that S3 < S4 automatically. This would obvisouly not occur when the disjunctions were split.] -split disjunction into search space -splitting disjunctions up front makes them easier to handle but leads to more failing choices and hinders performance [Added by Megan: not necessarily more failings, but the same failures are put into multiple paths.] -Schedulers have many of the same problems as planners when it comes to resolving conflicts for multi-capacity resources. [Added by Megan: The general problem with handling multi-capactiy resources is conflict detection and resolution. The interactions that occurs are no longer between single actions and single causal links, but sets. Say that machine X can handle 5 jobs. Currently 3 jobs have been assigned and 3 more jobs A1, A2 and A3 all want to use machine X. There are multiple ways to handle this conflict: 1. remove one job 3C1*2 possible orderings 2. remove two jobs 3C2 * 4 possible orderings 3. remove three jobs 3C3 * 8 possible orderings. The real problem occurs because who do you blame for the conflict. Furthermore, how do you resolve it so that it doesn't occur in the next iteration? ] [Added by Megan: Final thought, do you really want planners to handle single capacity resources? For example the multirobot blocksworld problem, as more robots are added the time to find a plan increases exponentially. This shows that the methods used for action selection may not be appropriate for resource selection. Is abstraction bad or good? If there are a small number of resources the planner could handle it and if there are a large number resource management could be seperate. OR Say, 1 resource is hard to organize (ie critical). The planner would deal with it. If the rest of the resources are easy to manage have the scheduler deal with them. ]