The paper illustrates a novel approach to conformant planning using classical planners. The approach relies on two core ideas developed to deal with incomplete information in the initial situation: the use of a classical planner to solve non-classical planning problems, and the reduction of the size of the initial belief state. Differently from previous uses of classical planners to solve non-classical planning problems, the approach proposed in this paper creates a valid plan from a possible plan---by inserting actions into the possible plan and maintaining only one level of non-deterministic choice (i.e., the initial plan being modified). The algorithm can be instantiated with different classical planners---the paper presents the GC[LAMA] implementation, whose classical planner is LAMA. We investigate properties of the approach, including conditions for completeness. GC[LAMA] is empirically evaluated against state-of-the-art conformant planners, using benchmarks from the literature. The experimental results show that GC[LAMA] is superior to other planners, in both performance and scalability. GC[LAMA] is the only planner that can solve the largest instances from several domains. The paper investigates the reasons behind the good performance and the challenges encountered in GC[LAMA].

Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.

This work presents an algorithm to provide a better represen- tation of space to artificially intelligent characters (i.e., agents or bots) in game and simulation environments by providing a more accurate breakdown of the traversable space present in the game environment. Such representations are generally constructed by decomposing the walkable space present in a game environment into a series of convex regions to form a data structure called a navigation mesh. We extend the basic concept of a navigation mesh by the introduction of an understanding of the textures that are attached to the underlying geometry creating what we refer to as a texture-aware navigation mesh. This does result in a more complex navigation mesh (more regions and a larger search space). However, since the textures of walkable geometry can be used to determine the appropriate traversal method for that terrain, a game character can determine valid paths for their traversal methods using just the navigation mesh (e.g., characters in cars can generate paths containing just roads or walking characters can create paths containing just sidewalks). We also present a use case that shows how such a system of texture aware naviga- tion meshes might benefit character path planning and search in virtual environments. In this use case, we examine a Real Time Strategy game style game environment, which shows it is possible to generate a navigation mesh such that each region is composed of a single terrain type.

This paper deals with planning domains that appear in computer games, especially when modeling intelligent virtual agents. Some of these domains contain only actions with no negative effects and are thus treated as easy from the planning perspective. We propose two new techniques to solve the problems in these planning domains, a heuristic search algorithm ANA* and a constraint-based planner RelaxPlan, and we compare them with the state-of-the-art planners, that were successful in IPC, using planning domains motivated by computer games.

Automated planning is a well studied research topic thanks to its wide range of real-world applications. Despite significant progress in this area many planning problems still remain hard and challenging. Some techniques such as learning macro-operators improve the planning process by reformulating the (original) planning problem. While many encouraging practical results have been derived from such reformulation methods, little attention has been paid to the theoretical properties of reformulation such as soundness, completeness, and algorithmic complexity. In this paper we build up a theoretical framework describing reformulation schemes such as action elimination or creating macro-actions. Using this framework, we show that finding entanglements (relationships useful for action elimination) is as hard as planning itself. Moreover, we design a tractable algorithm for checking under what conditions it is safe to reformulate a problem by removing primitive operators (assembled to a macro-operator).

Markov logic networks have been successfully applied to many problems in AI. However, the computational complexity of the inference procedures has limited their application. Previous work in lifted inference, lazy inference and cutting plane inference has identified cases where the entire ground network need not be constructed. These approaches are specific to particular inference procedures, and apply well only to certain classes of problems. We introduce a method of focused grounding that can use either general purpose or domain specific heuristics to produce only the most relevant ground formulas. Though a solution to the focused grounding is not, in general, a solution to the complete grounding, we show empirically that the smaller search space of a focused grounding makes it easier to locate a good solution. We evaluate focused grounding on two diverse domains, joint entity resolution and abductive plan recognition. We show improved results and decreased computation cost for the entity resolution domain relative to a complete grounding. Focused grounding in abductive plan recognition produces state of the art results in a domain where complete grounding proved intractable.

In this paper, we introduce an admissible heuristic for hybrid planning with preferences. Hybrid planning is the fusion of hierarchical task network (HTN) planning with partial order causal link (POCL) planning. We consider preferences to be soft goals - facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. Our heuristic estimates the best quality of any solution that can be developed from the current plan under consideration. It can thus be used by any branch-and-bound algorithm that performs search in the space of plans to prune suboptimal plans from the search space.

This paper suggests and supports a design idea for improving dynamical navigation: adding an intermediary, adaptive obstacle representation level between perception and repeller representations. We illustrate our idea with our specific example of an adaptive obstacle representation level, which cleanly integrates into multiple existing navigation systems, treating each perceived obstacle entity as a locally sensitive, obstacle-valued function that returns an obstacle representation upon which steering and obstacle avoidance are based. Moreover, other elements of the navigation systems remain unaltered, thus preserving and extending original design virtues such as behavioral flexibility, computational efficiency, and dynamic responsiveness. Extensive simulations, validated with tests of real robots, demonstrate that our new representations compare favorably to previously employed representations on measures of effectiveness within a tested scenario, robustness over varying scenarios and ranges of parameter values, and computational efficiency.

In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.

The AAAI-11 workshop program was held Sunday and Monday, August 7–18, 2011, at the Hyatt Regency San Francisco in San Francisco, California USA. The AAAI-11 workshop program included 15 workshops covering a wide range of topics in artificial intelligence. The titles of the workshops were Activity Context Representation: Techniques and Languages; Analyzing Microtext; Applied Adversarial Reasoning and Risk Modeling; Artificial Intelligence and Smarter Living: The Conquest of Complexity; AI for Data Center Management and Cloud Computing; Automated Action Planning for Autonomous Mobile Robots; Computational Models of Natural Argument; Generalized Planning; Human Computation; Human-Robot Interaction in Elder Care; Interactive Decision Theory and Game Theory; Language-Action Tools for Cognitive Artificial Agents: Integrating Vision, Action and Language; Lifelong Learning; Plan, Activity, and Intent Recognition; and Scalable Integration of Analytics and Visualization. This article presents short summaries of those events.