1、Multiagent Planning regarding ResourceconstraintsPresented by: Bo Hui Presentation PlanMultiagent SystemCooperative planningA specific study in a certain context (a paper in AAMAS-2003)ConclusionMultiagent System(MAS) a loosely coupled network of that interact to solve problems that are beyond the i

2、ndividual capacities or knowledge of . Why MAS?Real problems are too large and complex for a single agent Individual agents are limited by its knowledge, computing resources, and perspectiveProvide efficient solutions where resources are spatially distributed Distributed sensors, seismic monitoring,

3、 information gatheringProvide solutions where expertise is distributed Concurrent engineering, manufacturing, health careMAS CharacteristicsModular, distributed systemsDecentralized dataAgent has incomplete information or capabilitiesNo global system controlAsynchronous computationCooperative Planni

4、ng(1) is an important topic in MAS Objectives: coordinate plans share resources share goalsCooperative Planning(2) is used for two reasons:there exist problems that cannot be solved by a single agent in isolation improve efficiency and save cost even problems can be solved on their own Cooperative P

5、lanning(3) An example in Supply Chain Management:First, a chain manager assigns each agent a part of task; next, the agents create their plans to complete their part of task;finally, the chain manager analyses these plans and may insist on cooperation between some agents ; In such cases, cooperation

6、 can be accomplished by plan revision : an agent tries to revise part of its plan by exchanging resources and goals with other agents.Cooperative Planning(4) Most existing research:Negotiation Plan mergingMultiagent MDPs(Markov Decision Processes)(Generic) Partial Global Planning Common points To av

7、oid conflicts Assume sufficient resourcesCooperative Planning(5) An important consideration How much an agent knows ahead of time about the other agents?3 possibilities: knowing nothing knowing everything need to know knowing somePaper studyTitle“Multiagent Planning for Agents with Internal Executio

8、n Resource Constraints”O(jiān)bjective Study how agents can cooperate to revise their plans as they attempt to ensure not over-use their local resourcesIntroduction(1)ConceptsUnconditional events e.g., rockslides in the roadConditional events e.g., merging trafficExecution resources include the perceptual

9、, effectual, and reasoning capabilities during executionIntroduction(2)An ideal agent could manage its resources to respond rapidly and correctly to all events of both typesto guarantee hard real-time performanceIntroduction(3)A realistic agentExecution resources are constrainedHave to give up on gu

10、aranteeing timely responses to some events Concentrate their resources on other more important demands (e.g., the driver might focus on traffic ahead at the expense of missing signs for an exit.) Might modify their behaviors to elongate reaction times for events (e.g., drive more slowly)Adopt restri

11、ctions on their behaviors to eliminate some dangerous controllable events (e.g., drive on the right), Share information to help each other know what conditional events to be prepared for (e.g., use directional signals).Strategy in generalThe agent prioritizes its use of resources by planning for eve

12、nts in order of their occurrence probabilitiesUnlikely events are ignored in case of insufficient resources.CIRCACooperative Intelligent Real-time Control ArchitectureRealizes the strategy in MAS with execution resources constraintsModels the interactions between actions and (conditional and uncondi

13、tional) eventsSelects, schedules, and executes recognition-reactionsTwo componentsAIS (Artificial Intelligence Subsystem)Probabilistic PlannerSearches through the state space to determine the appropriate reactions for hazardous states.generates a set of recognition-reactions (TAPs).Choose the period

14、 for each TAP.SchedulerBases on the resource constraints of the RTSSchedules the set of TAPs according to their periods.RTS (Real-Time Subsystem) executes the real-time control plans pre-computed by the AIS.Concepts(1)TAPsTest-Action-Pairs, recognition reactionThe recognition test is done by activel

15、y collecting data or monitor for the relevant aspects of the world.A reaction is only executed if the world matches the state description in the corresponding recognition test. are also referred as “actions” laterConcepts(2)Control Plan is composed of a scheduled set of recognition reaction pairs is

16、 a cyclic (periodic) real-time schedule of TAPs.Processor utilization of each TAP u = (worst testing time + worst execution time)/periodConcepts(3)unlikely state (cutoff) heuristicif u 1 in a set of TAPs, no schedule is possible! In this case, CIRCA computes the probabilities, called state probabili

17、ties, of the agent reaching different states based on its local state diagram. It finds a subset of the TAPs by removing those planned for states with state probabilities below a threshold.It keeps increasing this threshold until a schedulable subset is found.Problem: The failure probability may inc

18、rease when it is appliedConcepts(4)Necessary actions are those that an agent may have to perform during execution to preempt some hazards.are planned for unconditional events and some conditional eventsUnnecessary actions are those that the agent includes in its plan due to its ignorance about the p

19、lans of other agents. are planned for those conditional events that will not arise.To identify and remove enough unnecessary actions to deal with “heuristic problem”Concepts(5)State-space representation is constructed from a set of state propositions, called state features actions events, called tra

20、nsitionsA state consists of a set of state features that describe the different aspects of the world.Two types transitions Action transitions, controlled by plan executor in RTS. Temporal transitions, events outside the systems control.Concepts(6)Temporal transitionsTwo types:innocuous temporal tran

21、sitions (labeled tt) ordeleterious temporal transitions leading to system failure (labeled ttf) Any temporal transition is described by:A PreconditionAn effectA probability functiondescribes the probability of a transition happening as a function of the time since it was enabled, independently of ot

22、her transitions.Concepts(7)Guaranteed actionsWhen there is a ttf in a state, CIRCA plans a TAP to preempt the hazard. Preempting actions are called guaranteed actions.Reliable actions is another type of action, which is also scheduled with real-time deadlines and thus utilize resources. However, the

23、y do not preempt any explicit failures.Concepts(8)Private (local) featuresare those that no other agents are interested in, e.g. its current fuel level.Do not appear in the state diagrams of other agents.Public (shared) features are those features that more than one agent is interested in. An agent

24、includes in its feature set only the public features that it cares about.It is through manipulating the public features that agents impact each other.Concepts(9)Furthermore, a CIRCA agent includes:Some public temporal transitions (labeled tts)Some public temporal action transitions (labeled ttacs)Of

25、 other agents into its KB Tts and ttacs can affect the public features the agent cares about.A State diagramThe diagram shown in next page is a partial state diagram for an agent named FIGHTER. It is also the reachability graph for FIGHTER.Action SHOOT-MISSILE-1 is a guaranteed action to preempt the

26、 ttf BEING-ATTACKED.Action HEAD-TO-LOC1 is a reliable action and private for FIGHTER.COMM and ENEMY are public features shared by both BOMBER and FIGHTERHEADINGF and LOCF are private features that are accessible only to FIGHTER.B:BOMB-1 and B:BOMB-2 are public actions of BOMBERThe temporal transitio

27、ns FLY-TO-LOC0, FLY-TO-LOC1, and FLYTO-LOC2 are private for FIGHTER.State diagram for FIGHTERCOMM = FENEMY = FHEADINGF = NULLLOCF = LOC0FAILURE = FCOMM = FENEMY = FHEADINGF = LOC1LOCF = LOC0FAILURE = FCOMM = FENEMY = THEADINGF = NULLLOCF = LOC1FAILURE = FCOMM = FENEMY = FHEADINGF = NULLLOCF = LOC1FA

28、ILURE = FCOMM = FENEMY = THEADINGF = NULLLOCF = LOC1FAILURE = TCOMM = FENEMY = FHEADINGF = LOC2LOCF = LOC1FAILURE = FCOMM = FENEMY = FHEADINGF = NULLLOCF = LOC2FAILURE = FCOMM = FENEMY = FHEADINGF = LOC0LOCF = LOC2FAILURE = FCOMM = FENEMY = THEADINGF = NULLLOCF = LOC2FAILURE = FCOMM = FENEMY = THEAD

29、INGF = NULLLOCF = LOC2FAILURE = THEAD-TO-LOC1FLY-TO-LOC1B:BOMB-1SHOOT-MISSILE-1BEING-ATTACKEDHEAD-TO-LOC2FLY-TO-LOC2B:BOMB-2SHOOT-MISSILE-2HEAD-TO-LOC0BEING-ATTACKEDACTIONTT OR TTACGOALSTATEWITH DOTTED EDGEFAILURESTATEWITHTHICKBORDERPUBLIC FEATURES/ACTIONS/TEMPORALS IN ITALICPRIVATE FEATURES/.ACTION

30、S.TEMORALS TTACS IN NORMALFLY-TO-LOC0Reachability analysisA rational agent need to foresee what actions other agents might take, and choose its own actions accordingly.To play it most safe, the agent must consider and plan for all states that it foresees, such an analysis is a reachability analysis.

31、However, some states that might never ariseunreachable states.Unreachable states are included in a reachability graph only because of ignorance at beginning and can be removed if they can be recognized as such.In an ideal case, an agent need not to know other agents plan. But due to resources constr

32、aints, it need to know intersecting parts of their plans.Convergence Protocol(1)Benefits: Agents can identify unreachable states in the state diagrams andeliminate the associated actions from their tentative plans.e.g., in the figure before.Assumption before using it:they have locally formed their r

33、eachability graphs and have selected all actions they would like to take (as if there were no resource constraints).Convergence Protocol(2)Inquiring agent () Choose the uncertain point that gives the biggest estimated utilization reduction; /*Ask the corresponding agent which action(s) it will take;

34、Upon receiving an answer, update the state diagram and drop unnecessary actions from the local plan;Loop until either the resource constraints are satisfied or all uncertain points are examined;Answering agent () When (being asked by another agent about an uncertain point) Identify the corresponding

35、 state(s) in the local graph;Reply with the action(s) (or none) planned for the state(s);Record the agents name with the state(s);If (an action is removed from its state diagram/plan) /*Inform all agents with names recorded with the state that the action is no longer planned for that state;Convergen

36、ce Protocol(3)Main points: Uncertain points: is a combination of a state and a set of mutually exclusive ttacs.If the agent starts with sufficient resources, then it is guaranteed to find a plan that schedules all the actions. And the agents utility is not compromised.If an agent fails to schedule f

37、or all remaining actions, it resorts to the unlikely state heuristic to remove the most unlikely (but possibly necessary) actions. And the agents utility decreases only when it drops some necessary actions by raising the probability threshold.DemonstrationBoth FIGHTER and BOMBER have 5 actions to sc

38、hedule if they do not know anothers plan. See The Reachability Graph for BOMBERSuppose the resource constraints are simplified such that each agent can schedule only 4 TAPs.By running the Convergence Protocol, FIGHTER asks BOMBER what actions it plans when (COMM = F) & (ENEMY = F)We can see the resu

39、ltsEvaluation(1)Experiment environment:A set of random domains.Each domain has a random number of agents from 2 up to a maximum of 10. Each agent has its own knowledge base. The knowledge base has 7 private and public binary features (T/F) total. The number of public features in a domain is random.T

40、here are 15 private and public actions combined, and 7 private and public temporal transitions combined for each agent.We have generated 1126 agents (KBs) for 402 domains with which we perform our experiments.Evaluation(3)Experiment results (following):Action effectiveness is the percentage of unnec

41、essary actions removed by the protocol.The average effectiveness is 51.74% and the standard deviation is 35.84%State effectiveness is the percentage of states included in an agents reachability graph but removed by the protocol.The average effectiveness is 53.74% and the standard deviation is 29.45%.The data suggest tha