We describe a novel approach to monitoring high level behaviors using concepts from AI planning. Our goal is to understand what a program is doing based on its system call trace. This ability is particularly important for detecting malware. We approach this problem by building an abstract model of the operating system using the STRIPS planning language, casting system calls as planning operators. Given a system call trace, we simulate the corresponding operators on our model and by observing the properties of the state reached, we learn about the nature of the original program and its behavior. Thus, unlike most statistical detection methods that focus on syntactic features, our approach is semantic in nature. Therefore, it is more robust against obfuscation techniques used by malware that change the outward appearance of the trace but not its effect. We demonstrate the efficacy of our approach by evaluating it on actual system call traces.
Behavior recognition is closely related to plan and goal recognition @cite_12 . Given a sequence of observed actions, the goal is to try to infer the actor's intentions. Typically, the output is a ranked list of hypothesized goals. Most work assumes a library of possible behavior instances, i.e., plans, an approach limited in its ability to go beyond known instances. Probabilistic techniques, such as @cite_1 use Bayesian methods to assess the probability of various goals based on the actions involved. An influential recent approach is plan-recognition as planning @cite_14 , where the authors do away with the assumption of an explicit plan library. The plan library is replaced by a model of the domain (which implicitly defines the set of possible plans), and the goal is to compute a good plan that is closest to the observed behavior. This line of work is appropriate when the observations are a subset of the actual actions taken, or when we attempt to recognize the goal before plan completion. We attempt to recognize malicious behavior off-line given a complete trace, although extensions for the online setting are natural.
@cite_14 @cite_1 @cite_12
1575558843 2119199958
Goal Recognition is the task of inferring an actor's goals given some or all of the actor's observed actions. There is considerable interest in Goal Recognition for use in intelligent personal assistants, smart environments, intelligent tutoring systems, and monitoring user's needs. In much of this work, the actor's observed actions are compared against a generated library of plans. Recent work by Ramirez and Geffner makes use of AI planning to determine how closely a sequence of observed actions matches plans for each possible goal. For each goal, this is done by comparing the cost of a plan for that goal with the cost of a plan for that goal that includes the observed actions. This approach yields useful rankings, but is impractical for real-time goal recognition in large domains because of the computational expense of constructing plans for each possible goal. In this paper, we introduce an approach that propagates cost and interaction information in a plan graph, and uses this information to estimate goal probabilities. We show that this approach is much faster, but still yields high quality results. Plan recognition is the problem of inferring the goals and plans of an agent after observing its behavior. Recently, it has been shown that this problem can be solved efficiently, without the need of a plan library, using slightly modified planning algorithms. In this work, we extend this approach to the more general problem of probabilistic plan recognition where a probability distribution over the set of goals is sought under the assumptions that actions have deterministic effects and both agent and observer have complete information about the initial state. We show that this problem can be solved efficiently using classical planners provided that the probability of a partially observed execution given a goal is defined in terms of the cost difference of achieving the goal under two conditions: complying with the observations, and not complying with them. This cost, and hence the posterior goal probabilities, are computed by means of two calls to a classical planner that no longer has to be modified in any way. A number of examples is considered to illustrate the quality, flexibility, and scalability of the approach. Plan recognition is the problem of inferring the goals and plans of an agent from partial observations of her behavior. Recently, it has been shown that the problem can be formulated and solved using planners, reducing plan recognition to plan generation. In this work, we extend this model-based approach to plan recognition to the POMDP setting, where actions are stochastic and states are partially observable. The task is to infer a probability distribution over the possible goals of an agent whose behavior results from a POMDP model. The POMDP model is shared between agent and observer except for the true goal of the agent that is hidden to the observer. The observations are action sequences O that may contain gaps as some or even most of the actions done by the agent may not be observed. We show that the posterior goal distribution P(G|O) can be computed from the value function VG(b) over beliefs b generated by the POMDP planner for each possible goal G. Some extensions of the basic framework are discussed, and a number of experiments are reported. We introduce a novel framework to formalize and solve transparent planning tasks by executing actions selected in a suitable and timely fashion. A transparent planning task is defined as a task where the objective of the agent is to communicate its true goal to observers, thereby making its intentions and its action selection transparent. We formally define and model these tasks as Goal POMDPs where the state space is the Cartesian product of the states of the world and a given set of hypothetical goals. Action effects are deterministic in the world states of the problem but probabilistic in the observer's beliefs. Transition probabilities are obtained from making a call to a model-based plan recognition algorithm, which we refer to as an observer stereotype. We propose an action selection strategy via on-line planning that seeks actions to quickly convey the goal being pursued to an observer assumed to fit a given stereotype. In order to keep run-times feasible, we propose a novel model-based plan recognition algorithm that approximates well-known probabilistic plan recognition methods. The resulting on-line planner, after being evaluated over a diverse set of domains and three different observer stereotypes, is found to convey goal information faster than purely goal-directed planners. In this work we aim to narrow the gap between plan recognition and planning by exploiting the power and generality of recent planning algorithms for recognizing the set G* of goals G that explain a sequence of observations given a domain theory. After providing a crisp definition of this set, we show by means of a suitable problem transformation that a goal G belongs to G* if there is an action sequence π that is an optimal plan for both the goal G and the goal G extended with extra goals representing the observations. Exploiting this result, we show how the set G* can be computed exactly and approximately by minor modifications of existing optimal and suboptimal planning algorithms, and existing polynomial heuristics. Experiments over several domains show that the suboptimal planning algorithms and the polynomial heuristics provide good approximations of the optimal goal set G* while scaling up as well as state-of-the-art planning algorithms and heuristics. Humans are adept at inferring the mental states underlying other agents’ actions, such as goals, beliefs, desires, emotions and other thoughts. We propose a computational framework based on Bayesian inverse planning for modeling human action understanding. The framework represents an intuitive theory of intentional agents’ behavior based on the principle of rationality: the expectation that agents will plan approximately rationally to achieve their goals, given their beliefs about the world. The mental states that caused an agent’s behavior are inferred by inverting this model of rational planning using Bayesian inference, integrating the likelihood of the observed actions with the prior over mental states. This approach formalizes in precise probabilistic terms the essence of previous qualitative approaches to action understanding based on an ‘‘intentional stance” [Dennett, D. C. (1987). The intentional stance. Cambridge, MA: MIT Press] or a ‘‘teleological stance” [Gergely, G., Nadasdy, Z., Csibra, G., & Biro, S. (1995). Taking the intentional stance at 12 months of age. Cognition, 56, 165–193]. In three psychophysical experiments using animated stimuli of agents moving in simple mazes, we assess how well different inverse planning models based on different goal priors can predict human goal inferences. The results provide quantitative evidence for an approximately rational inference mechanism in human goal inference within our simplified stimulus paradigm, and for the flexible nature of goal representations that human observers can adopt. We discuss the implications of our experimental results for human action understanding in real-world contexts, and suggest how our framework might be extended to capture other kinds of mental state inferences, such as inferences about beliefs, or inferring whether an entity is an intentional agent. Most human behaviors consist of multiple parts, steps, or sub-tasks. These structures guide our action planning and execution, but when we observe others, the latent structure of their actions is typically unobservable, and must be inferred in order to learn new skills by demonstration, or to assist others in completing their tasks. For example, an assistant who has learned the subgoal structure of a colleague's task can more rapidly recognize and support their actions as they unfold. Here we model how humans infer subgoals from observations of complex action sequences using a nonparametric Bayesian model, which assumes that observed actions are generated by approximately rational planning over unknown subgoal sequences. We test this model with a behavioral experiment in which humans observed different series of goal-directed actions, and inferred both the number and composition of the subgoal sequences associated with each goal. The Bayesian model predicts human subgoal inferences with high accuracy, and significantly better than several alternative models and straightforward heuristics. Motivated by this result, we simulate how learning and inference of subgoals can improve performance in an artificial user assistance task. The Bayesian model learns the correct subgoals from fewer observations, and better assists users by more rapidly and accurately inferring the goal of their actions than alternative approaches. Possessing a sufficient level of situation awareness is essential for effective decision making in dynamic environments. In video games, this includes being aware to some extent of the intentions of the opponents. Such high-level awareness hinges upon inferences over the lower-level situation awareness provided by the game state. Traditional plan recognizers are completely passive processes that leave all the initiative to the observed agent. In a situation where the opponent’s intentions are unclear, the observer is forced to wait until further observations of the opponent’s actions are made to disambiguate the pending goal hypotheses. With the plan recognizer we propose, in contrast, the observer would take the initiative and provoke the opponent, with the expectation that his reaction will give cues as to what his true intentions actually are. Plan recognition is of course only one component of a larger AI system which in addition involves components to make decisions on how to act against the opposing force, execute and monitor planned and reactive actions, and learn from past interactions to adapt accordingly. Our long term objective is to develop plan recognition and planning algorithms that will compete against humans in games and other applications. The unlimited creativity of the human mind coupled with its sometimes chaotic and unpredictable nature makes this challenge very exciting. Abstract We argue that the problem of plan recognition, inferring an agent's plan from observations, is largely a problem of inference under conditions of uncertainty. We present an approach to the plan recognition problem that is based on Bayesian probability theory. In attempting to solve a plan recognition problem we first retrieve candidate explanations. These explanations (sometimes only the most promising ones) are assembled into a plan recognition Bayesian network , which is a representation of a probability distribution over the set of possible explanations. We perform Bayesian updating to choose the most likely interpretation for the set of observed actions. This approach has been implemented in the Wimp3 system for natural language story understanding. Everyday social interactions are heavily influenced by our snap judgments about others' goals. Even young infants can infer the goals of intentional agents from observing how they interact with objects and other agents in their environment: e.g., that one agent is 'helping' or 'hindering' another's attempt to get up a hill or open a box. We propose a model for how people can infer these social goals from actions, based on inverse planning in multiagent Markov decision problems (MDPs). The model infers the goal most likely to be driving an agent's behavior by assuming the agent acts approximately rationally given environmental constraints and its model of other agents present. We also present behavioral evidence in support of this model over a simpler, perceptual cue-based alternative. Knowing a user's plans and goals can significantly improve the effectiveness of an interactive system. However, recognizing such goals and the user's intended plan for achieving them is not an easy task. Although much research has dealt with representing the knowledge necessary for plan inference and developing strategies that hypothesize the user's evolving plans, a number of serious problems still impede the use of plan recognition in large-scale, real-world applications. This paper describes the various approaches that have been taken to plan inference, along with techniques for dealing with ambiguity, robustness, and representation of requisite domain knowledge, and discusses areas for further research. This paper presents a computational model of how conversational participants collaborate in order to make a referring action successful. The model is based on the view of language as goal-directed behavior. We propose that the content of a referring expression can be accounted for by the planning paradigm. Not only does this approach allow the processes of building referring expressions and identifying their referents to be captured by plan construction and plan inference, it also allows us to account for how participants clarify a referring expression by using meta-actions that reason about and manipulate the plan derivation that corresponds to the referring expression. To account for how clarification goals arise and how inferred clarification plans affect the agent, we propose that the agents are in a certain state of mind, and that this state includes an intention to achieve the goal of referring and a plan that the agents are currently considering. It is this mental state that sanctions the adoption of goals and the acceptance of inferred plans, and so acts as a link between understanding and generation. Human agents are extremely flexible in dealing with Natural Language instructions. I argue that most instructions don't exactly mirror the agent's knowledge, but are understood by accommodating them in the context of the general plan the agent is considering; the accommodation process is guided by the goal(s) that the agent is trying to achieve. Therefore a NL system which interprets instructions must be able to recognize and or hypothesize goals; it must make use of a flexible knowledge representation system, able to support the specialized inferences necessary to deal with input action descriptions that do not exactly match the stored knowledge. The data that support my claim are Purpose Clauses (PCs), infinitival constructions as in @math , and Negative Imperatives. I present a pragmatic analysis of both PCs and Negative Imperatives. Furthermore, I analyze the computational consequences of PCs, in terms of the relations between actions PCs express, and of the inferences an agent has to perform to understand PCs. I propose an action representation formalism that provides the required flexibility. It has two components. The Terminological Box (TBox) encodes linguistic knowledge about actions, and is expressed by means of the hybrid system CLASSIC. To guarantee that the primitives of the representation are linguistically motivated, I derive them from Jackendoff's work on Conceptual Structures. The Action Library encodes planning knowledge about actions. The action terms used in the plans are those defined in the TBox. Finally, I present an algorithm that implements inferences necessary to understand @math , and supported by the formalism I propose. In particular, I show how the TBox classifier is used to infer whether @math can be assumed to match one of the substeps in the plan for @math , and how expectations necessary for the match to hold are computed. Natural language interfaces for robot control aspire to find the best sequence of actions that reflect the behavior intended by the instruction. This is difficult because of the diversity of language, variety of environments, and heterogeneity of tasks. Previous work has demonstrated that probabilistic graphical models constructed from the parse structure of natural language can be used to identify motions that most closely resemble verb phrases. Such approaches however quickly succumb to computational bottlenecks imposed by construction and search the space of possible actions. Planning constraints, which define goal regions and separate the admissible and inadmissible states in an environment model, provide an interesting alternative to represent the meaning of verb phrases. In this paper we present a new model called the Distributed Correspondence Graph (DCG) to infer the most likely set of planning constraints from natural language instructions. A trajectory planner then uses these planning constraints to find a sequence of actions that resemble the instruction. Separating the problem of identifying the action encoded by the language into individual steps of planning constraint inference and motion planning enables us to avoid computational costs associated with generation and evaluation of many trajectories. We present experimental results from comparative experiments that demonstrate improvements in efficiency in natural language understanding without loss of accuracy. Planning for extended goals in non-deterministic domains is one of the most significant and challenging planning problems. In spite of the recent results in this field, no work has proposed a language designed specifically for planning. As a consequence, it is still impossible to specify and plan for several classes of goals that are typical of real world applications, like for instance "try to achieve a goal whenever possible", or "if you fail to achieve a goal, recover by trying to achieve something else".We propose a new goal language that allows for capturing the intended meaning of these goals. We give a semantics to this language that is radically different from the usual semantics for extended goals, e.g., the semantics for LTL or CTL. Finally, we implement an algorithm for planning for extended goals expressed in this language, and experiment with it on a parametric domain. Abstract : Discourses are fundamentally instances of collaboration behavior. We propose a model of the collaborative plans of agents achieving joint goals and illustrate the role of these plans in discourses. Three types of collaborative plans, called Shared Plans, are formulated for joint goals requiring simultaneous, conjoined or sequential actions on the part of the agents who participate in the plans and the discourse; a fourth type of Shared Plan is presented for the circumstance where two agents communicate, but only one acts. Generating plans for a single agent has been shown to be a difficult task. If we generalize to a multi-agent setting, the problem becomes exponentially harder in general. The centralized approach where a plan is jointly generated for all agents is only possible in some applications when agents do not have private goals, actions or states. We describe in this paper an alternative approach, MAPR (Multi-Agent Planning by plan Reuse), that considers both the agents private and public information. We have been inspired by iterative Multi-Agent Planning (MAP) techniques as the one presented in [1]. MAPR first assigns a subset of public goals to each agent, while each agent might have a set of private goals also. Then, MAPR calls the first agent to provide a solution (plan) that takes into account its private and public goals. MAPR iteratively calls each agent with the solutions provided by previous agents. Each agent receives its own goals plus the goals of the previous agents. Thus, each agent solves its problem, but taking into account the previous agents solutions. Since previous solutions might consider private data, all private information from an agent is obfuscated for the next ones. Since each agent receives the plan from the previous agent that implicitly considers the solutions to all previous agents, instead of starting the search from scratch, it can also reuse the previous whole plan or only a subset of the actions. Experiments show that MAPR outperforms in several orders of magnitude state-of-the-art techniques in the tested domains. Research in discourse analysis, story understanding, and user modeling for expert systems has shown great interest in plan recognition problems. In a plan recognition problem, one is given a fragmented description of actions performed by one or more agents, and expected to infer the overall plan or scenario which explains those actions. This thesis develops the first formal description of the plan recognition process. Beginning with a reified logic of events, the thesis presents a scheme for hierarchically structuring a library of event types. A semantic basis for non-deductive inference, called "minimum covering entailment", justifies the conclusions that one may draw from a set of observed actions. Minimum covering entailment is defined by delineating the class of models in which the library is complete and the set of unrelated observations is minimized. An equivalent proof theory forms a preliminary basis for mechanizing the theory. Equivalence theorems between the proof and model theories are presented. Minimum covering entailment is related to a formalism for non-monotonic inference known as "circumscription". Finally, the thesis describes a number of algorithms which correctly implement the theory, together with a discussion of their complexity. The theory is applied to a number of examples of plan recognition, in domains ranging from an operating system advisor to the theory of speech acts. The thesis shows how problems of medical diagnosis, a similar kind of non-deductive reasoning, can be cast in the framework, and an example previously solved by a medical expert system is worked out in detail. The analyses provides a firm theoretical foundation for much of what is loosely called "frame based inference", and directly accounts for problems of ambiguity, abstraction, and complex temporal interactions, which were ignored by previous work. The framework can be extended to handle difficult phenomena such as errors, and can also be restricted in order to improve its computational properties in specialized domains. We present the PHATT algorithm for plan recognition. Unlike previous approaches to plan recognition, PHATT is based on a model of plan execution. We show that this clarifies several difficult issues in plan recognition including the execution of multiple interleaved root goals, partially ordered plans, and failing to observe actions. We present the PHATT algorithm's theoretical basis, and an implementation based on tree structures. We also investigate the algorithm's complexity, both analytically and empirically. Finally, we present PHATT's integrated constraint reasoning for parametrized actions and temporal constraints. In classical planning, the planner is given a concrete goal; it returns a plan for it or a failure message. In the latter case, the user can either quit or modify the goal. For many applications, it is more convenient to let the user provide a more elaborate specification consisting of constraints and preferences over possible goal states. Then, let the system discover a plan for the most desirable among the feasible goal states. To materialize such an approach we require a formalism for specifying preferences and constraints over goals and an algorithm for solving the resulting constrained optimization problem. In this work we motivate the need for planning with preferences and constraints, suggest a rich, yet intuitive formalism for representing goal preferences in the context of a deterministic action model, discuss some of its properties, propose an efficient algorithm for planning with preferences and constraints based on this formalism, and provide extensive experimental analysis in an interesting new domain of configuration planning.