The paper introduces mixed networks, a new framework for expressing and reasoning with probabilistic and deterministic information. The framework combines belief networks with constraint networks, defining the semantics and graphical representation. We also introduce the AND/OR search space for graphical models, and develop a new linear space search algorithm. This provides the basis for understanding the benefits of processing the constraint information separately, resulting in the pruning of the search space. When the constraint part is tractable or has a small number of solutions, using the mixed representation can be exponentially more effective than using pure belief networks which model constraints as conditional probability tables.

Macros have long been studied in AI planning [9, 18]. Many domain-dependent applications of macros have been exhibited and studied [15, 17, 12]; also, a number of domain-independent methods for learning, inferring, filtering, and applying macros have been the topic of research continuing up to the present [2, 7, 20]. In this paper, we present a domain-independent algorithm that computes macros in a novel way. Our algorithm computes macros "on-the-fly" for a given set of states and does not require previously learned or inferred information, nor does it need any prior domain knowledge. We exhibit the power of our algorithm by using it to define new domain-independent tractable classes of classical planning that strictly extend previously defined such classes [6], and can be proved to include Blocksworld-arm 1 and Towers of Hanoi. We believe that this is notable as theoretically defined, domainindependent tractable classes have generally struggled to incorporate construction-type domains such as these two. We hence give theoretically grounded evidence of the computational value of macros in planning.

Optimal plans of delete-free planning tasks are interesting both in domains that have no delete effects and as the relaxation heuristic h+ in general planning. Many heuristics for optimal and satisficing planning approximate the h+ heuristic, which is well-informed and admissible but intractable to compute. In this work, branch-and-bound and IDA* search are used in a search space tailored to delete-free planning together with an incrementally computed version of the LM-cut heuristic. The resulting algorithm for optimal delete-free planning exceeds the performance of A* with the LM-cut heuristic in the state-of-the-art planner Fast Downward.

The Liner Shipping Fleet Repositioning Problem (LSFRP) poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between services in a liner shipping network. The LSFRP is characterized by chains of interacting activities, many of which have costs that are a function of their duration; for example, sailing slowly between two ports is cheaper than sailing quickly. Despite its great industrial importance, the LSFRP has received little attention in the literature. We show how the LSFRP can be solved sub-optimally using the planner POPF and optimally with a mixed-integer program (MIP) and a novel method called Temporal Optimization Planning (TOP). We evaluate the performance of each of these techniques on a dataset of real-world instances from our industrial collaborator, and show that automated planning scales to the size of problems faced by industry.

Concept maps are frequently used in K-12 educational settings. The purpose of this study is to determine whether students’ performance on interactive concept map tasks in Guru, an intelligent tutoring system, is related to immediate and delayed learning outcomes. Guru is a dialogue-based system for high-school biology that intersperses concept map tasks within the tutorial dialogue. Results indicated that when students first attempt to complete concept maps, time spent on the maps may be a good indicator of their understanding, whereas the errors they make on their second attempts with the maps may be an indicator of the knowledge they are lacking.  This pattern of results was observed for one cycle of testing, but not replicated in a second cycle. Differences in the findings for the two testing cycles are most likely due to topic variations.

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.

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.

One of the consequences of the growth in AI research in South Africa in recent years is the establishment of a number of research hubs involved in AI activities ranging from mobile robotics and computational intelligence, to knowledge representation and reasoning, and human language technologies. In this survey we take the reader through a quick tour of the research being conducted at these hubs, and touch on an initiative to maintain and extend the current level of interest in AI research in the country.

Posters, the AAAI/SIGART Doctoral of AAAI; submit papers to the conference Consortium, and more!

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.