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.
Ma, Hang (University of Southern California) | Hönig, Wolfgang (University of Southern California) | Kumar, T. K. Satish (University of Southern California) | Ayanian, Nora (University of Southern California) | Koenig, Sven (University of Southern California)
The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities. This paper was published at AAAI 2019.
Shperberg, Shahaf S. (Ben-Gurion University of the Negev) | Felner, Ariel (Ben-Gurion University of the Negev) | Shimony, Solomon Eyal (Ben-Gurion University of the Negev) | Sturtevant, Nathan R. (University of Alberta) | Hayoun, Avi (Ben-Gurion University of the Negev)
Recent work in bidirectional heuristic search characterize pairs of nodes from which at least one node must be expanded in order to ensure optimality of solutions. We use these findings to propose a method for improving existing heuristics by propagating lower bounds between the forward and backward frontiers. We then define a number of desirable properties for bidirectional heuristic search algorithms, and show that applying the bound propagations adds these properties to many existing algorithms (e.g. to the MM family of algorithms). Finally, experimental results show that applying these propagations significantly reduce the running time of various algorithms.
Stern, Roni (Ben-Gurion University of the Negev) | Sturtevant, Nathan R. (University of Alberta) | Felner, Ariel (Ben-Gurion University of the Negev) | Koenig, Sven (University of Southern California) | Ma, Hang (University of Southern California) | Walker, Thayne T. (University of Denver) | Li, Jiaoyang (University of Southern California) | Atzmon, Dor (Ben Gurion University of the Negev) | Cohen, Liron (University of Southern California) | Kumar, T. K. Satish (University of Southern California) | Barták, Roman (Charles University) | Boyarski, Eli (Ben Gurion University of the Negev)
The multi-agent pathfinding problem (MAPF) is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses, autonomous vehicles, and robotics. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers assume different sets of assumptions, e.g., whether agents can traverse the same road at the same time, and have different objective functions, e.g., minimize makespan or sum of agents' actions costs. These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult for establishing appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. This paper aims to fill this gap and facilitate future research and practitioners by providing a unifying terminology for describing the common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks. In particular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms.
We present a novel search scheme for privacy-preserving multi-agent planning. Inspired by UCT search, the scheme is based on growing an asynchronous search tree by running repeated trials through the tree. We describe key differences to classical multi-agent forward search, discuss theoretical properties of the presented approach, and evaluate it based on benchmarks from the CoDMAP competition. As a secondary contribution, we describe a technique that extends the regular search approach by small explorative trials which are performed subsequent to each node expansion. We show that this technique significantly increases the number of problems solved for all algorithms considered, including MAFS.
Cohen, Liron (University of Southern California) | Uras, Tansel (University of Southern California) | Kumar, T. K. Satish (University of Southern California) | Koenig, Sven (University of Southern California)
Multi-Agent Motion Planning (MAMP) is the task of finding conflict-free kinodynamically feasible plans for agents from start to goal states. While MAMP is of significant practical importance, existing solvers are either incomplete, inefficient or rely on simplifying assumptions. For example, Multi-Agent Path Finding (MAPF) solvers conventionally assume discrete timesteps and rectilinear movement of agents between neighboring vertices of a graph. In this paper, we develop MAMP solvers that obviate these simplifying assumptions and yet generalize the core ideas of state-of-the-art MAPF solvers. Specifically, since different motions may take arbitrarily different durations, MAMP solvers need to efficiently reason with continuous time and arbitrary wait durations. To do so, we adapt (Enhanced) Conflict-Based Search to continuous time and develop a novel bounded-suboptimal extension of Safe Interval Path Planning, called Soft Conflict Interval Path Planning. On the theoretical side, we justify the completeness, optimality and bounded-suboptimality of our MAMP solvers. On the experimental side, we show that our MAMP solvers scale well with increasing suboptimality bounds.
Empirically, this optimization lead to 0.5 - 2.5% savings on expansions in our experiments A fundamental concern in real-time planning is the presence (Cserna, Gall, and Ruml 2019). of dead-ends in the state space, from which no goal is reachable. SafeRTS interleaves exploration and safety proofs during Providing real-time heuristic search algorithms that are its planning phase. As a direct consequence, it attempts complete in domains with dead-end states is a challenging safety proofs on nodes that become internal to the LSS by problem. Recently, the SafeRTS algorithm was proposed for the end of the search iteration. As shown in Cserna, Gall, and searching in such spaces (Cserna et al. 2018). SafeRTS exploits Ruml (2019), it would be equally or less difficult to achieve a user-provided predicate to identify safe states, from the same or better safety coverage by doing safety proofs after which a goal is likely reachable, and attempts to maintain a all the LSS expansions. SafeRTS has an anytime behavior backup plan for reaching a safe state at all times.
The travelling thief problem (TTP) is a combination of two interdependent NP-hard components: travelling salesman problem (TSP) and knapsack problem (KP). Existing approaches for TTP typically solve the TSP and KP components in an interleaved fashion, where the solution to one component is held fixed while the other component is changed. This indicates poor coordination between solving the two components and may lead to poor quality TTP solutions. For solving the TSP component, the 2-OPT segment reversing heuristic is often used for modifying the tour. We propose an extended and modified form of the reversing heuristic in order to concurrently consider both the TSP and KP components. Items deemed as less profitable and picked in cities earlier in the reversed segment are replaced by items that tend to be equally or more profitable and not picked in the later cities. Comparative evaluations on a broad range of benchmark TTP instances indicate that the proposed approach outperforms existing state-of-the-art TTP solvers.