{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T15:16:44Z","timestamp":1777907804063,"version":"3.51.4"},"reference-count":50,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T00:00:00Z","timestamp":1560816000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["1S40217N"],"award-info":[{"award-number":["1S40217N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Goal recognition is an important component of many context-aware and smart environment services; however, a person\u2019s goal often cannot be determined until their plan nears completion. Therefore, by modifying the state of the environment, our work aims to reduce the number of observations required to recognise a human\u2019s goal. These modifications result in either: Actions in the available plans being replaced with more distinctive actions; or removing the possibility of performing some actions, so humans are forced to take an alternative (more distinctive) plan. In our solution, a symbolic representation of actions and the world state is transformed into an Action Graph, which is then traversed to discover the non-distinctive plan prefixes. These prefixes are processed to determine which actions should be replaced or removed. For action replacement, we developed an exhaustive approach and an approach that shrinks the plans then reduces the non-distinctive plan prefixes, namely Shrink\u2013Reduce. Exhaustive is guaranteed to find the minimal distinctiveness but is more computationally expensive than Shrink\u2013Reduce. These approaches are compared using a test domain with varying amounts of goals, variables and values, and a realistic kitchen domain. Our action removal method is shown to increase the distinctiveness of various grid-based navigation problems, with a width\/height ranging from 4 to 16 and between 2 and 14 randomly selected goals, by an average of 3.27 actions in an average time of 4.69 s, whereas a state-of-the-art approach often breaches a 10 min time limit.<\/jats:p>","DOI":"10.3390\/s19122741","type":"journal-article","created":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T02:42:46Z","timestamp":1560912166000},"page":"2741","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Action Graphs for Performing Goal Recognition Design on Human-Inhabited Environments"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3195-2579","authenticated-orcid":false,"given":"Helen","family":"Harman","sequence":"first","affiliation":[{"name":"Department of Information Technology\u2014IDLab, Ghent University\u2014imec, Technologiepark 126, B-9052 Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9569-9373","authenticated-orcid":false,"given":"Pieter","family":"Simoens","sequence":"additional","affiliation":[{"name":"Department of Information Technology\u2014IDLab, Ghent University\u2014imec, Technologiepark 126, B-9052 Ghent, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,6,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1613\/jair.1.11343","article-title":"Cost-Based Goal Recognition in Navigational Domains","volume":"64","author":"Masters","year":"2019","journal-title":"J. Artif. Intell. Res."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Pereira, R.F., Oren, N., and Meneguzzi, F. (2019). Landmark-Based Approaches for Goal Recognition as Planning. arXiv.","DOI":"10.1016\/j.artint.2019.103217"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1007\/s11042-018-6163-6","article-title":"A Comprehensive Solution for Detecting Events in Complex Surveillance Videos","volume":"78","author":"Zhu","year":"2019","journal-title":"Multimed. Tools Appl."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yordanova, K., L\u00fcdtke, S., Whitehouse, S., Kr\u00fcger, F., Paiement, A., Mirmehdi, M., Craddock, I., and Kirste, T. (2019). Analysing Cooking Behaviour in Home Settings: Towards Health Monitoring. Sensors, 19.","DOI":"10.3390\/s19030646"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kortuem, G., Finney, J., Lea, R., and Sundramoorthy, V. (2007). Recognising Activities of Daily Life Using Hierarchical Plans. Smart Sensing and Context, Springer.","DOI":"10.1007\/978-3-540-75696-5"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Freedman, R.G., and Zilberstein, S. (2017, January 4\u20139). Integration of Planning with Recognition for Responsive Interaction Using Classical Planners. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.11188"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Ram\u00edrez, M., and Geffner, H. (2010, January 11\u201315). Probabilistic Plan Recognition Using Off-the-shelf Classical Planners. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, Atlanta, GA, USA.","DOI":"10.1609\/aaai.v24i1.7745"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Pereira, R.F., Oren, N., and Meneguzzi, F. (2017, January 4\u20139). Landmark-based Heuristics for Goal Recognition. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.11021"},{"key":"ref_9","unstructured":"E-Martin, Y., R-Moreno, M.D., and Smith, D.E. (2015, January 25\u201331). A Fast Goal Recognition Technique Based on Interaction Estimates. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Keren, S., Gal, A., and Karpas, E. (2014, January 21\u201326). Goal Recognition Design. Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling, Portsmouth, NH, USA.","DOI":"10.1609\/icaps.v24i1.13617"},{"key":"ref_11","unstructured":"Harman, H., and Simoens, P. (February, January 27). Solving Navigation-Based Goal Recognition Design Problems with Action Graphs. Proceedings of the AAAI Workshops on Plan, Activity, and Intent Recognition (PAIR-19), Honolulu, HI, USA."},{"key":"ref_12","unstructured":"Wayllace, C., Hou, P., Yeoh, W., and Son, T.C. (2016, January 9\u201315). Goal Recognition Design with Stochastic Agent Action Outcomes. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, New York, NY, USA."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Son, T.C., Sabuncu, O., Schulz-Hanke, C., Schaub, T., and Yeoh, W. (2016, January 12\u201317). Solving Goal Recognition Design Using ASP. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA.","DOI":"10.1609\/aaai.v30i1.10407"},{"key":"ref_14","unstructured":"Wayllace, C., Keren, S., Yeoh, W., Gal, A., and Karpas, E. (2018, January 26). Accounting for Partial Observability in Stochastic Goal Recognition Design: Messing with the Marauder\u2019s Map. Proceedings of the 10th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP), Delft, The Netherlands."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Keren, S., Gal, A., and Karpas, E. (2018, January 24\u201329). Strong Stubborn Sets for Efficient Goal Recognition Design. Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling, Delft, The Netherlands.","DOI":"10.1609\/icaps.v28i1.13876"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Wu, J., Osuntogun, A., Choudhury, T., Philipose, M., and Rehg, J.M. (2007, January 14\u201321). A Scalable Approach to Activity Recognition Based on Object Use. Proceedings of the Eleventh IEEE International Conference on Computer Vision, Rio de Janeiro, Brazil.","DOI":"10.1109\/ICCV.2007.4408865"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Keren, S., Gal, A., and Karpas, E. (2015, January 25\u201330). Goal Recognition Design for Non-optimal Agents. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, TX, USA.","DOI":"10.1609\/aaai.v30i1.10403"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Keren, S., Gal, A., and Karpas, E. (2016, January 12\u201317). Goal Recognition Design with Non-observable Actions. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, Phoenix, AZ, USA.","DOI":"10.1609\/aaai.v30i1.10403"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Wayllace, C., Hou, P., and Yeoh, W. (2017, January 19\u201325). New Metrics and Algorithms for Stochastic Goal Recognition Design Problems. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, Melbourne, Australia.","DOI":"10.24963\/ijcai.2017\/622"},{"key":"ref_20","unstructured":"Harman, H., Chintamani, K., and Simoens, P. (2018, January 25\u201326). Action Trees for Scalable Goal Recognition in Robotic Applications. Proceedings of the sixth Workshop on Planning and Robotics (PlanRob), Delft, The Netherlands."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"14:1","DOI":"10.1145\/3234464","article-title":"Goal and Plan Recognition Design for Plan Libraries","volume":"10","author":"Mirsky","year":"2019","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1613\/jair.1705","article-title":"The Fast Downward Planning System","volume":"26","author":"Helmert","year":"2006","journal-title":"J. Artif. Intell. Res."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ghallab, M., Nau, D., and Traverso, P. (2004). Part I\u2014Classical Planning. Automated Planning, Morgan Kaufmann.","DOI":"10.1016\/B978-155860856-6\/50005-3"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Geffner, H., and Bonet, B. (2013). A Concise Introduction to Models and Methods for Automated Planning: Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers. [1st ed.].","DOI":"10.1007\/978-3-031-01564-9"},{"key":"ref_25","unstructured":"Ram\u00edrez, M., and Geffner, H. (2009, January 14\u201317). Plan Recognition As Planning. Proceedings of the Twenty-First International Joint Conference on Artifical Intelligence, Pasadena, CA, USA."},{"key":"ref_26","unstructured":"Geib, C.W., and Goldman, R.P. (2001, January 12\u201314). Plan Recognition in Intrusion Detection Systems. Proceedings of the DARPA Information Survivability Conference and Exposition II, Anaheim, CA, USA."},{"key":"ref_27","unstructured":"Keren, S., Mirsky, R., and Geib, C. (2019, March 25). Plan Activity and Intent Recognition Tutorial. Available online: http:\/\/www.planrec.org\/Tutorial\/Resources_files\/pair-tutorial.pdf."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1109\/THMS.2016.2641388","article-title":"From Activity Recognition to Intention Recognition for Assisted Living Within Smart Homes","volume":"47","author":"Rafferty","year":"2017","journal-title":"IEEE T. Hum.-Mach. Syst."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s12652-009-0007-1","article-title":"Recognizing Independent and Joint Activities Among Multiple Residents in Smart Environments","volume":"1","author":"Singla","year":"2010","journal-title":"J. Ambient Intell. Humaniz. Comput."},{"key":"ref_30","unstructured":"Bisson, F., Larochelle, H., and Kabanza, F. (2015, January 25\u201330). Using a Recursive Neural Network to Learn an Agent\u2019s Decision Model for Plan Recognition. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, Austin, TX, USA."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Amado, L., Pereira, R.F., Aires, J., Magnaguagno, M., Granada, R., and Meneguzzi, F. (2018, January 8\u201313). Goal Recognition in Latent Space. Proceedings of the International Joint Conference on Neural Networks, Rio de Janeiro, Brazil.","DOI":"10.1109\/IJCNN.2018.8489653"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Roy, P.C., Giroux, S., Bouchard, B., Bouzouane, A., Phua, C., Tolstikov, A., and Biswas, J. (2011). A Possibilistic Approach for Activity Recognition in Smart Homes for Cognitive Assistance to Alzheimer\u2019s Patients. Activity Recognition in Pervasive Intelligent Environments, Atlantis Press.","DOI":"10.2991\/978-94-91216-05-3_2"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Yordanova, K., Kr\u00fcger, F., and Kirste, T. (2012, January 19\u201323). Context Aware Approach for Activity Recognition Based on Precondition-Effect Rules. Proceedings of the IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops), Lugano, Switzerland.","DOI":"10.1109\/PerComW.2012.6197586"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1016\/j.artint.2009.01.003","article-title":"A Probabilistic Plan Recognition Algorithm Based on Plan Tree Grammars","volume":"173","author":"Geib","year":"2009","journal-title":"Artif. Intell."},{"key":"ref_35","unstructured":"Kautz, H.A., and Allen, J.F. (1986, January 11\u201315). Generalized Plan Recognition. Proceedings of the Fifth AAAI National Conference on Artificial Intelligence, Philadelphia, PA, USA."},{"key":"ref_36","unstructured":"Kautz, H.A. (1987). A Formal Theory of Plan Recognition. [Ph.D. Thesis, Department of Computer Science, University of Rochester]."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"45:1","DOI":"10.1145\/2996200","article-title":"CRADLE: An Online Plan Recognition Algorithm for Exploratory Domains","volume":"8","author":"Mirsky","year":"2017","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"ref_38","unstructured":"Avrahami-Zilberbrand, D., and Kaminka, G.A. (August, January 30). Fast and Complete Symbolic Plan Recognition. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, UK."},{"key":"ref_39","unstructured":"Vilain, M. (August, January 29). Getting Serious About Parsing Plans: A Grammatical Analysis of Plan Recognition. Proceedings of the Eighth National Conference on Artificial Intelligence, Boston, MA, USA."},{"key":"ref_40","unstructured":"Kabanza, F., Filion, J., Benaskeur, A.R., and Irandoust, H. (2013, January 3\u20139). Controlling the Hypothesis Space in Probabilistic Plan Recognition. Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, Beijing, China."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Holtzen, S., Zhao, Y., Gao, T., Tenenbaum, J.B., and Zhu, S.C. (2016, January 9\u201314). Inferring Human Intent From Video by Sampling Hierarchical Plans. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Daejeon, Korea.","DOI":"10.1109\/IROS.2016.7759242"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s101070100263","article-title":"Benchmarking Optimization Software with Performance Profiles","volume":"91","author":"Dolan","year":"2002","journal-title":"Math. Program."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/j.artint.2015.01.004","article-title":"The Deterministic Part of the Seventh International Planning Competition","volume":"223","author":"Celorrio","year":"2015","journal-title":"Artif. Intell."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Keren, S., Pineda, L., Gal, A., Karpas, E., and Zilberstein, S. (2017, January 4\u20139). Redesigning Stochastic Environments for Maximized Utility. Proceedings of the AAAI Workshops on Plan, Activity, and Intent Recognition (PAIR-17), San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.11095"},{"key":"ref_45","unstructured":"Chakraborti, T., Kulkarni, A., Sreedharan, S., Smith, D.E., and Kambhampati, S. (2018). Explicability? Legibility? Predictability? Transparency? Privacy? Security? the Emerging Landscape of Interpretable Agent Behavior. arXiv."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Dragan, A.D., Lee, K.C., and Srinivasa, S.S. (2013, January 3\u20136). Legibility and Predictability of Robot Motion. Proceedings of the 8th ACM\/IEEE International Conference on Human-robot Interaction, Tokyo, Japan.","DOI":"10.1109\/HRI.2013.6483603"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Pozanco, A., E-Mart\u00edn, Y., Fern\u00e1ndez, S., and Borrajo, D. (2018, January 13\u201319). Counterplanning Using Goal Recognition and Landmarks. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, Stockholm, Sweden.","DOI":"10.24963\/ijcai.2018\/668"},{"key":"ref_48","unstructured":"Horvitz, E., Breese, J., Heckerman, D., Hovel, D., and Rommelse, K. (1998, January 24\u201326). The Lumi\u00e8Re Project: Bayesian User Modeling for Inferring the Goals and Needs of Software Users. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, Madison, WI, USA."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.830","article-title":"Goal Recognition Through Goal Graph Analysis","volume":"15","author":"Hong","year":"2001","journal-title":"J. Artif. Intell. Res."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Ashley, K.D., and Bridge, D.G. (2003, January 23\u201326). Case-Based Plan Recognition in Computer Games. Proceedings of the International Conference on Case-Based Reasoning Research and Development, Trondheim, Norway.","DOI":"10.1007\/3-540-45006-8"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/12\/2741\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:59:23Z","timestamp":1760187563000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/12\/2741"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,18]]},"references-count":50,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["s19122741"],"URL":"https:\/\/doi.org\/10.3390\/s19122741","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,18]]}}}