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.
We propose an exact algorithm for solving the longest path problem between two given vertices in undirected weighted graphs. By using graph partitioning and dynamic programming, we obtain an algorithm that is significantly faster than other state-of-the-art methods. This enables us to solve instances that were previously unsolved and solve hard instances significantly faster. We also present a parallel version of the algorithm.
PLRTA* conflates all states that differ only in time into a single abstract state. Abstract states inherit the union of all In dynamic environments such as cities, agents often do not the predecessors of their preimage states, so that backups have time to find a complete plan to reach a goal state. Planning can be performed properly. PLRTA* learns a single static in such environment requires an agent to update its plan heuristic value for each abstract state. For dynamic learning, frequently to respond to the changes around it. The setting PLRTA* performs the standard Dijkstra-style backup across of real-time heuristic search models online planning by requiring the LSS, considering only costs arising from the dynamic elements the agent to commit to its next action within a strict of the environment. As presented by Cannon, Rose, time limit. The time bound for planning is set to the time and Ruml (2014), the algorithm commits to only one step at which the actions to which the agent has already committed along the selected path, and then replans using updated information.
In a multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. Guaranteeing that collisions will never occur may be impossible. An important task is to find a plan that is very likely to succeed, even though unexpected delays may occur. We propose an algorithm for finding a plan in which the probability that no collisions will occur is at least a given parameter p (p-robust plan). We show that finding an optimal p-robust plan is significantly more difficult than finding an optimal standard plan. As a practical solution, we propose a greedy algorithm based on the Conflict-Based Search framework. Our experiments show that it finds p-robust plans with cost that is relatively close to the optimal cost of the standard, non-robust plans.
Multi-agent pathfinding is the problem of finding a non-interfering paths for a set of agents, such that if the agents follow these paths then each agent will reach its desired destination. Recent years have shown tremendous advances in this field, with optimal and suboptimal algorithms that are able to plan paths for over 100 agents in reasonable time. However, autonomous mobile agents are prime targets for cyber-security attacks, where an adversary may take control over an agent to disrupt the agents execution of their plan. This threat raises two questions. The first question is how much damage can an agent do if it does not follow its plan. The second question is how can one plan a-priori to be as robust as possible to such cyber-attacks. In this work, We provide an answer to both questions. To compute the maximal amount of damage that an adversary agent can do, we define a corresponding graph search problem and solve this problem with A*. Then, we provide a very simple method to choose a solution that is robust to such damages. We demonstrate both algorithms in simulation over standard multi-agent pathfinding domains.
In this paper, we study a problem from the realm of multi-criteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S' with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S'. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.
Li, Jiaoyang (University of Southern California) | Boyarski, Eli (Ben-Gurion University of the Negev) | Felner, Ariel (Ben-Gurion University of the Negev) | Ma, Hang (University of Southern California) | Koenig, Sven (University of Southern California)
Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Pathfinding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependency between agents. Empirically, CBS with both new heuristics significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50, yielding a new state-of-the-art CBS-based algorithm.
Nguyen, Van (New Mexico State University) | Obermeier, Philipp (University of Postdam) | Son, Tran Cao (New Mexico State University) | Schaub, Torsten (Washington University in St. Louis) | Yeoh, William (Washington University in St. Louis)
In Multi-Agent Path Finding (MAPF), a team of agents needs to find collision-free paths from their starting locations to their respective targets. Combined Target Assignment and Path Finding (TAPF) extends MAPF by including the problem of assigning targets to agents as a precursor to the MAPF problem. A limitation of both models is their assumption that the number of agents and targets are equal, which is invalid in some applications. We address this limitation by generalizing TAPF to allow for (1) unequal number of agents and tasks; (2) tasks to have deadlines by which they must be completed; (3) ordering of groups of tasks to be completed; and (4) tasks that are composed of a sequence of checkpoints that must be visited in a specific order. Further, we model the problem using answer set programming (ASP) to show that customizing the desired variant of the problem is simple -- one only needs to choose the appropriate combination of ASP rules to enforce it. We also demonstrate experimentally that if problem specific information can be incorporated into the ASP encoding then ASP based methods can be efficient and can scale up to solve practical applications.