nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

5. User-Centered Planning

verfasst von : Pascal Bercher, Daniel Höller, Gregor Behnke, Susanne Biundo

Erschienen in: Companion Technology

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

User-centered planning capabilities are core elements of Companion-Technology. They are used to implement the functional behavior of technical systems in a way that makes those systems Companion-able—able to serve users individually, to respect their actual requirements and needs, and to flexibly adapt to changes in their situation and environment. This chapter presents various techniques we have developed and integrated to realize user-centered planning. They are based on a hybrid planning approach that combines key principles also humans rely on when making plans: stepwise refining complex tasks into executable courses of action and considering causal relationships between actions. Since the generated plans impose only a partial order on actions, they allow for a highly flexible execution order as well. Planning for Companion-Systems may serve different purposes, depending on the application for which the system is created. Sometimes, plans are just like control programs and executed automatically in order to elicit the desired system behavior; but sometimes they are made for humans. In the latter case, plans have to be adequately presented and the definite execution order of actions has to coincide with the user’s requirements and expectations. Furthermore, the system should be able to smoothly cope with execution errors. To this end, the plan generation capabilities are complemented by mechanisms for plan presentation, execution monitoring, and plan repair.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Modeling Aspects in Human-Computer Interaction: Adaptivity, User Characteristics and Evaluation

Nächstes Kapitel Addressing Uncertainty in Hierarchical User-Centered Planning

More technically, it uses not just s _init as effect, but—because s _init consists only of positive literals due to the closed world assumption—also all negative ground literals that unify with any negative precondition that are not contradicting s _init. Otherwise, there might be a negative task precondition literal that could not be protected by a causal link rooting in the initial state.

Delete-relaxation means ignoring negative literals in the effects and, optionally, in the preconditions of any action.

Assuming there are no not-yet executed actions that are inserted due to the underlying action hierarchy; cf. Solution Criterion 1a.

Alford, R., Shivashankar, V., Kuter, U., Nau, D.S.: HTN problem spaces: structure, algorithms, termination. In: Proceedings of the 5th Annual Symposium on Combinatorial Search (SoCS), pp. 2–9. AAAI Press, Palo Alto (2012)

Alford, R., Shivashankar, V., Kuter, U., Nau, D.: On the feasibility of planning graph style heuristics for HTN planning. In: Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS), pp. 2–10. AAAI Press, Palo Alto (2014)

Alford, R., Bercher, P., Aha, D.: Tight bounds for HTN planning. In: Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS), pp. 7–15. AAAI Press, Palo Alto (2015)

Alford, R., Bercher, P., Aha, D.: Tight bounds for HTN planning with task insertion. In: Proceedings of the 25th International Joint Conference on AI (IJCAI), pp. 1502–1508. AAAI Press, Palo Alto (2015)

Behnke, G., Höller, D., Biundo, S.: On the complexity of HTN plan verification and its implications for plan recognition. In: Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS), pp. 25–33. AAAI Press, Palo Alto (2015)

Behnke, G., Ponomaryov, D., Schiller, M., Bercher, P., Nothdurft, F., Glimm, B., Biundo, S.: Coherence across components in cognitive systems – one ontology to rule them all. In: Proceedings of the 25th International Joint Conference on AI (IJCAI), pp. 1442–1449. AAAI Press, Palo Alto (2015)

Behnke, G., Höller, D., Bercher, P., Biundo, S.: Change the plan - how hard can that be? In: Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS), pp. 38–46. AAAI Press, Palo Alto (2016)

Bercher, P., Biundo, S.: A heuristic for hybrid planning with preferences. In: Proceedings of the 25th International Florida AI Research Society Conference (FLAIRS), pp. 120–123. AAAI Press, Palo Alto (2012)

Bercher, P., Höller, D.: Interview with David E. Smith. Künstliche Intelligenz 30, 101–105 (2016). doi:10.1007/s13218-015-0403-yCrossRef

10.

Bercher, P., Geier, T., Biundo, S.: Using state-based planning heuristics for partial-order causal-link planning. In: Advances in AI, Proceedings of the 36th German Conference on AI (KI), pp. 1–12. Springer, Berlin (2013)

11.

Bercher, P., Geier, T., Richter, F., Biundo, S.: On delete relaxation in partial-order causal-link planning. In: Proceedings of the 25th International Conference on Tools with AI (ICTAI), pp. 674–681. IEEE Computer Society, New York (2013)

12.

Bercher, P., Biundo, S., Geier, T., Hörnle, T., Nothdurft, F., Richter, F., Schattenberg, B.: Plan, repair, execute, explain - how planning helps to assemble your home theater. In: Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS), pp. 386–394. AAAI Press, Palo Alto (2014)

13.

Bercher, P., Keen, S., Biundo, S.: Hybrid planning heuristics based on task decomposition graphs. In: Proceedings of the 7th Annual Symposium on Combinatorial Search (SoCS), pp. 35–43. AAAI Press, Palo Alto (2014)

14.

Bercher, P., Richter, F., Hörnle, T., Geier, T., Höller, D., Behnke, G., Nothdurft, F., Honold, F., Minker, W., Weber, M., Biundo, S.: A planning-based assistance system for setting up a home theater. In: Proceedings of the 29th National Conference on Artificial Intelligence (AAAI), pp. 4264–4265. AAAI Press, Palo Alto (2015)

15.

Bercher, P., Höller, D., Behnke, G., Biundo, S.: More than a name? On implications of preconditions and effects of compound HTN planning tasks. In: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), pp. 225–233. IOS Press (2016)

16.

Bertrand, G., Nothdurft, F., Honold, F., Schüssel, F.: CALIGRAPHI-creation of adaptive dialogues using a graphical interface. In: 35th Annual Computer Software and Applications Conference (COMPSAC), pp. 393–400. IEEE, New York (2011)

17.

Bidot, J., Schattenberg, B., Biundo, S.: Plan repair in hybrid planning. In: Advances in AI, Proceedings of the 31st German Conference on AI (KI), pp. 169–176. Springer, Berlin (2008)

18.

Biundo, S., Schattenberg, B.: From abstract crisis to concrete relief (a preliminary report on combining state abstraction and HTN planning). In: Proceedings of the 6th European Conference on Planning (ECP), pp. 157–168. AAAI Press, Palo Alto (2001)

19.

Biundo, S., Wendemuth, A.: Companion-technology for cognitive technical systems. Künstliche Intelligenz 30, 71–75 (2016). doi:10.1007/s13218-015-0414-8CrossRef

20.

Biundo, S., Bercher, P., Geier, T., Müller, F., Schattenberg, B.: Advanced user assistance based on AI planning. Cogn. Syst. Res. 12(3–4), 219–236 (2011); Special Issue on Complex Cognition

21.

Biundo, S., Höller, D., Schattenberg, B., Bercher, P.: Companion-technology: an overview. Künstliche Intelligenz 30, 11–20 (2016). doi:10.1007/s13218-015-0419-3CrossRef

22.

Bylander, T.: The computational complexity of propositional STRIPS planning. Artif. Intell. 94(1–2), 165–204 (1994)MathSciNetCrossRefMATH

23.

Edelkamp, S.: On the compilation of plan constraints and preferences. In: Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS), pp. 374–377. AAAI Press, Palo Alto (2006)

24.

Elkawkagy, M., Schattenberg, B., Biundo, S.: Landmarks in hierarchical planning. In: Proceedings of the 20th European Conference on AI (ECAI), pp. 229–234. IOS Press, Amsterdam (2010)

25.

Elkawkagy, M., Bercher, P., Schattenberg, B., Biundo, S.: Improving hierarchical planning performance by the use of landmarks. In: Proceedings of the 26th National Conference on Artificial Intelligence (AAAI), pp. 1763–1769. AAAI Press, Palo Alto (2012)

26.

Erol, K., Hendler, J.A., Nau, D.S.: UMCP: a sound and complete procedure for hierarchical task-network planning. In: Proceedings of the 2nd International Conference on AI Planning Systems (AIPS), pp. 249–254. AAAI Press, Palo Alto (1994)

27.

Erol, K., Hendler, J.A., Nau, D.S.: Complexity results for HTN planning. Ann. Math. Artif. Intell. 18(1), 69–93 (1996)MathSciNetCrossRefMATH

28.

Fiedler, A.: P.rex: an interactive proof explainer. In: Proceedings of the 1st International Joint Conference on Automated Reasoning (IJCAR), pp. 416–420. Springer, Berlin (2001)

29.

Geier, T., Bercher, P.: On the decidability of HTN planning with task insertion. In: Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 1955–1961. AAAI Press, Palo Alto (2011)

30.

Holland-Minkley, A.M., Barzilay, R., Constable, R.L.: Verbalization of high-level formal proofs. In: Proceedings of the 16th National Conference on AI and the 11th Innovative Applications of AI Conference (AAAI/IAAI), pp. 277–284. AAAI Press, Palo Alto (1999)

31.

Höller, D., Behnke, G., Bercher, P., Biundo, S.: Language classification of hierarchical planning problems. In: Proceedings of the 21st European Conference on AI (ECAI), pp. 447–452. IOS Press, Amsterdam (2014)

32.

Höller, D., Bercher, P., Richter, F., Schiller, M., Geier, T., Biundo, S.: Finding user-friendly linearizations of partially ordered plans. In: 28th PuK Workshop “Planen, Scheduling und Konfigurieren, Entwerfen” (PuK) (2014)

33.

Höller, D., Behnke, G., Bercher, P., Biundo, S.: Assessing the expressivity of planning formalisms through the comparison to formal languages. In: Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS), pp. 158–165. AAAI Press, Palo Alto (2016)

34.

Honold, F., Schüssel, F., Weber, M.: Adaptive probabilistic fission for multimodal systems. In: Proceedings of the 24th Australian Computer-Human Interaction Conference (OzCHI), pp. 222–231. ACM, New York (2012)

35.

Honold, F., Bercher, P., Richter, F., Nothdurft, F., Geier, T., Barth, R., Hörnle, T., Schüssel, F., Reuter, S., Rau, M., Bertrand, G., Seegebarth, B., Kurzok, P., Schattenberg, B., Minker, W., Weber, M., Biundo, S.: Companion-technology: towards user- and situation-adaptive functionality of technical systems. In: International Conference on Intelligent Environments (IE), pp. 378–381. IEEE, New York (2014). http://companion.informatik.uni-ulm.de/ie2014/companion-system.mp4

36.

Kambhampati, S., Mali, A., Srivastava, B.: Hybrid planning for partially hierarchical domains. In: Proceedings of the 15th National Conference on AI (AAAI), pp. 882–888. AAAI Press, Palo Alto (1998)

37.

Keyder, E., Geffner, H.: Soft goals can be compiled away. J. Artif. Intell. Res. 36, 547–556 (2009)MATH

38.

Kowalski, R.A.: Predicate logic as programming language. In: IFIP Congress, pp. 569–574 (1974)

39.

Lin, N., Kuter, U., Sirin, E.: Web service composition with user preferences. In: Proceedings of the 5th European Semantic Web Conference (ESWC), pp. 629–643. Springer, Heidelberg (2008)

40.

Lyons, J.B., Koltai, K.S., Ho, N.T., Johnson, W.B., Smith, D.E., Shively, R.J.: Engineering trust in complex automated systems. Ergon. Des. 24(1), 13–17 (2016). https://doi.org/10.1177/1064804615611272

41.

McAllester, D., Rosenblitt, D.: Systematic nonlinear planning. In: Proceedings of the 9th National Conference on AI (AAAI), pp. 634–639. AAAI Press, Palo Alto (1991)

42.

Muir, B.M.: Trust in automation: part I. theoretical issues in the study of trust and human intervention in automated systems. Ergonomics 37(11), 1905–1922 (1994)

43.

Nau, D.S., Au, T.C., Ilghami, O., Kuter, U., Murdock, J.W., Wu, D., Yaman, F.: SHOP2: an HTN planning system. J. Artif. Intell. Res. 20, 379–404 (2003)MATH

44.

Nau, D.S., Au, T.C., Ilghami, O., Kuter, U., Wu, D., Yaman, F., Muñoz-Avila, H., Murdock, J.W.: Applications of SHOP and SHOP2. IEEE Intell. Syst. 20, 34–41 (2005)CrossRef

45.

Nebel, B., Koehler, J.: Plan reuse versus plan generation: a theoretical and empirical analysis. Artif. Intell. 76(1-2), 427–454 (1995)CrossRef

46.

Nguyen, X., Kambhampati, S.: Reviving partial order planning. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI), pp. 459–466. Morgan Kaufmann, San Francisco (2001)

47.

Nothdurft, F., Bertrand, G., Heinroth, T., Minker, W.: GEEDI - guards for emotional and explanatory dialogues. In: 6th International Conference on Intelligent Environments (IE), pp. 90–95. IEEE, New York (2010)

48.

Nothdurft, F., Honold, F., Zablotskaya, K., Diab, A., Minker, W.: Application of verbal intelligence in dialog systems for multimodal interaction. In: 10th International Conference on Intelligent Environments (IE), pp. 361–364. IEEE, New York (2014)

49.

Parasuraman, R., Riley, V.: Humans and automation: use, misuse, disuse, abuse. Hum. Factors: J. Hum. Factors Ergon. Soc. 39(2), 230–253 (1997)CrossRef

50.

Penberthy, J.S., Weld, D.S.: UCPOP: a sound, complete, partial order planner for ADL. In: Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR), pp. 103–114. Morgan Kaufmann, San Francisco (1992)

51.

Porteous, J., Sebastia, L., Hoffmann, J.: On the extraction, ordering, and usage of landmarks in planning. In: Proceedings of the 6th European Conference on Planning (ECP), pp. 37–48. AAAI Press, Palo Alto (2001)

52.

Russell, S., Norvig, P.: Artificial Intelligence – A Modern Approach, 1 edn. Prentice-Hall, Englewood Cliffs (1994)MATH

53.

Seegebarth, B., Müller, F., Schattenberg, B., Biundo, S.: Making hybrid plans more clear to human users – a formal approach for generating sound explanations. In: Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS), pp. 225–233. AAAI Press, Palo Alto (2012)

54.

Simons, M.: Proof presentation for Isabelle. In: Proceedings of the 10th International Conference on Theorem Proving in Higher Order Logics (TPHOLs), pp. 259–274. Springer, Berlin (1997)

55.

Sohrabi, S., Baier, J.A., McIlraith, S.A.: HTN planning with preferences. In: Proceedings of the 21st International Joint Conference on AI (IJCAI), pp. 1790–1797. AAAI Press, Palo Alto (2009)

56.

Trac, S., Puzis, Y., Sutcliffe, G.: An interactive derivation viewer. Electron. Notes Theor. Comput. Sci. 174(2), 109–123 (2007)CrossRefMATH

57.

Younes, H.L.S., Simmons, R.G.: VHPOP: versatile heuristic partial order planner. J. Artif. Intell. Res. 20, 405–430 (2003)MATH

58.

Zhu, L., Givan, R.: Heuristic planning via roadmap deduction. In: IPC-4 Booklet, pp. 64–66 (2004)

Titel: User-Centered Planning
verfasst von: Pascal Bercher
Daniel Höller
Gregor Behnke
Susanne Biundo
Verlag: Springer International Publishing
Buch: Companion Technology
Print ISBN: 978-3-319-43664-7

Electronic ISBN: 978-3-319-43665-4

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-43665-4_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"