2002 · 46 citations · 11 references
ComputingComputer ScienceSystems EngineeringFormal MethodsModel-based Systems EngineeringSystems ArchitectureFinite State Machine ModelingModel CheckingMulti-agent SystemsPetri NetsPredicate LogicAgent PlanningHigh-level Petri NetsMulti-agent PlanningPetri Net AnalysisPetri Net ModelsPetri Net VerificationReachabilityReachability Analysis
In a multi-agent system, how agents accomplish a goal task is usually specified by multi-agent plans built from basic actions (e.g. operators) of which the agents are capable. A critical problem with such an approach is how can the designer make sure the plans are reliable. To tackle this problem, this paper presents a formal approach for modeling and analyzing multi-agent behaviors using Predicate/Transition (PrT) nets, a high-level formalism of Petri nets. We construct a multi-agent model by representing agent capabilities as transitions. To verify a multi-agent PrT model, we adapt the planning graphs as a compact structure for the reachability analysis. We also demonstrate that, based on the PrT model, whether parallel actions specified in multi-agent plans can be executed in parallel and whether the plans guarantee the achievement of the goal can be verified by analyzing the dependency relations among the transitions.
11
Petri nets: Properties, analysis and applications
T. Murata · Proceedings of the IEEE · 1989 · 10.5K citations
Intention is choice with commitment
Philip R. Cohen, Hector J. Levesque · Artificial Intelligence · 1990 · 1.9K citations
Fast planning through planning graph analysis
Avrim Blum, Merrick L. Furst · Artificial Intelligence · 1997 · 1.6K citations
Collaborative plans for complex group action
Barbara J. Grosz, Sarit Kraus · Artificial Intelligence · 1996 · 970 citations · Full text
A specifier's introduction to formal methods