Abstract
We introduce a novel approach to the smart execution of scenario-based models of reactive systems, such as those resulting from the multi-modal inter-object language of live sequence charts (LSCs). Our approach finds multiple execution paths from a given state of the system, and allows the user to interactively traverse them. The method is based on translating the problem of finding a superstep of execution into a problem in the AI planning domain, and issuing a known planning algorithm, which we have had to modify and strengthen for our purposes.
This research was supported by the John von Neumann Minerva Center for the Development of Reactive Systems at the Weizmann Institute of Science.
This is a somewhat shortened conference version of the paper. The full version [16] can be obtained by emailing one of the authors.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barner, S., et al.: An Algorithmic Approach to Design Exploration. In: Eriksson, L.-H., Lindsay, P.A. (eds.) FME 2002. LNCS, vol. 2391, pp. 146–162. Springer, Heidelberg (2002)
Blum, A., Furst, M.: Fast Planning Through Planning Graph Analysis. In: Proc. 14th Intl. Joint Conf. on Artificial Intelligence, pp. 1636–1642 (1995), (Extended version appears in Artificial Intelligence 90(1-2), 281–300 (1997))
Bonet, B., Geffner, H.: HSP: Heuristic Search Planner. In: Proc. 4th Intl. Conf. on Artificial Intelligence Planning Systems (AIPS’98) Planning Competition, Pittsburgh (1998)
Damm, W., Harel, D.: LSCs: Breathing life into message sequence charts. Formal Methods in System Design 19(1) (2001), Preliminary version appeared in Proc. 3rd IFIP Int. Conf. on Formal Methods for Open Object-Based Distributed Systems (FMOODS’99)
Ernst, M., Millstein, T., Weld, D.: Automatic SAT-Compilation of Planning Problems. In: Proc. 15th Intl. Joint Conf. on Artificial Intelligence (IJCAI’97), pp. 1169–1176 (1997)
Erol, K., Nau, D.S., Subrahmanian, V.S.: Complexity, Decidability and Undecidability Results for Domain-Independent Planning. Artificial Intelligence 76(1-2), 75–88 (1995)
Fikes, R., Nilsson, N.: STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Journal of Artificial Intelligence 2(3-4), 189–208 (1971)
Gilboa, A.: Finding all Possible Supersteps in LSCs. MSC Thesis, The Weizmann Institute of Science (2003)
Glusman, M., et al.: Multiple-Counterexample guided Iterative Abstraction Refinement: An Industrial Evaluation. In: Garavel, H., Hatcliff, J. (eds.) ETAPS 2003 and TACAS 2003. LNCS, vol. 2619, pp. 176–191. Springer, Heidelberg (2003)
Harel, D., et al.: Smart Play-Out of Behavioral Requirements. In: Aagaard, M.D., O’Leary, J.W. (eds.) FMCAD 2002. LNCS, vol. 2517, pp. 378–398. Springer, Heidelberg (2002)
Harel, D., Kugler, H., Pnueli, A.: Smart Play-Out Extended: Time and Forbidden Elements. In: Proc. 4th Int. Conf. on Quality Software (QSIC’04), pp. 2–10. IEEE Computer Society Press, Los Alamitos (2004)
Harel, D., Maoz, S.: Assert and Negate Revisited: Modal Semantics for UML Sequence Diagrams. In: Proc. 5th Int. Workshop on Scenarios and State Machines: Models, Algorithms and Tools (SCESM’06), pp. 13–20 (2006)
Harel, D., Maoz, S.: From Multi-Modal Scenarios to Code: Compiling LSCs into AspectJ. In: 14th ACM SIGSOFT Symp. on Foundations of Software Engineering (FSE’14), Portland (November 2006)
Harel, D., Marelly, R.: Come, Let’s Play: Scenario-Based Programming Using LSCs and the Play-Engine. Springer, Heidelberg (2003)
Harel, D., Marelly, R.: Specifying and Executing Behavioral Requirements: The Play-In/Play-Out Approach. Software and Systems Modeling (SoSyM) 2, 82–107 (2003)
Harel, D., Segall, I.: Planned and Traversable Play-Out: A Flexible Method for Executing Scenario-Based Programs. Technical Report MCS07-01, The Weizmann Institute of Science (2007)
Hoffmann, J., Koehler, J.: A new Method to Query and Index Sets. In: Proc. 16th Intl. Joint Conf. on Artificial Intelligence (IJCAI’99), pp. 462–467 (1999)
Hoffmann, J., Nebel, B.: The FF Planning System: Fast Plan Generation Through Heuristic Search. J. Artificial Intelligence Research 14, 253–302 (2001)
http://www.wisdom.weizmann.ac.il/~itais/video/TPO-Example.avi
IPP website: http://www.informatik.uni-freiburg.de/~koehler/ipp.html
ITU-TS Recommendation Z.120: Message Sequence Chart (MSC). ITU-TS, Geneva (1996)
Kautz, H., Selman, B.: Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search. In: Proc. 13th National Conf. on Artificial Intelligence (AAAI’96), Portland, pp. 1194–1201 (1996)
Kautz, H., Selman, B.: Blackbox: A New Approach to the Application of Theorem Proving to Problem Solving. In: Workshop on Planning as Combinatorial Search, Artificial Intelligence Planning Systems (AIPS’98), June 1998, pp. 58–60 (1998)
Koehler, J.: Planning under Resource Constraints. In: 13th biennial European Conf. on Artificial Intelligence (ECAI’98), pp. 489–493 (1998)
Koehler, J., et al.: Extending Planning Graphs to an ADL Subset. In: Steel, S. (ed.) ECP 1997. LNCS, vol. 1348, pp. 273–285. Springer, Heidelberg (1997)
Long, D., Fox, M.: Efficient Implementation of the Plan Graph in STAN. Journal of Artificial Intelligence Research 10, 87–115 (1999)
Pednault, E.P.D.: ADL: Exploring the Middle Ground Between STRIPS and the Situation Calculus. In: Proc. 1st Intl. Conf. on Principles of Knowledge Representation and Reasoning, Toronto, pp. 324–332 (1989)
UML: Documentation of the unified modeling language (UML). Available from the Object Management Group (OMG), http://www.omg.org
Veloso, M.M.: Nonlinear problem solving using intelligent casual-commitment. Technical Report CMU-CS-89-210, School of Computer Science, Carnegie Mellon University (1989)
Wang, T., et al.: Symbolic Execution of Behavioral Requirements. In: Jayaraman, B. (ed.) PADL 2004. LNCS, vol. 3057, pp. 178–192. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Harel, D., Segall, I. (2007). Planned and Traversable Play-Out: A Flexible Method for Executing Scenario-Based Programs, . In: Grumberg, O., Huth, M. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2007. Lecture Notes in Computer Science, vol 4424. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-71209-1_37
Download citation
DOI: https://doi.org/10.1007/978-3-540-71209-1_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-71208-4
Online ISBN: 978-3-540-71209-1
eBook Packages: Computer ScienceComputer Science (R0)