Cargando…
Comparing Plan Recognition Algorithms Through Standard Plan Libraries
Plan recognition deals with reasoning about the goals and execution process of an actor, given observations of its actions. It is one of the fundamental problems of AI, applicable to many domains, from user interfaces to cyber-security. Despite the prevalence of these approaches, they lack a standar...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Frontiers Media S.A.
2022
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8778577/ https://www.ncbi.nlm.nih.gov/pubmed/35072058 http://dx.doi.org/10.3389/frai.2021.732177 |
_version_ | 1784637359741992960 |
---|---|
author | Mirsky, Reuth Galun, Ran Gal, Kobi Kaminka, Gal |
author_facet | Mirsky, Reuth Galun, Ran Gal, Kobi Kaminka, Gal |
author_sort | Mirsky, Reuth |
collection | PubMed |
description | Plan recognition deals with reasoning about the goals and execution process of an actor, given observations of its actions. It is one of the fundamental problems of AI, applicable to many domains, from user interfaces to cyber-security. Despite the prevalence of these approaches, they lack a standard representation, and have not been compared using a common testbed. This paper provides a first step towards bridging this gap by providing a standard plan library representation that can be used by hierarchical, discrete-space plan recognition and evaluation criteria to consider when comparing plan recognition algorithms. This representation is comprehensive enough to describe a variety of known plan recognition problems and can be easily used by existing algorithms in this class. We use this common representation to thoroughly compare two known approaches, represented by two algorithms, SBR and Probabilistic Hostile Agent Task Tracker (PHATT). We provide meaningful insights about the differences and abilities of these algorithms, and evaluate these insights both theoretically and empirically. We show a tradeoff between expressiveness and efficiency: SBR is usually superior to PHATT in terms of computation time and space, but at the expense of functionality and representational compactness. We also show how different properties of the plan library affect the complexity of the recognition process, regardless of the concrete algorithm used. Lastly, we show how these insights can be used to form a new algorithm that outperforms existing approaches both in terms of expressiveness and efficiency. |
format | Online Article Text |
id | pubmed-8778577 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2022 |
publisher | Frontiers Media S.A. |
record_format | MEDLINE/PubMed |
spelling | pubmed-87785772022-01-22 Comparing Plan Recognition Algorithms Through Standard Plan Libraries Mirsky, Reuth Galun, Ran Gal, Kobi Kaminka, Gal Front Artif Intell Artificial Intelligence Plan recognition deals with reasoning about the goals and execution process of an actor, given observations of its actions. It is one of the fundamental problems of AI, applicable to many domains, from user interfaces to cyber-security. Despite the prevalence of these approaches, they lack a standard representation, and have not been compared using a common testbed. This paper provides a first step towards bridging this gap by providing a standard plan library representation that can be used by hierarchical, discrete-space plan recognition and evaluation criteria to consider when comparing plan recognition algorithms. This representation is comprehensive enough to describe a variety of known plan recognition problems and can be easily used by existing algorithms in this class. We use this common representation to thoroughly compare two known approaches, represented by two algorithms, SBR and Probabilistic Hostile Agent Task Tracker (PHATT). We provide meaningful insights about the differences and abilities of these algorithms, and evaluate these insights both theoretically and empirically. We show a tradeoff between expressiveness and efficiency: SBR is usually superior to PHATT in terms of computation time and space, but at the expense of functionality and representational compactness. We also show how different properties of the plan library affect the complexity of the recognition process, regardless of the concrete algorithm used. Lastly, we show how these insights can be used to form a new algorithm that outperforms existing approaches both in terms of expressiveness and efficiency. Frontiers Media S.A. 2022-01-06 /pmc/articles/PMC8778577/ /pubmed/35072058 http://dx.doi.org/10.3389/frai.2021.732177 Text en Copyright © 2022 Mirsky, Galun, Gal and Kaminka. https://creativecommons.org/licenses/by/4.0/This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) and the copyright owner(s) are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms. |
spellingShingle | Artificial Intelligence Mirsky, Reuth Galun, Ran Gal, Kobi Kaminka, Gal Comparing Plan Recognition Algorithms Through Standard Plan Libraries |
title | Comparing Plan Recognition Algorithms Through Standard Plan Libraries |
title_full | Comparing Plan Recognition Algorithms Through Standard Plan Libraries |
title_fullStr | Comparing Plan Recognition Algorithms Through Standard Plan Libraries |
title_full_unstemmed | Comparing Plan Recognition Algorithms Through Standard Plan Libraries |
title_short | Comparing Plan Recognition Algorithms Through Standard Plan Libraries |
title_sort | comparing plan recognition algorithms through standard plan libraries |
topic | Artificial Intelligence |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8778577/ https://www.ncbi.nlm.nih.gov/pubmed/35072058 http://dx.doi.org/10.3389/frai.2021.732177 |
work_keys_str_mv | AT mirskyreuth comparingplanrecognitionalgorithmsthroughstandardplanlibraries AT galunran comparingplanrecognitionalgorithmsthroughstandardplanlibraries AT galkobi comparingplanrecognitionalgorithmsthroughstandardplanlibraries AT kaminkagal comparingplanrecognitionalgorithmsthroughstandardplanlibraries |