The theme of IJCAI-09 is "The Interdisciplinary Reach of Artificial Intelligence," with a focus on the broad impact of artificial intelligence on science, engineering, medicine, social sciences, arts, and humanities. The conference will include invited talks, workshops, tutorials, and other events dedicated to this theme.
The Twenty-Third Innovative Applications of Artificial Intelligence Conference (IAAI-11) will be held in San Francisco, California at the Hyatt Regency San Francisco, from August 9–11, 2011, USA. The proceedings will be published by AAAI Press. This site only contains the published proceedings of the conference. For information about the conference in general, please see the conference website.
The Twenty-Fourth Innovative Applications of Artificial Intelligence conference (IAAI 2012) will be held in Toronto, Ontario, Canada, July 22–26 2012. The proceedings will be published by AAAI Press. This site only contains the published proceedings of the conference. For information about the conference in general, please see the conference website.
An influence diagram is a graphical representation of sequential decision-making under uncertainty, defining a structured decision problem by conditional probability functions and additive utility functions over discrete state and action variables. The task of finding the maximum expected utility of influence diagrams is closely related to the cost-optimal probabilistic planning, stochastic programmings, or model-based reinforcement learning. In this position paper, we address the heuristic search for solving influence diagram, where we generate admissible heuristic functions from graph decomposition schemes. Then, we demonstrate how such heuristics can guide an AND/OR branch and bound search. Finally, we briefly discuss the future directions for improving the quality of heuristic functions and search strategies.
Belov, Gleb (Monash University) | Du, Wenbo (Australian National University) | Banda, Maria Garcia De La (Monash University) | Harabor, Daniel ( Monash University ) | Koenig, Sven (University of Southern California) | Wei, Xinrui (Monash University)
The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal positions in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance in automated warehousing (such as those operated by Amazon) and in other contemporary application areas. In this paper, we demonstrate that some recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on real-world PR instances. This opens up a new direction of industrial relevance for the MAPF research community.
The combinatorial problems that constraint programming typically solves belong to the class of NP-hard problems. The AI planning community focuses on even harder problems: for example, classical planning is PSPACE-hard. A natural and well-known constraint programming approach to classical planning solves a succession of fixed plan-length problems, but with limited success. We revisit this approach in light of recent progress on general-purpose branching heuristics. We conduct an empirical comparison of our proposal against state-of-the-art planners.
Multi-Agent Path Finding (MAPF) deals with the problem of finding collision-free paths for a set of agents, where each agent wants to move from its start location to its goal location on a shared graph. The paper addresses the question of how to model MAPF as a classical planning problem, specifically, how to encode various collision constraints. Several models in the PDDL modeling language are proposed and empirically compared.
Ulloa, Carlos Hernández (Universidad Andrés Bello) | Yeoh, William (Washington University in St. Louis) | Baier, Jorge A. (Pontificia Universidad Católica de Chile) | Suazo, Luis (Universidad Andrés Bello) | Zhang, Han (University of Southern California) | Koenig, Sven (University of Southern California)
Many interesting search problems can be formulated as bi-objective search problems; for example, transportation problems where both travel distance and time need to be minimized. Multi-objective best-ﬁrst search algorithms need to maintain the set of undominated paths from the start state to each state to compute a set of paths from a given start state to a given goal state (the Pareto-optimal solutions) such that no path in the set is dominated by another path in the set. Each time they ﬁnd a new path to a state n, they perform a dominance check to determine whether such a path dominates any of the previously found paths to n. Existing algorithms do not perform these checks efﬁciently, requiring at least a full iteration over the Open list per check. In this paper, we present the ﬁrst multi-objective algorithm that performs these checks efﬁciently. Indeed, Bi-Objective A* (BOA*)—our algorithm—requires constant time to check for dominance. Our experimental evaluation shows that BOA*is orders-of-magnitude faster than state-of-the-art search algorithms, such as NAMOA*, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.
The travelling thief problem (TTP) is a multi-component optimisation problem involving two interdependent NP-hard components: the travelling salesman problem (TSP) and the knapsack problem (KP). Recent state-of-the-art TTP solvers modify the underlying TSP and KP solutions in an iterative and interleaved fashion. The TSP solution (cyclic tour) is typically changed in a deterministic way, while changes to the KP solution typically involve a random search, effectively resulting in a quasi-meandering exploration of the TTP solution space. Once a plateau is reached, the iterative search of the TTP solution space is restarted by using a new initial TSP tour. We propose to make the search more efficient though an adaptive surrogate model (based on a customised form of Support Vector Regression) that learns the characteristics of initial TSP tours that lead to good TTP solutions. The model is used to filter out non-promising initial TSP tours, in effect reducing the amount of time spent to find a good TTP solution. Experiments on a broad range of benchmark TTP instances indicate that the proposed approach filters out a considerable number of non-promising initial tours, at the cost of missing only a small number of the best TTP solutions.
Atzmon, Dor (Ben-Gurion University) | Li, Jiaoyang (University of Southern California) | Felner, Ariel (Ben-Gurion University) | Nachmani, Eliran (Ben-Gurion University) | Shperberg, Shahaf (Ben-Gurion University) | Sturtevant, Nathan (University of Alberta) | Koenig, Sven (University of Southern California)
In the Multi-Agent Meeting (MAM) problem, the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding optimal meeting locations for multiple agents. A number of admissible heuristics are proposed and experiments demonstrate the benefits of MM*.