Christian Muise

IJCAI Conference 2024 Conference Paper

A Goal-Directed Dialogue System for Assistance in Safety-Critical Application

• Prakash Jamakatel
• Rebecca De Venezia
• Christian Muise
• Jane Jean Kiam

In safety-critical applications where a human is in the loop, providing timely contextual assistance can reduce the severity of emergencies. While the context can typically be inferred passively, engaging the human in an active conversation with the assistance system makes this context richer and more sound. For this, we explore a FOND-planning-powered goal-directed dialogue system with Natural Language Understanding (NLU) capabilities. We use an Ultralight (UL) aviation domain as an example application for test and validation by inferring the current context in situations requiring emergency landings using the goal-directed dialogue system. The inferred context is then used for real-time modelling of the problem instance, necessary for generating strategic plans to guide the human out of the emergency situations. To overcome data scarcity, we augment the data collected from human pilots using generative text models to train the NLU capabilities of the dialogue agent. We benchmark against generative chatbots and demonstrate that our goal-directed dialogue system significantly outperforms them in context inference.

IJCAI Conference 2024 Conference Paper

A Survey on Plan Optimization

• Pascal Bercher
• Patrik Haslum
• Christian Muise

Automated Planning deals with finding a sequence of actions that solves a given (planning) problem. The cost of the solution is a direct consequence of these actions, for example its number or their accumulated costs. Thus, in most applications, cheaper plans are preferred. Yet, finding an optimal solution is more challenging than finding some solution. So, many planning algorithms find some solution and then post-process, i. e. , optimize it -- a technique called plan optimization. Over the years many different approaches were developed, not all for the same kind of plans, and not all optimize the same metric. In this comprehensive survey, we give an overview of the existing plan optimization goals, their computational complexity (if known), and existing techniques for such optimizations.

AIJ Journal 2024 Journal Article

Planning with mental models – Balancing explanations and explicability

• Sarath Sreedharan
• Tathagata Chakraborti
• Christian Muise
• Subbarao Kambhampati

Human-aware planning involves generating plans that are explicable, i. e. conform to user expectations, as well as providing explanations when such plans cannot be found. In this paper, we bring these two concepts together and show how an agent can achieve a trade-off between these two competing characteristics of a plan. To achieve this, we conceive a first-of-its-kind planner MEGA that can reason about the possibility of explaining a plan in the plan generation process itself. We will also explore how solutions to such problems can be expressed as “self-explaining plans” – and show how this representation allows us to leverage classical planning compilations of epistemic planning to reason about this trade-off at plan generation time without having to incur the computational burden of having to search in the space of differences between the agent model and the mental model of the human in the loop in order to come up with the optimal trade-off. We will illustrate these concepts in two well-known planning domains, as well as with a robot in a typical search and reconnaissance task. Human factor studies in the latter highlight the usefulness of the proposed approach.

AAAI Conference 2024 Conference Paper

PRP Rebooted: Advancing the State of the Art in FOND Planning

• Christian Muise
• Sheila A. McIlraith
• J. Christopher Beck

Fully Observable Non-Deterministic (FOND) planning is a variant of classical symbolic planning in which actions are nondeterministic, with an action's outcome known only upon execution. It is a popular planning paradigm with applications ranging from robot planning to dialogue-agent design and reactive synthesis. Over the last 20 years, a number of approaches to FOND planning have emerged. In this work, we establish a new state of the art, following in the footsteps of some of the most powerful FOND planners to date. Our planner, PR2, decisively outperforms the four leading FOND planners, at times by a large margin, in 17 of 18 domains that represent a comprehensive benchmark suite. Ablation studies demonstrate the impact of various techniques we introduce, with the largest improvement coming from our novel FOND-aware heuristic.

NeurIPS Conference 2023 Conference Paper

Egocentric Planning for Scalable Embodied Task Achievement

• Xiatoian Liu
• Hector Palacios
• Christian Muise

Embodied agents face significant challenges when tasked with performing actions in diverse environments, particularly in generalizing across object types and executing suitable actions to accomplish tasks. Furthermore, agents should exhibit robustness, minimizing the execution of illegal actions. In this work, we present Egocentric Planning, an innovative approach that combines symbolic planning and Object-oriented POMDPs to solve tasks in complex environments, harnessing existing models for visual perception and natural language processing. We evaluated our approach in ALFRED, a simulated environment designed for domestic tasks, and demonstrated its high scalability, achieving an impressive 36. 07\% unseen success rate in the ALFRED benchmark and winning the ALFRED challenge at CVPR Embodied AI workshop. Our method requires reliable perception and the specification or learning of a symbolic description of the preconditions and effects of the agent's actions, as well as what object types reveal information about others. It can naturally scale to solve new tasks beyond ALFRED, as long as they can be solved using the available skills. This work offers a solid baseline for studying end-to-end and hybrid methods that aim to generalize to new tasks, including recent approaches relying on LLMs, but often struggle to scale to long sequences of actions or produce robust plans for novel tasks.

KR Conference 2023 Conference Paper

Planning with Epistemic Preferences

• Toryn Q. Klassen
• Christian Muise
• Sheila A. McIlraith

Within the field of automated planning, two areas of study are planning with preferences and epistemic planning. Planning with preferences involves generating plans that optimize for properties of the plan instead of, or in addition to, trying to reach a fixed goal. Epistemic planning allows for planning over the knowledge or belief states of one or more agents for the purpose of achieving epistemic goals (where agents have particular states of knowledge or belief). In this paper we motivate and explore the task of planning with epistemic preferences, proposing a method by which existing automated planning techniques can be combined for this purpose.

HAXP Workshop 2023 Workshop Paper

Towards Human-Aware AI via Planning with Epistemic Preferences

• Toryn Q. Klassen
• Christian Muise
• Sheila A. McIlraith

Within the field of automated planning, two areas of study are planning with preferences and epistemic planning. Planning with preferences involves generating plans that optimize for properties of the plan instead of, or in addition to, trying to reach a fixed goal. Epistemic planning allows for planning over the knowledge or belief states of one or more agents for the purpose of achieving epistemic goals (where agents have particular states of knowledge or belief). In this paper we motivate and explore the task of planning with epistemic preferences, proposing a method by which existing automated planning techniques can be combined for this purpose. Epistemic preferences may better allow for representing what humans want, and have benefits for AI safety.

JAIR Journal 2022 Journal Article

Classical Planning in Deep Latent Space

• Masataro Asai
• Hiroshi Kajino
• Alex Fukunaga
• Christian Muise

Current domain-independent, classical planners require symbolic models of the problem domain and instance as input, resulting in a knowledge acquisition bottleneck. Meanwhile, although deep learning has achieved significant success in many fields, the knowledge is encoded in a subsymbolic representation which is incompatible with symbolic systems such as planners. We propose Latplan, an unsupervised architecture combining deep learning and classical planning. Given only an unlabeled set of image pairs showing a subset of transitions allowed in the environment (training inputs), Latplan learns a complete propositional PDDL action model of the environment. Later, when a pair of images representing the initial and the goal states (planning inputs) is given, Latplan finds a plan to the goal state in a symbolic latent space and returns a visualized plan execution. We evaluate Latplan using image-based versions of 6 planning domains: 8-puzzle, 15-Puzzle, Blocksworld, Sokoban and Two variations of LightsOut.

AIJ Journal 2022 Journal Article

Efficient multi-agent epistemic planning: Teaching planners about nested belief

• Christian Muise
• Vaishak Belle
• Paolo Felli
• Sheila McIlraith
• Tim Miller
• Adrian R. Pearce
• Liz Sonenberg

Many AI applications involve the interaction of multiple autonomous agents, requiring those agents to reason about their own beliefs, as well as those of other agents. However, planning involving nested beliefs is known to be computationally challenging. In this work, we address the task of synthesizing plans that necessitate reasoning about the beliefs of other agents. We plan from the perspective of a single agent with the potential for goals and actions that involve nested beliefs, non-homogeneous agents, co-present observations, and the ability for one agent to reason as if it were another. We formally characterize our notion of planning with nested belief, and subsequently demonstrate how to automatically convert such problems into problems that appeal to classical planning technology for solving efficiently. Our approach represents an important step towards applying the well-established field of automated planning to the challenging task of planning involving nested beliefs of multiple agents.

AAAI Conference 2022 Conference Paper

Planning to Avoid Side Effects

• Toryn Q. Klassen
• Sheila A. McIlraith
• Christian Muise
• Jarvis Xu

In sequential decision making, objective specifications are often underspecified or incomplete, neglecting to take into account potential (negative) side effects. Executing plans without consideration of their side effects can lead to catastrophic outcomes – a concern recently raised in relation to the safety of AI. In this paper we investigate how to avoid side effects in a symbolic planning setting. We study the notion of minimizing side effects in the context of a planning environment where multiple independent agents co-exist. We define (classes of) negative side effects in terms of their effect on the agency of those other agents. Finally, we show how plans which minimize side effects of different types can be computed via compilations to cost-optimizing symbolic planning, and investigate experimentally.

AAAI Conference 2020 Conference Paper

Expectation-Aware Planning: A Unifying Framework for Synthesizing and Executing Self-Explaining Plans for Human-Aware Planning

• Sarath Sreedharan
• Tathagata Chakraborti
• Christian Muise
• Subbarao Kambhampati

In this work, we present a new planning formalism called Expectation-Aware planning for decision making with humans in the loop where the human’s expectations about an agent may differ from the agent’s own model. We show how this formulation allows agents to not only leverage existing strategies for handling model differences like explanations (Chakraborti et al. 2017) and explicability (Kulkarni et al. 2019), but can also exhibit novel behaviors that are generated through the combination of these different strategies. Our formulation also reveals a deep connection to existing approaches in epistemic planning. Specifically, we show how we can leverage classical planning compilations for epistemic planning to solve Expectation-Aware planning problems. To the best of our knowledge, the proposed formulation is the first complete solution to planning with diverging user expectations that is amenable to a classical planning compilation while successfully combining previous works on explanation and explicability. We empirically show how our approach provides a computational advantage over our earlier approaches that rely on search in the space of models.

IJCAI Conference 2020 Conference Paper

Learning Neural-Symbolic Descriptive Planning Models via Cube-Space Priors: The Voyage Home (to STRIPS)

• Masataro Asai
• Christian Muise

We achieved a new milestone in the difficult task of enabling agents to learn about their environment autonomously. Our neuro-symbolic architecture is trained end-to-end to produce a succinct and effective discrete state transition model from images alone. Our target representation (the Planning Domain Definition Language) is already in a form that off-the-shelf solvers can consume, and opens the door to the rich array of modern heuristic search capabilities. We demonstrate how the sophisticated innate prior we place on the learning process significantly reduces the complexity of the learned representation, and reveals a connection to the graph-theoretic notion of ``cube-like graphs'', thus opening the door to a deeper understanding of the ideal properties for learned symbolic representations. We show that the powerful domain-independent heuristics allow our system to solve visual 15-Puzzle instances which are beyond the reach of blind search, without resorting to the Reinforcement Learning approach that requires a huge amount of training on the domain-dependent reward information.

AAAI Conference 2020 System Paper

TraceHub – A Platform to Bridge the Gap between State-of-the-Art Time-Series Analytics and Datasets

• Shubham Agarwal
• Christian Muise
• Mayank Agarwal
• Sohini Upadhyay
• Zilu Tang
• Zhongshen Zeng
• Yasaman Khazaeni

In this paper, we present TraceHub - a platform that connects new non-trivial state-of-the-art time-series analytics with datasets from different domains. Analytics owners can run their insights on new datasets in an automated setting to find insight’s potential and improve it. Dataset owners can find all possible types of non-trivial insights based on latest research. We provide a plug-n-play system as a set of Dataset, Transformer pipeline, and Analytics APIs for both kinds of users. We show a usefulness measure of generated insights across various types of analytics in the system. We believe that this platform can be used to bridge the gap between time-series analytics and datasets by significantly reducing the time to find the true potential of budding timeseries research and improving on it faster.

IJCAI Conference 2019 Conference Paper

Bayesian Inference of Linear Temporal Logic Specifications for Contrastive Explanations

• Joseph Kim
• Christian Muise
• Ankit Shah
• Shubham Agarwal
• Julie Shah

Temporal logics are useful for providing concise descriptions of system behavior, and have been successfully used as a language for goal definitions in task planning. Prior works on inferring temporal logic specifications have focused on "summarizing" the input dataset - i. e. , finding specifications that are satisfied by all plan traces belonging to the given set. In this paper, we examine the problem of inferring specifications that describe temporal differences between two sets of plan traces. We formalize the concept of providing such contrastive explanations, then present BayesLTL - a Bayesian probabilistic model for inferring contrastive explanations as linear temporal logic (LTL) specifications. We demonstrate the robustness and scalability of our model for inferring accurate specifications from noisy data and across various benchmark planning domains.

IJCAI Conference 2019 Conference Paper

Evaluating the Interpretability of the Knowledge Compilation Map: Communicating Logical Statements Effectively

• Serena Booth
• Christian Muise
• Julie Shah

Knowledge compilation techniques translate propositional theories into equivalent forms to increase their computational tractability. But, how should we best present these propositional theories to a human? We analyze the standard taxonomy of propositional theories for relative interpretability across three model domains: highway driving, emergency triage, and the chopsticks game. We generate decision-making agents which produce logical explanations for their actions and apply knowledge compilation to these explanations. Then, we evaluate how quickly, accurately, and confidently users comprehend the generated explanations. We find that domain, formula size, and negated logical connectives significantly affect comprehension while formula properties typically associated with interpretability are not strong predictors of human ability to comprehend the theory.

AAAI Conference 2019 System Paper

MAi: An Intelligent Model Acquisition Interface for Interactive Specification of Dialogue Agents

• Tathagata Chakraborti
• Christian Muise
• Shubham Agarwal
• Luis A. Lastras

The state of the art in automated conversational agents for enterprise (e.g. for customer support) require a lengthy design process with experts in the loop who have to figure out and specify complex conversation patterns. This demonstration looks at a prototype interface that aims to bring down the expertise required to design such agents as well as the time taken to do so. Specifically, we will focus on how a metawriter can assist the domain-writer during the design process and how complex conversation patterns can be derived from simplifying abstractions at the interface level.

IJCAI Conference 2018 Conference Paper

LTL Realizability via Safety and Reachability Games

• Alberto Camacho
• Christian Muise
• Jorge A. Baier
• Sheila A. McIlraith

In this paper, we address the problem of LTL realizability and synthesis. State of the art techniques rely on so-called bounded synthesis methods, which reduce the problem to a safety game. Realizability is determined by solving synthesis in a dual game. We provide a unified view of duality, and introduce novel bounded realizability methods via reductions to reachability games. Further, we introduce algorithms, based on AI automated planning, to solve these safety and reachability games. This is the the first complete approach to LTL realizability and synthesis via automated planning. Experiments illustrate that reductions to reachability games are an alternative to reductions to safety games, and show that planning can be a competitive approach to LTL realizability and synthesis.

IJCAI Conference 2018 Conference Paper

Managing Communication Costs under Temporal Uncertainty

• Nikhil Bhargava
• Christian Muise
• Tiago Vaquero
• Brian Williams

In multi-agent temporal planning, individual agents cannot know a priori when other agents will execute their actions and so treat those actions as uncertain. Only when others communicate the results of their actions is that uncertainty resolved. If a full communication protocol is specified ahead of time, then delay controllability can be used to assess the feasibility of the temporal plan. However, agents often have flexibility in choosing when to communicate the results of their action. In this paper, we address the question of how to choose communication protocols that guarantee the feasibility of the original temporal plan subject to some cost associated with that communication. To do so, we introduce a means of extracting delay controllability conflicts and show how we can use these conflicts to more efficiently guide our search. We then present three conflict-directed search algorithms and explore the theoretical and empirical trade-offs between the different approaches.

IJCAI Conference 2018 Conference Paper

SynKit: LTL Synthesis as a Service

• Alberto Camacho
• Christian Muise
• Jorge A. Baier
• Sheila A. McIlraith

Automatic synthesis of software from specification is one of the classic problems in computer science. In the last decade, significant advances have been made in the synthesis of programs from specifications expressed in Linear Temporal Logic (LTL). LTL synthesis technology is central to a myriad of applications from the automated generation of controllers for Internet of Things devices, to the synthesis of control software for robotic applications. Unfortunately, the number of existing tools for LTL synthesis is limited, and using them requires specialized expertise. In this paper we present SynKit, a tool that offers LTL synthesis as a service. SynKit integrates a RESTful API and a web service with an editor, a solver, and a strategy visualizer.

IJCAI Conference 2018 Conference Paper

Variable-Delay Controllability

• Nikhil Bhargava
• Christian Muise
• Brian Williams

In temporal planning, agents must schedule a set of events satisfying a set of predetermined constraints. These scheduling problems become more difficult when the duration of certain actions are outside the agent's control. Delay controllability is the generalized notion of whether a schedule can be constructed in the face of uncertainty if the agent eventually learns when events occur. Our work introduces the substantially more complex setting of determining variable-delay controllability, where an agent learns about events after some unknown but bounded amount of time has passed. We provide an efficient O(n^3) variable-delay controllability checker and show how to create an execution strategy for variable-delay controllability problems. To our knowledge, these essential capabilities are absent from existing controllability checking algorithms. We conclude by providing empirical evaluations of the quality of variable-delay controllability results as compared to approximations that use fixed delays to model the same problems.

AAAI Conference 2017 Conference Paper

Logical Filtering and Smoothing: State Estimation in Partially Observable Domains

• Brent Mombourquette
• Christian Muise
• Sheila McIlraith

State estimation is the task of estimating the state of a partially observable dynamical system given a sequence of executed actions and observations. In logical settings, state estimation can be realized via logical filtering, which is exact but can be intractable. We propose logical smoothing, a form of backwards reasoning that works in concert with approximated logical filtering to refine past beliefs in light of new observations. We characterize the notion of logical smoothing together with an algorithm for backwards-forwards state estimation. We also present an approximation of our smoothing algorithm that is space efficient. We prove properties of our algorithms, and experimentally demonstrate their behaviour, contrasting them with state estimation methods for planning. Smoothing and backwards-forwards reasoning are important techniques for reasoning about partially observable dynamical systems, introducing the logical analogue of effective techniques from control theory and dynamic programming.

AAAI Conference 2017 Conference Paper

Non-Deterministic Planning with Temporally Extended Goals: LTL over Finite and Infinite Traces

• Alberto Camacho
• Eleni Triantafillou
• Christian Muise
• Jorge Baier
• Sheila McIlraith

Temporally extended goals are critical to the specification of a diversity of real-world planning problems. Here we examine the problem of non-deterministic planning with temporally extended goals specified in linear temporal logic (LTL), interpreted over either finite or infinite traces. Unlike existing LTL planners, we place no restrictions on our LTL formulae beyond those necessary to distinguish finite from infinite interpretations. We generate plans by compiling LTL temporally extended goals into problem instances described in the Planning Domain Definition Language that are solved by a state-of-the-art fully observable non-deterministic planner. We propose several different compilations based on translations of LTL to alternating or non-deterministic (Büchi) automata, and evaluate various properties of the competing approaches. We address a diverse spectrum of LTL planning problems that, to this point, had not been solvable using AI planning techniques, and do so in a manner that demonstrates highly competitive performance.

IJCAI Conference 2016 Conference Paper

Belief Update for Proper Epistemic Knowledge Bases

• Tim Miller
• Christian Muise

Reasoning about the nested beliefs of others is important in many multi-agent scenarios. While epistemic and doxastic logics lay a solid groundwork to approach such reasoning, the computational complexity of these logics is often too high for many tasks. Proper Epistemic Knowledge Bases (PEKBs) enforce two syntactic restrictions on formulae to obtain efficient querying: both disjunction and infinitely long nestings of modal operators are not permitted. PEKBs can be compiled, in exponential time, to a prime implicate formula that can be queried in polynomial time, while more recently, it was shown that consistent PEKBs had certain logical properties that meant this compilation was unnecessary, while still retaining polynomial-time querying. In this paper, we present a belief update mechanism for PEKBs that ensures the knowledge base remains consistent when new beliefs are added. This is achieved by first erasing any formulae that contradict these new beliefs. We show that this update mechanism can be computed in polynomial time, and we assess it against the well-known KM postulates for belief update.

AAAI Conference 2016 Conference Paper

Knowing Whether’ in Proper Epistemic Knowledge Bases

• Tim Miller
• Paolo Felli
• Christian Muise
• Adrian Pearce
• Liz Sonenberg

Proper epistemic knowledge bases (PEKBs) are syntactic knowledge bases that use multi-agent epistemic logic to represent nested multi-agent knowledge and belief. PEKBs have certain syntactic restrictions that lead to desirable computational properties; primarily, a PEKB is a conjunction of modal literals, and therefore contains no disjunction. Sound entailment can be checked in polynomial time, and is complete for a large set of arbitrary formulae in logics Kn and KDn. In this paper, we extend PEKBs to deal with a restricted form of disjunction: ‘knowing whether’. An agent i knows whether ϕ iff agent i knows ϕ or knows ¬ϕ; that is, iϕ ∨ i¬ϕ. In our experience, the ability to represent that an agent knows whether something holds is useful in many multi-agent domains. We represent knowing whether with a modal operator, Δi, and present sound polynomial-time entailment algorithms on PEKBs with Δi in Kn and KDn, but which are complete for a smaller class of queries than standard PEKBs.

JAIR Journal 2016 Journal Article

Optimal Partial-Order Plan Relaxation via MaxSAT

• Christian Muise
• J. Christopher Beck
• Sheila A. McIlraith

Partial-order plans (POPs) are attractive because of their least-commitment nature, which provides enhanced plan flexibility at execution time relative to sequential plans. Current research on automated plan generation focuses on producing sequential plans, despite the appeal of POPs. In this paper we examine POP generation by relaxing or modifying the action orderings of a sequential plan to optimize for plan criteria that promote flexibility. Our approach relies on a novel partial weighted MaxSAT encoding of a sequential plan that supports the minimization of deordering or reordering of actions. Using a similar technique, we further demonstrate how to remove redundant actions from the plan, and how to combine this criterion with the objective of maximizing a POP's flexibility. Our partial weighted MaxSAT encoding allows us to compute a POP from a sequential plan effectively. We compare the efficiency of our approach to previous methods for POP generation via sequential-plan relaxation. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. We also investigate and confirm the accuracy of the standard flex metric typically used to predict the true flexibility of a POP as measured by the number of linearizations it represents.

IJCAI Conference 2016 Conference Paper

Planning for a Single Agent in a Multi-Agent Environment Using FOND

• Christian Muise
• Paolo Felli
• Tim Miller
• Adrian R. Pearce
• Liz Sonenberg

Single-agent planning in a multi-agent environment is challenging because the actions of other agents can affect our ability to achieve a goal. From a given agent's perspective, actions of others can be viewed as non-deterministic outcomes of that agent's actions. While simple conceptually, this interpretation of planning in a multi-agent environment as non-deterministic planning remains challenging, not only due to the non-determinism resulting from others' actions, but because it is not clear how to compactly model the possible actions of others in the environment. In this paper, we cast the problem of planning in a multi-agent environment as one of Fully-Observable Non-Deterministic (FOND) planning. We extend a non-deterministic planner to plan in a multi-agent setting, allowing non-deterministic planning technology to solve a new class of planning problems. To improve the efficiency in domains too large for solving optimally, we propose a technique to use the goals and possible actions of other agents to focus the search on a set of plausible actions. We evaluate our approach on existing and new multi-agent benchmarks, demonstrating that modelling the other agents' goals improves the quality of the resulting solutions.

IJCAI Conference 2015 Conference Paper

Computing Social Behaviours Using Agent Models

• Paolo Felli
• Tim Miller
• Christian Muise
• Adrian R. Pearce
• Liz Sonenberg

Agents can be thought of as following a social behaviour, depending on the context in which they are interacting. We devise a computationally grounded mechanism to represent and reason about others in social terms, reflecting the local perspective of an agent (first-person view), to support both stereotypical and empathetic reasoning. We use a hierarchy of agent models to discriminate which behaviours of others are plausible, and decide which behaviour for ourselves is socially acceptable, i. e. conforms to the social context. To this aim, we investigate the implications of considering agents capable of various degrees of theory of mind, and discuss a scenario showing how this affects behaviour.

AAAI Conference 2015 Conference Paper

Planning Over Multi-Agent Epistemic States: A Classical Planning Approach

• Christian Muise
• Vaishak Belle
• Paolo Felli
• Sheila McIlraith
• Tim Miller
• Adrian Pearce
• Liz Sonenberg

Many AI applications involve the interaction of multiple autonomous agents, requiring those agents to reason about their own beliefs, as well as those of other agents. However, planning involving nested beliefs is known to be computationally challenging. In this work, we address the task of synthesizing plans that necessitate reasoning about the beliefs of other agents. We plan from the perspective of a single agent with the potential for goals and actions that involve nested beliefs, non-homogeneous agents, co-present observations, and the ability for one agent to reason as if it were another. We formally characterize our notion of planning with nested belief, and subsequently demonstrate how to automatically convert such problems into problems that appeal to classical planning technology. Our approach represents an important first step towards applying the well-established field of automated planning to the challenging task of planning involving nested beliefs of multiple agents.

AAAI Conference 2015 Conference Paper

Stable Model Counting and Its Application in Probabilistic Logic Programming

• Rehan Aziz
• Geoffrey Chu
• Christian Muise
• Peter Stuckey

Model counting is the problem of computing the number of models that satisfy a given propositional theory. It has recently been applied to solving inference tasks in probabilistic logic programming, where the goal is to compute the probability of given queries being true provided a set of mutually independent random variables, a model (a logic program) and some evidence. The core of solving this inference task involves translating the logic program to a propositional theory and using a model counter. In this paper, we show that for some problems that involve inductive definitions like reachability in a graph, the translation of logic programs to SAT can be expensive for the purpose of solving inference tasks. For such problems, direct implementation of stable model semantics allows for more efficient solving. We present two implementation techniques, based on unfounded set detection, that extend a propositional model counter to a stable model counter. Our experiments show that for particular problems, our approach can outperform a state-of-the-art probabilistic logic programming solver by several orders of magnitude in terms of running time and space requirements, and can solve instances of significantly larger sizes on which the current solver runs out of time or memory.

AAAI Conference 2014 Conference Paper

Computing Contingent Plans via Fully Observable Non-Deterministic Planning

• Christian Muise
• Vaishak Belle
• Sheila McIlraith

Planning with sensing actions under partial observability is a computationally challenging problem that is fundamental to the realization of AI tasks in areas as diverse as robotics, game playing, and diagnostic problem solving. Recent work on generating plans for partially observable domains has advocated for online planning, claiming that offline plans are often too large to generate. Here we push the envelope on this challenging problem, proposing a technique for generating conditional (aka contingent) plans offline. The key to our planner’s success is the reliance on state-of-the-art techniques for fully observable non-deterministic (FOND) planning. In particular, we use an existing compilation for converting a planning problem under partial observability and sensing to a FOND planning problem. With a modified FOND planner in hand, we are able to scale beyond previous techniques for generating conditional plans with solutions that are orders of magnitude smaller than previously possible in some domains.

IJCAI Conference 2013 Conference Paper

Flexible Execution of Partial Order Plans with Temporal Constraints

• Christian Muise
• J. Christopher Beck
• Sheila A. McIlraith

We propose a unified approach to plan execution and schedule dispatching that converts a plan, which has been augmented with temporal constraints, into a policy for dispatching. Our approach generalizes the original plan and temporal constraints so that the executor need only consider the subset of state that is relevant to successful execution of valid plan fragments. We can accommodate a variety of calamitous and serendipitous changes to the state of the world by supporting the seamless re-execution or omission of plan fragments, without the need for costly replanning. Our methodology for plan generalization and online dispatching is a novel combination of plan execution and schedule dispatching techniques. We demonstrate the effectiveness of our method through a prototype implementation and a series of experiments.

AAAI Conference 2012 Conference Paper

Generalizing and Executing Plans

• Christian Muise

AAMAS Conference 2012 Conference Paper

On Supervising Agents in Situation-Determined ConGolog

• Giuseppe De Giacomo
• Yves Lesp
• eacute; rance
• Christian Muise

We investigate agent supervision, a form of customization, which constrains the actions of an agent so as to enforce certain desired behavioral specifications. This is done in a setting based on the Situation Calculus and a variant of the ConGolog programming language which allows for nondeterminism, but requires the remainder of a program after the execution of an action to be determined by the resulting situation. Such programs can be fully characterized by the set of action sequences that they generate. Hence operations like intersection and difference become natural. The main results of the paper are a characterization of the maximally permissive supervisor that minimally constrains the agent so as to enforce the desired behavioral constraints when some agent actions are uncontrollable, and a sound and complete technique to execute the agent as constrained by such a supervisor.

IJCAI Conference 2011 Conference Paper

Monitoring the Execution of Partial-Order Plans via Regression

• Christian Muise
• Sheila A. McIlraith
• J. Christopher Beck

Partial-order plans (POPs) have the capacity to compactly represent numerous distinct plan linearizations and as a consequence are inherently robust. We exploit this robustness to do effective execution monitoring. We characterize the conditions under which a POP remains viable as the regression of the goal through the structure of a POP. We then develop a method for POP execution monitoring via a structured policy, expressed as an ordered algebraic decision diagram. The policy encompasses both state evaluation and action selection, enabling an agent to seamlessly switch between POP linearizations to accommodate unexpected changes during execution. We demonstrate the effectiveness of our approach by comparing it empirically and analytically to a standard technique for execution monitoring of sequential plans. On standard benchmark planning domains, our approach is 2 to 17 times faster and up to 2. 5 times more robust than comparable monitoring of a sequential plan. On POPs that have few ordering constraints among actions, our approach is significantly more robust, with the ability to continue executing in up to an exponential number of additional states.