History

itSIMPLE 2.0: An Integrated Tool for Designing Planning Domains

Description
itSIMPLE 2.0: An Integrated Tool for Designing Planning Domains
Categories
Published
of 8
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
  itSIMPLE 2 . 0 : An Integrated Tool for Designing Planning Domains Tiago Stegun Vaquero 1 and  Victor Romero 1 and  Flavio Tonidandel 2 and  Jos´e Reinaldo Silva 1 1 Escola Polit´ecnica - Universidade de S˜ao PauloDesign Lab, Mechatronic and Mechanical Systems Department - S˜ao Paulo, Brazil 2 Centro Universit´ario da FEIIAAA - Artificial Intelligence Applied in Automation Lab - S˜ao Bernardo do Campo, Brazil { tiago.vaquero, victor.romero } @poli.usp.br, flaviot@fei.edu.br, reinaldo@usp.br Abstract A great effort has been made today in the area of Artifi-cial Intelligence for defining reliable automated plan-ning systems that can be applied in real life applica-tions. That leads to the need of a systematic design pro-cess, in which the initial phases are not neglected andwhere Knowledge and Requirement Engineering toolshave a fundamental role for supporting designers. Fol-lowing this principle, this paper presents the evolutionof thetool itSIMPLEwhich implementsaKEintegratedenvironment where designers can perform knowledgeacquisition, domain modeling, domain model analysis,model testing, maintenance and plan analysis processesby using different well-known languages such as UML,Petri Nets, PDDL and XML, each one of them withits best contribution. The tool supports users in an or-ganized object-oriented domain design process with afriendly and easy-to-use interface. Introduction The rising demand for reliable planning systems have be-come a great motivation to apply all developments alreadyachieved in real life applications. This scenario leads tothe need of a systematic design process, in which the ini-tial phases are not neglected and where Knowledge andRequirement Engineering tools and methodologies have afundamental role for supporting designers. These conceptshave been addressed in the planning community in severalinitiatives, such as the first International Competition onKnowledgeEngineeringforPlanningandScheduling- ICK-EPS 2005. This competition has brought extremely impor-tant knowledge and design engineering issues and showedpowerful tools, such as itSIMPLE (Vaquero, Tonidandel,& Silva 2005), ModPlan (Edelkamp & Mehler 2005) andGIPO(Simpson2005),allofthemassistingdesignerstobet-ter understand, specify, visualize, verify and validate theirplanning domain models.The itSIMPLE tool was designed to give support to usersduring the construction of a planning domain applicationmainly in the initial stages of the design life cycle. Theseinitial stages encompassprocesses suchas domainspecifica-tion, modeling, analysis, model testing and maintenance, all Copyright c  2007, Association for the Advancement of ArtificialIntelligence (www.aaai.org). All rights reserved. of them crucial for the success of the application. The evo-lution of the itSIMPLE, called itSIMPLE 2 . 0 , presents a en-hanced integrated environment with well-known represen-tation languages such as UML (OMG 2001), XML (Bray et al.  2004), Petri Nets (Murata 1989) and PDDL (Fox &Long 2003), each one of them with its best contribution tothe whole design process, leading designers from the infor-mality of real world requirements to formal domain mod-els. Starting with requirements elicitation, specification andmodeling, itSIMPLE proposes a special use of UML - Uni-fied Modeling Language - in a planning approach (namedUML.P) which we believe can contribute to the knowledgeacquisition process (from different viewpoints) as well as tothe domain model visualization and verification.itSIMPLE 2 . 0  focuses also on the use of Petri Nets for dy-namic domain analysis since it is a formalism with great po-tential for model checking and simulation. The tool alsointegrates PDDL representation to test models with generalplanners. In fact, by using itSIMPLE 2 . 0  it is possible to ex-portadomainmodeltoPDDLrepresentationcontainingfea-tures from version PDDL3 (Gerevini & Long 2006). XML(Extended Markup Language) is suitably used as an inter-mediate language that can translate the model from UML tootherrepresentationssuchas PDDL orPetriNets. Integratedin the initial stages, the environment also gives to end-usersan interface for plan analysis and management where de-signers can observe the behavior of the model during theexecution of plans (given by users or by planners). This isdone by using variable observation in XY and Gantt charts.itSIMPLE 2 . 0  is an open source project implemented inJava that provides a user-friendly GUI to model and analyzemany planning domains at the same time. This fact usuallycontributes to domain model reusability and maintenance.This paper is organized as follows: First, we describe theitSIMPLE 2 . 0  Environment and then we give a brief expla-nation about the integrated languages available. Next, wepresent each design process stage encompassed by the newitSIMPLE 2 . 0  environment such as requirements, modeling,model analysis, model testing and plan analysis. The paperends with a conclusions for this work. The itSIMPLE 2 . 0  Environment The itSIMPLE 2 . 0  environment aims to help designersto overcome the problems encountered during life cycle 336  of planning application projects, mainly at the require-ments specification, modeling and analysis phases. TheitSIMPLE 2 . 0  is designed to permit users to have a disci-plined design process to create knowledge intensive mod-els for several planning domains. The suggested processfor designing planning domains follows a cyclic sequenceof phases inherited from Software Engineering applicationscombined with modeling experiences acquired in the designof planning domain. Such process is shown in Figure 1.Figure 1: Planningdomaindesign processes in itSIMPLE 2 . 0 The environment is independent of any existing planner,i.e., the processes of modeling, verificationand dynamic do-main validation are independent of any particular planningtechniques. However, these techniques would be attached tothe process analysis as a name list in order to be chosen (au-tomatically or not) for a planning application.The environment was designed to incorporate a toolset(representation languages and theories) capable of dealingwith requirements and knowledge engineering as shown inFigure 1. Among many available specification languages,itSIMPLE 2 . 0  started by using the semi-formal languageUML (which is a well-known diagrammatic language com-monlyusedintheRequirementEngineering)fortherequire-ment process and modeling. It is one of the most used lan-guage that models a great variety of applications and webelieve that most engineers, working in several applicationareas, are somehow familiar with this representation. Thisfact makes UML a good choice for a modeling language inthe planning domains context, mainly because of its suit-ability to make a first model (tracking requirement specifi-cations). Sincedynamicaspectsarefundamentalinplanningapproach, formal languages and theories that provide goodrepresentation of state space evolution may become an al-ternative to a sound planning domain specification. Follow-ing this principle, the environment provides the use of PetriNets (Murata1989),whichis a formalrepresentation,whichcan help designers to perform dynamic domain validationsdeploying visual and animated information to the entire dy-namic system. By using Petri Nets it is possible to utilizeall available techniques based on graphs in order to formallyanalyze the dynamic features of a planning domain (suchas deadlocks, invariants, parallelism, concurrency and oth-ers). Also, since the AI Planning community has acceptedthe PDDL as the standard specification language for plannerinputs, itSIMPLE integrates the capabilities of dealing withsuch language mainly in the model testing stage.In order to hold all information available in several rep-resentation languages (UML, Petri Nets and PDDL) itSIM-PLE uses the well-known language XML (Bray  et al.  2004)which is commonly used in data transactions systems, webapplications and data sharing systems. The important pointon using XML is that some proposed integrated languageshave direct representation in XML such as PNML - whichstands for Petri Nets Markup Language (Billington  et al. 2003) - for Petri Net representation and XPDDL - eXten-sible Planning Domain Definition language (Gough 2002)- for PDDL. In itSIMPLE 2 . 0  all internal verifications andtranslations are performedin the structure and data availablein the XML model which came from UML diagrams. Infact, in order to create a Petri Net representation, a model isfirst presented in PNML form and then showed to the useras a Petri Net graph for simulation and analysis. In the caseof PDDL, all necessary data is extracted from XML spec-ification in order to first translate the model to a XPDDLrepresentation and then to PDDL. In fact, we believe XMLcanreallyhelpdesignerstoshareandmaintaintheirdomainsmodels and knowledge. Considering all these issues, the in-tegrated frameworkarchitecture of itSIMPLE 2 . 0  is shown inFigure 2.Figure 2: The architecture of the integrated languagesBy using itSIMPLE 2 . 0  translators, designers are able tochange from one language to another any time they want.Users can also deal with many projects and domains at thesame time, which allows the reusability of models. In thefollowing sections we present each main phase of the do-main design process illustrated in Figure 1 using the inte-grated environment provided by itSIMPLE 2 . 0 . Requirements Elicitation As Kotonyaand Sommerville (Kotonya& Somerville 1996)states, ”requirements reflect the needs of customers andusersofa system. Theyshouldincludea justificationforthissystem, whatthe system is intendedto accomplish,and whatdesign constraints are to be observed”. Truly, when dealingwith real life planning application the requirements elicita-tion is one of the most important stage in the whole designprocess. During elicitation, knowledge engineers need togather all the viewpoints from domain experts, users, stake-holders, sponsors and planning experts to investigate every 337  aspect of the same problem.Indeed, all the acquired requirements need to be docu-mented and discussed exhaustively for saving time and re-sources in furtherstages. One of the well-knownapproachesfor dealing and documenting requirements is the use casedriven approach. By using use case diagrams from UML, itis possible to expressrequirementsin a highlevel of abstrac-tion. Following this approach, itSIMPLE 2 . 0  allows design-ers to build use case diagrams trying to specify the planningdomain in a structured way. In these diagrams, each usecase holds information such as descriptions, pre and post-conditions, flow events, invariants, constraints, issues andothers relevant information that represents the domain re-quirements. Doing so, itSIMPLE 2 . 0  automaticallygeneratesan structured documentation which turns to be the princi-pal reference for the early design phase. Figure 3 shows anexample of the use case diagram for the classical planningdomain Logistic.Figure 3: Use case driven approachfor domain specification Domain Modeling with UML.P As highlighted before, in the itSIMPLE 2 . 0  environment,de-signers model their planning domains by using UML di-agrams. The UML was first defined by OMG UnifiedModeling Language Specification between 1996 and 1997(D’Souza & Wills 1999), and nowadays is one of the mostused languages to model a great variety of applications. Be-sides, UML has flexibility to attend manykinds of models inan object-oriented fashion since it is widely accepted as thestandard for object-oriented analysis and design. This semi-formal modeling language is largely used for the modelingand visualizationofsystem models. itSIMPLE 2 . 0  allows de-signers to use, in the planning domain context, all the col-lection of best engineering practices that are embedded inUML (OMG 2001).Since UML is a general purpose modeling language itturns to be necessary to propose an extended representationthat could deal with specification features that are intrinsi-cally related to planning domains. It was called UML.P(UML in a Planning Approach) and was firstly introducedin (Vaquero, Tonidandel, & Silva 2005). For instance, someof the UML diagrams can be directly applied for planningdomains such as class diagram, state chart diagram (alsoknown as state machine diagram) and object diagram. InitSIMPLE 2 . 0  the designer can model a planning domain byusing gradually these diagrams in order to model both do-mainandproblemfeaturesas we depictin thefollowingsec-tions. Figure 4 shows a screenshot of itSIMPLE 2 . 0  interfacefor modeling activities.Figure 4: itSIMPLE 2 . 0  interface for modeling with UML.P Domain Features Modeling By domain features modeling we mean the process of mod-eling not only the static structure of a planning domain -with the definition of classes, attributes, associations andstructural constraints - but also the dynamic features suchas states, actions an their pre and post conditions. In orderto model these features in UML.P, two main diagrams areneeded: the class diagram (for static features) and the statechart diagram (for dynamic characteristics).The class diagram is the commonly used in object-oriented modeling process. itSIMPLE 2 . 0  provides a cleanand very intuitive interface for modeling the main staticstructure of a planning domain, either a classical domain ora real life one, as depicted in (Vaquero  et al.  2006). Beyondall the classes, attributes and association definitions, the de-signercanalsospecifywhichclassesarecapableofperform-ing actions by declaring operators (each operator with itsset of parameters). Assigning classes with their operatorsmeans that users are deciding which classes perform eachaction. Classes capable of performing actions are what wecall the agent, while others are considered only resources inthemodel. Figure5illustrates an exampleofa class diagramfor the Logistic domain.Another diagram used for modeling the domain featuresis the state chart diagram. In UML.P the state chart diagramis responsible for representing dynamic features of the do-main model. Such dynamic representation is actually thebottleneck in the planning domain modeling process.In UML.P the designer build a state chart diagram foreach class that has a dynamic behavior in the model. Bydefiningonediagramfor each dynamicclass, users can viewtheir model as a set of regions in the state space. 338  Figure 5: Modeling static features with class diagramUser specifies in the state chart diagram all the pre andpost conditions of actions using the language OCL (ObjectConstraint Language) (OMG 2003) following the same ap-proach presented in (D’Souza & Wills 1999). OCL is apredefined formal language of the UML to represent con-straints, invariants and pre and post conditions of actions.In itSIMPLE 2 . 0 , states are defined by using OCL expres-sions representing the possible values of attributes. This ex-pressions are also used in transition arcs which representsan action in the chart. A complete action representation isthe result of the union of all pre and postcondition expres-sions declared in all state chart diagram where such actionappears. itSIMPLE 2 . 0  helps the user with an OCL editorto avoid mistakes while writing such expression. Figure 7and Figure 6 show two state chart diagrams representing thedynamic features of two classes of the Logistic domain.Figure 6: State chart diagram for the Package classWe considered a great advantage to construct state chartdiagrams for representing the dynamic features. However,since the designer can use more than one diagram to rep-resent the dynamic aspect, it becomes difficult to guaranteethat the domain model preserves the coherency among allFigure 7: State chart diagram for the Airplane classdiagrams.Unfortunately,the UML does not have a diagram that canrepresenttheglobalstates oftheplanningdomainthatwouldgive the designer an entire view of the domain dynamic as-pects. For this reason, itSIMPLE 2 . 0  provides a translationprocess from the state chart diagrams into Petri Nets (PN) inorder to allow designer to verify and validate the coherenceand consistency of his/her domain model. The main advan-tage on using PN is its formalism which providessimulationmechanisms and analysis techniques like invariants identi-fication, deadlocks and others illustrated in (Murata 1989).Some works show the successful application of PN for val-idation and verification of dynamic aspects of UML models(Watanabe  et al.  1997) (Cheung, Chow, & Cheung 1998)(Saldhana & Shatz 2000). The use of PN for analysis pur-pose is described further in the domain analysis section.In order to complete the domain features modeling pro-cess using itSIMPLE 2 . 0 , designer can represent the objectsthat compose the domain, i.e., the agents and the resourcesthat will be used to model the planning problems. For that,users can utilize object diagrams as a repository of objectsto be used in all problems. Problem Features Modeling A problem statement in a planning domain is usually char-acterized by a situation where only two states are known:the initial and goal state. The diagram used to describe thesestates is the object diagram or Snapshots. A good definitionof Snapshot is given as a depictionof a set of objects and thevalues of some or all of their attributes at a particular pointof time (D’Souza & Wills 1999).In other words, a snapshot is a picture of a specific staterepresenting an instantiation of the domain structure. Suchinstantiation represents features such as: which are the ob- jects available in the problem (including agents and re-sources); how they are arranged; what the values of eachobject attribute are; and how the objects are related witheach other. The itSIMPLE 2 . 0  tool assists designer to spec-ify consistentsnapshots by promotingautomaticverificationon all the constraints and features defined in the class dia-gram. For example, when two objects are associated, firstlyitSIMPLE 2 . 0  verify all possible associations between themin the class diagram and then verify the multiplicity rules. 339  This available automatic verification in snapshot modelingcan avoid inconsistent states. Figure 8 shows an example of a initial snapshot of a Logistic problem. This figure also il-lustrates the importance of using icons when modeling bothdomain and problem. Usually, icons and images provide anintuitive view of all problem components.Figure 8: The initial state of a Logistic problemAnother importantfeature available in itSIMPLE 2 . 0  is thedefinition of intermediate states (snapshots) in a problem.These intermediate states can represent situations that mustbe avoided or some kind of state trajectory constraints dur-ing the planning process. This capability follows the con-cepts introduced in the definition of PDDL3 (Gerevini &Long 2006). Thus, the use of itSIMPLE 2 . 0  make it possibleto model situations that must happen always, sometimes, at-most-onceorneverduringtheevaluationof a planningprob-lem. This particular tool capability can be a powerful mod-eling characteristic for many real planning problems. Allthese constrained situations are considered snapshots in thetool environment. Domain Model Analysis with Petri Nets Domain analysis process is becoming one of the main stud-ied topicin theKE forAI Planning,and,indeed,this processhas a great impact on the quality of the domain model be-ing built. As mentioned before, itSIMPLE 2 . 0  also providesmechanismsforhelpingdesignerstoanalyzeandverifytheirmodel focusing on dynamic aspects. It is done by represent-ing state chart diagrams into Petri Nets. As highlighted inthis paper and in (Vaquero  et al.  2006), each state chart dia-gram shows the dynamic characteristics of objects (of a spe-cific class) beingaffectedby actions that can appearin manystate chart diagrams. Therefore,there are usually manystatechart diagrams in a single domain model.In this framework,each state chart diagramcan be viewedas a module of the entire domain. Considering this modu-larity introduced by the state chart diagrams in UML, it ispossible to represent these modules through the concept of  modular PNML  (Kindler & Weber 2001). This concept isused by itSIMPLE 2 . 0  to represent Petri Nets. It is importantto highlight that OCL expressions are not considered in thePNML representation in itSIMPLE 2 . 0 .The dynamic domain analysis process using the statecharts and Petri Nets is divided in two main analyses:  Mod-ular Analysis  and  Interface Analysis . Modular Analysis The  Modular Analysis  tries to verify each module one-by-one, taking into account the dependencies with others mod-ules (representedby what we call Gates). The modularanal-ysis throughPetri Nets allows the designer to detect featureslike parallelism, concurrencies and undesirable deadlocksthroughout simulation processes. Figure 9 and Figure 10show an example of Petri Nets derived from the state chartsillustrated in Figure 6 and Figure 7, respectively.Figure 9: Modular Analysis of the class PackageFigure 10: Modular Analysis of the class AirplaneIn order to analyze modules, designers must verify theflow of the marks in each one, checking the existence of undesirable deadlocks and also validating the concurrenciesand parallelism by manipulating Gates (representing exter-nal dependencies from other modules). This manipulation(turning Gates on or off) allows the designer to realize whathappens, for example, with a package when an airplane isnot available. This modular visualization and manipulation 340
Search
Tags
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x