Constructing a strong heuristic function is a central problem in heuristic search. A common approach is to combine a number of heuristics by maximizing over the values from each. If a limit is placed on this number, then a subset selection problem arises. We treat this as an optimization problem, and proceed by translating a natural loss function into a submodular and monotonic utility function under which greedy selection is guaranteed to be near-optimal. We then extend this approach with a sampling scheme that retains provable optimality. Our empirical results show large improvements over existing methods, and give new insight into building heuristics for directed domains.

CSP solvers usually search a partial assignment search tree.We present a new formalization for CSP solvers, which spansa conceptually different search tree, where each node representssubsets of the original domains for the variables. We experimentwith a simple backtracking algorithm for this searchtree and show that it outperforms a simple backtracking algorithmon the traditional search tree in many cases.

The AAAI-12 Workshop program was held Sunday and Monday, July 22–23, 2012 at the Sheraton Centre Toronto Hotel in Toronto, Ontario, Canada. The AAAI-12 workshop program included 9 workshops covering a wide range of topics in artificial intelligence. The titles of the workshops were Activity Context Representation: Techniques and Languages, AI for Data Center Management and Cloud Computing, Cognitive Robotics, Grounding Language for Physical Systems, Human Computation, Intelligent Techniques for Web Personalization and Recommendation, Multiagent Pathfinding, Neural-Symbolic Learning and Reasoning, Problem Solving Using Classical Planners, Semantic Cities. This article presents short summaries of those events.

A* is often described as being `optimal', in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. n is re-inserted into the OPEN list, but with the f-cost of the next best child. This paper introduces an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* generates only the children with the same f-cost as the parent. EPEA* is generalized to its iterative-deepening variant, EPE-IDA*. For some domains, these algorithms yield substantial performance improvements. State-of-the-art results were obtained for the pancake puzzle and for some multi-agent pathfinding instances. Drawbacks of EPEA* are also discussed.

In the multi agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

In the multi agent path finding problem (MAPF) paths shouldbe found for several agents, each with a different start andgoal position such that agents do not collide. Previous optimalsolvers applied global A*-based searches. We presenta new search algorithm called Conflict Based Search (CBS).CBS is a two-level algorithm. At the high level, a search isperformed on a tree based on conflicts between agents. At thelow level, a search is performed only for a single agent at atime. In many cases this reformulation enables CBS to examinefewer states than A* while still maintaining optimality.We analyze CBS and show its benefits and drawbacks. Experimentalresults on various problems shows a speedup ofup to a full order of magnitude over previous approaches.

The Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment was held from October 11–14, 2011, on the campus of Stanford University near Palo Alto, California. This report summarizes the conference and related activities.

This report summarizes the conference and related activities. For the first time in AIIDE's history, the main program of the conference was preceded by three workshops: Intelligent Narrative Technologies workshop, the workshop on Nonplayer Character AI, and the Artificial Intelligence in the Game Design Process workshop. All three attracted a substantial audience and led to exciting debates and fruitful discussions (figure 1). In total, 24 papers were presented in the three workshops. The Intelligent Narrative Technologies workshop included papers on story representation, dialogue generation, narrative visualization, and authoring interfaces for interactive narrative, and a panel on corpus-based approaches to modeling narrative.

This demonstration describes ScriptEase II, a tool that allows game story authors to generate scripts that control objects in video games by manipulating high level story patterns and game objects. ScriptEase II can generate scripting code for any game engine for which a translator is written. Currently there are translators for Neverwinter Nights and real Pinball games.