A critical challenge in temporal planning is robustly dealing with non-determinism, e.g., the durational uncertainty of a robot's activity due to slippage or other unexpected influences. Recent advances show that robustness is a better measure of solution quality than traditional metrics such as flexibility. This paper introduces the Robust Execution Problem for finding maximally robust dispatch strategies for general probabilistic temporal planning problems. While generally intractable, we introduce approximate solution techniques — one that can be computed statically prior to the start of execution with robustness guarantees and one that dynamically adjusts to opportunities and setbacks during execution. We show empirically that our dynamic approach outperforms all known approaches in terms of execution success rate.

In this paper, we propose an approach to ensure the diagnosability of a partially controllable system. Given a model of correct and faulty behaviors of a partially observable discrete event system, equipped with a set of elementary actions that do not intertwine with autonomous events, we search a diagnosability plan, i.e., a sequence of applicable actions that leads the system from an initial belief state (a set of potentially current states) to a diagnosable belief state, in which the system is then left to run freely. This helps in reducing the diagnosis interaction with running systems and can be applied, e.g., on the output of a repair plan, like in power networks. The two successive stages of this approach keep diagnosability planning, including diagnosability tests, in PSpace in comparison to the Exptime test for the more complex active diagnosability used usually in such cases. For this, we propose to construct incrementally the twin plant structure of the given system and to exploit its parts already constructed while testing the candidate plans and constructing its next parts. This helps in pruning the twin plant constructions and many non-diagnosability plan tests. We have created a special benchmark and tested three proposed methods, according to the recycling level of twin plants construction, with one cost function used for plan optimality and an optional heuristics.

Branching story games have gained popularity for adapting to user actions within a story world. An active area of Interactive Narrative (IN) research uses automated planning to generate story plans as it can lighten the authorial burden of writing a branching story. Branches can be generated from a declarative representation rather than hand-crafted. A goal of an Experience Manager (EM) is to guide a user through a space of desirable narrative trajectories, or story branches, in an IN. However, in the cases when an EM must accommodate user actions and mediate them from a desired narrative trajectory to a new narrative trajectory, automated planning’s authorial advantage becomes a liability as the available narrative trajectories are not known apriori. This limitation can lead to the EM choosing a new narrative trajectory that is not coherent with the previous one and may result in a negative user experience. The goal of my research is to develop a problem formulation methodology for story planning problems that elicits the available narrative trajectories enabling an EM to execute more coherent accommodations.

Axioms can be used to model derived predicates in domain-independent planning models. Formulating models which use axioms can sometimes result in problems with much smaller search spaces than the original model. We propose a method for automatically extracting a particular class of axioms from standard STRIPS PDDL models. More specifically, we identify operators whose effects become irrelevant given some other operator, and generate axioms that capture this relationship. We show that this algorithm can be used to successfully extract axioms from standard IPC benchmark instances, and show that the extracted axioms can be used to significantly improve the performance of an IP-based planner.

Goal Recognition Design (GRD) is the problem of designing a domain in a way that will allow easy identification of agents' goals. This work extends the original GRD problem to the Plan Recognition Design (PRD) problem which is the task of designing a domain using plan libraries in order to facilitate fast identification of an agent's plan. While GRD can help to explain faster which goal the agent is trying to achieve, PRD can help in faster understanding of how the agent is going to achieve its goal. We define a new measure that quantifies the worst-case distinctiveness of a given planning domain, propose a method to reduce it in a given domain and show the reduction of this new measure in three domains from the literature.

Task allocation is ubiquitous in computer science and robotics, yet some problems have received limited attention in the computer science and AI community. Specifically, we will focus on multi-robot task allocation problems when tasks have time windows or ordering constraints. We will outline the main lines ofresearch and open problems.

Interaction between multiple agents requires some form of coordination and a level of mutual awareness. When computers and robots interact with people, they need to recognize human plans and react appropriately. Plan and goal recognition techniques have focused on identifying an agent's task given a sufficiently long action sequence. However, by the time the plan and/or goal are recognized, it may be too late for computing an interactive response. We propose an integration of planning with probabilistic recognition where each method uses intermediate results from the other as a guiding heuristic for recognition of the plan/goal in-progress as well as the interactive response. We show that, like the used recognition method, these interaction problems can be compiled into classical planning problems and solved using off-the-shelf methods. In addition to the methodology, this paper introduces problem categories for different forms of interaction, an evaluation metric for the benefits from the interaction, and extensions to the recognition algorithm that make its intermediate results more practical while the plan is in progress.

Robots operating in the real world must be able to handle both discrete and continuous change. Many robot behaviors can be controlled through numeric parameters (called control variables), which affect the rate of the continuous change. Previous approaches capable of reasoning efficiently with control variables impose severe restrictions that limit the expressivity of the problems that can be solved. A broad class of robotic applications require, for example, convex quadratic constraints on state variables and control variables that are jointly constrained and that affect multiple state variables simultaneously. However, extensions to prior approaches are not straightforward, since these characteristics are non-linear and hard to scale. We introduce cqScotty, a heuristic forward search planner that solves these problems efficiently. While naive formulations of consistency checks are not convex and do not scale, cqScotty uses an efficient convex formulation, in the form of a Second Order Cone Program (SOCP), that is very fast to solve. We demonstrate the scalability of our approach on three new realistic domains.

Cognitive agents operating in complex and dynamic domains benefit from significant goal management. Operations on goals include formulation, selection, change, monitoring and delegation in addition to goal achievement. Here we model these operations as transformations on goals. An agent may observe events that affect the agent’s ability to achieve its goals. Hence goal transformations allow unachievable goals to be converted into similar achievable goals. This paper examines an implementation of goal change within a cognitive architecture. We introduce goal transformation at the metacognitive level as well as goal transformation in an automated planner and discuss the costs and benefits of each approach. We evaluate goal change in the MIDCA architecture using a resource-restricted planning domain, demonstrating a performance benefit due to goal operations.

Embodied cognition is a theory stating that the processes and functions comprising the human mind are influenced by a person's physical body. Embodied musical cognition is a theory of the musical mind stating that the person's body largely influences his or her musical experiences and actions (such as performing, learning, or listening to music). In this work, a proof of concept demonstrating the utility of an embodied musical cognition for robotic musicianship is described. Though alternative theories attempting to explain human musical cognition exist (such as cognitivism and connectionism), this work contends that the integration of physical constraints and musical knowledge is vital for a robot in order to optimize note generating decisions based on limitations of sound generating motion and enable more engaging performance through increased coherence between the generated music and sound accompanying motion. Moreover, such a system allows for efficient and autonomous exploration of the relationship between music and physicality and the resulting music that is contingent on such a connection.