This paper investigates methods for training parameterized functions for guiding state-space search algorithms. Existing work commonly generates data for training such guiding functions by solving problem instances while leveraging the current version of the guiding function. As a result, as training progresses, the guided search algorithm can solve more difficult instances that are, in turn, used to further train the guiding function. These methods assume that a set of problem instances of varied difficulty is provided. Since previous work was not designed to distinguish the instances that the search algorithm can solve from those that cannot be solved with the current guiding function, the algorithm commonly wastes time attempting and failing to solve many of these instances. In this paper, we improve upon these training methods by generating a curriculum for learning the guiding function that directly addresses this issue. Namely, we propose and evaluate a Teacher-Student Curriculum (TSC) approach where the teacher is an evolutionary strategy that attempts to generate problem instances of ``correct difficulty'' and the student is a guided search algorithm utilizing the current guiding function. The student attempts to solve the problem instances generated by the teacher. We conclude with experiments demonstrating that TSC outperforms the current state-of-the-art Bootstrap Learning method in three representative benchmark domains and three guided search algorithms, with respect to the time required to solve all instances of the test set.

We address the following mechanism design problem: Given a multi-player Normal-Form Game (NFG) with a continuous action space, find a non-discriminatory (i.e., identical for all players) restriction of the action space which maximizes the resulting Nash Equilibrium with respect to a fixed social utility function. First, we propose a formal model of a Restricted Game and the corresponding restriction optimization problem. We then present an algorithm to find optimal non-discriminatory restrictions under some assumptions. Our experimental results with Braess' Paradox and the Cournot Game show that this method leads to an optimized social utility of the Nash Equilibria, even when the assumptions are not guaranteed to hold. Finally, we outline a generalization of our approach to the much wider scope of Stochastic Games.

Traffic is the pulse of the city. Transportation systems can involve humans, vehicles, shipments, information technology, and the physical infrastructure, all interacting in complex ways. Intelligent transportation enables the city to function in a more efficient and effective way. A wide range of city data become increasingly available, such as taxi trips, surveillance camera data, human mobility data from mobile phones or location-based services, events from social media, car accident reports, bike-sharing information, Points-Of-Interest, traffic sensors, public transportation data, and many more. This abundance of data poses a grand challenge to the CIKM research community: How to utilize such data toward city intelligence, across various transportation tasks? The 3rd workshop of "Data-driven Intelligent Transportation" welcomes articles and presentations in the areas of transportation systems, data mining, and artificial intelligence, conveying new advances and developments in theory, modeling, simulation, testing, case studies, as well as large-scale deployment.

In this work, we examine a line of recent publications that propose to use deep neural networks to approximate the goal distances of states for heuristic search. We present a first step toward showing that this work suffers from inherent scalability limitations since --- under the assumption that P≠NP --- such approaches require network sizes that scale exponentially in the number of states to achieve the necessary (high) approximation accuracy.

This paper presents a novel embedding protocol that allows for safe and efficient operation of the Hybrid Autonomous Intersection Management (H-AIM) protocol concurrently with actuated and adaptive signal controllers. The proposed protocol extends H-AIM to allow it to cope with some operational uncertainty that is common in actuated signal controllers. A novel approach for computing safety bounds on signal timing is presented as a way of insuring safety in the face of demand uncertainty. Experimental results show the feasibility and effectiveness of combining H-AIM with actuated controllers for various levels of connected and autonomous vehicle (CAV) market penetration and different combinations of common signal control schemes, namely, adaptive signal timing, fixed signal timing, and signal actuation. The benefits are presented in terms of delay improvement when common actuation protocols are used in conjunction with the H-AIM protocol. In contrast to previous reports, the results presented in this paper suggest that mixtures of turning movement assignments that are more permissive for CAVs and less permissive for human operated vehicles are often detrimental in terms of traffic delay. Nonetheless, when implemented on top of an actuated and adaptive controller, the extended H-AIM protocol is shown to never be detrimental while presenting statistically significant reductions in total delay when more than 15% of the traffic is composed of CAVs.

This paper reviews current AI solutions towards road traffic congestion alleviation. Three specific AI technologies are discussed, (1) intersection management protocols for coordinating vehicles through a roads intersection in a safe and efficient manner, (2) road pricing protocol that induce optimized traffic flow, and (3) partial or full autonomous driving that can stabilize traffic flow and mitigate adverse traffic shock waves. The paper briefly presents the challenges affiliated with each of these applications along with an overview of state-of-the-art solutions. Finally, real-world implementation gaps and challenges are discussed.

In various control task domains, existing controllers provide a baseline level of performance that—though possibly suboptimal—should be maintained. Reinforcement learning (RL) algorithms that rely on extensive exploration of the state and action space can be used to optimize a control policy. However, fully exploratory RL algorithms may decrease performance below a baseline level during training. In this paper, we address the issue of online optimization of a control policy while minimizing regret with respect to a baseline policy performance. We present a joint imitation-reinforcement learning framework, denoted JIRL. The learning process in JIRL assumes the availability of a baseline policy and is designed with two objectives in mind (a) training while leveraging demonstrations from the baseline policy to minimize regret with respect to the baseline policy, and (b) eventually surpassing the baseline performance. JIRL addresses these objectives by initially learning to imitate the baseline policy and gradually shifting control from the baseline to an RL agent. Experimental results show that JIRL effectively accomplishes the aforementioned objectives in several, continuous action-space domains. The results demonstrate that JIRL is comparable to a state-of-the-art algorithm in its final performance while incurring significantly lower baseline regret during training. Moreover, the results show a reduction factor of up to 21 in baseline regret over a trust-region-based approach that guarantees monotonic policy improvement.

The year 2020 saw the covid-19 virus lead to one of the worst global pandemics in history. As a result, governments around the world have been faced with the challenge of protecting public health while keeping the economy running to the greatest extent possible. Epidemiological models provide insight into the spread of these types of diseases and predict the effects of possible intervention policies. However, to date, even the most data-driven intervention policies rely on heuristics. In this paper, we study how reinforcement learning (RL) and Bayesian inference can be used to optimize mitigation policies that minimize economic impact without overwhelming hospital capacity. Our main contributions are (1) a novel agent-based pandemic simulator which, unlike traditional models, is able to model fine-grained interactions among people at specific locations in a community; (2) an RLbased methodology for optimizing fine-grained mitigation policies within this simulator; and (3) a Hidden Markov Model for predicting infected individuals based on partial observations regarding test results, presence of symptoms, and past physical contacts. This article is part of the special track on AI and COVID-19.

This paper examines the impact of tolls on social welfare in the context of a transportation network in which only a portion of the agents are subject to tolls. More specifically, this paper addresses the question: which subset of agents provides the most system benefit if they are compliant with an approximate marginal cost tolling scheme? Since previous work suggests this problem is NP-hard, we examine a heuristic approach. Our experimental results on three real-world traffic scenarios suggest that evaluating the marginal impact of a given agent serves as a particularly strong heuristic for selecting an agent to be compliant. Results from using this heuristic for selecting 7.6% of the agents to be compliant achieved an increase of up to 10.9% in social welfare over not tolling at all. The presented heuristic approach and conclusions can help practitioners target specific agents to participate in an opt-in tolling scheme.

To alleviate traffic congestion in urban areas, electronic toll collection (ETC) systems are deployed all over the world. Despite the merits, tolls are usually pre-determined and fixed from day to day, which fail to consider traffic dynamics and thus have limited regulation effect when traffic conditions are abnormal. In this paper, we propose a novel dynamic ETC (DyETC) scheme which adjusts tolls to traffic conditions in realtime. The DyETC problem is formulated as a Markov decision process (MDP), the solution of which is very challenging due to its 1) multi-dimensional state space, 2) multi-dimensional, continuous and bounded action space, and 3) time-dependent state and action values. Due to the complexity of the formulated MDP, existing methods cannot be applied to our problem. Therefore, we develop a novel algorithm, PG-beta, which makes three improvements to traditional policy gradient method by proposing 1) time-dependent value and policy functions, 2) Beta distribution policy function and 3) state abstraction. Experimental results show that, compared with existing ETC schemes, DyETC increases traffic volume by around 8%, and reduces travel time by around 14:6% during rush hour. Considering the total traffic volume in a traffic network, this contributes to a substantial increase to social welfare.

This paper focuses on two commonly used path assignment policies for agents traversing a congested network: self-interested routing, and system-optimum routing. In the self-interested routing policy each agent selects a path that optimizes its own utility, while in the system-optimum routing, agents are assigned paths with the goal of maximizing system performance. This paper considers a scenario where a centralized network manager wishes to optimize utilities over all agents, i.e., implement a system-optimum routing policy. In many real-life scenarios, however, the system manager is unable to influence the route assignment of all agents due to limited influence on route choice decisions. Motivated by such scenarios, a computationally tractable method is presented that computes the minimal amount of agents that the system manager needs to influence (compliant agents) in order to achieve system optimal performance. Moreover, this methodology can also determine whether a given set of compliant agents is sufficient to achieve system optimum and compute the optimal route assignment for the compliant agents to do so. Experimental results are presented showing that in several large-scale, realistic traffic networks optimal flow can be achieved with as low as 13% of the agent being compliant and up to 54%.

Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.

We present MM, the first bidirectional heuristic search algorithm whose forward and backward searches are guaranteed to ''meet in the middle'', i.e. never expand a node beyond the solution midpoint. We also present a novel framework for comparing MM, A*, and brute-force search, and identify conditions favoring each algorithm. Finally, we present experimental results that support our theoretical analysis.

We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robot-routing problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for flowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multi-agent path-finding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a flow-based ILP formulation and an adaptation of conflict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances.

Bidirectional search algorithms interleave a search forward from the start state (start ) and a search backward (i.e. using reverse operators) from the goal state (goal). We say that the two searches “meet in the middle” if neither search expands a node whose g-value (in the given direction) exceeds C*/2 , where C* is the cost of an optimal solution. The only bidirectional heuristic search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM’s priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe’s correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.

This paper proposes a mapping between multi-agent pathfinding (MAPF) and combinatorial auctions (CAs). In MAPF, agents need to reach their goal destinations without colliding. Algorithms for solving MAPF aim at assigning agents non-conflicting paths that minimize agents' travel costs. In CA problems, agents bid over bundles of items they desire. Auction mechanisms aim at finding an allocation of bundles that maximizes social welfare. In the proposed mapping of MAPF to CAs, agents bid on paths to their goals and the auction allocates non-colliding paths to the agents. Using this formulation, auction mechanisms can be naturally used to solve a range of MAPF problem variants. In particular, auction mechanisms can be applied to non-cooperative settings with self-interested agents while providing optimality guarantees and robustness to manipulations by agents. The paper further shows how to efficiently implement an auction mechanism for MAPF, utilizing methods and representations from both the MAPF and CA literatures.

The multi-agent path finding (MAPF) problem is a generalization of the single-agent path finding problem for k > 1 agents. It consists of a graph and a number of agents. Foreach agent, a unique start state and a unique goal state are given, the task is to find paths for all agents from their start states to their goal states, under the constraint that agents cannot collide during their movements. In many cases there is an additional goal of minimizing a cumulative cost function such as the sum of the time steps required for every agent to reach its goal. The goal of my research is providing new methods to solve MAPF optimally and provide theoretical understandings that will help choose the best solver given a problem instance.

Conflict-Based Search (CBS) and its generalization, Meta-Agent CBS are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces ICBS, an improved version of CBS. ICBS incorporates three orthogonal improvements to CBS which are systematically described and studied. Experimental results show that each of these improvements reduces the runtime over basic CBS by up to 20x in many cases. When all three improvements are combined, an even larger improvement is achieved, producing state-ofthe art results for a number of domains.

The traditional approach for solving Constraint satisfaction Problems (CSPs) is searching the Assignment Space in which each state represents an assignment to some variables. This paper suggests a new search space formalization for CSPs, the Partial Domain Search Tree (PDST). In each PDST node aunique subset of the original domain is considered, values are excluded from the domains in each node to insure that a given set of constraints is satisfied. We provide theoretical analysis of this new approach showing that searching the PDST is beneficial for loosely constrained problems. Experimental results show that this new formalization is a promising direction for future research. In some cases searching the PDST outperforms the traditional approach by an order of magnitude. Furthermore, PDST can enhance Local Search techniques resulting in solutions that violate up to 30% less constraints.

In the Real-Time Agent-Centered Search (RTACS) problem,an agent has to arrive at a goal location while acting and reasoningin the physical world. Traditionally, RTACS problemsare solved by propagating and updating heuristic values ofstates visited by the agent. In existing RTACS algorithms theagent may revisit each state many times causing the entireprocedure to be quadratic in the state space. We study theIterative Deepening (ID) approach for solving RTACS andintroduce Exponential Deepening A* (EDA*), an RTACS algorithmwhere the threshold between successive Depth-Firstcalls is increased exponentially. EDA* is proven to hold aworst case bound that is linear in the state space. Experimentalresults supporting this bound are presented and demonstrateup to 10x reduction over existing RTACS solvers wrtdistance traveled, states expanded and CPU runtime.

The task in the multi-agent path finding problem (MAPF) is to find paths for multiple agents, each with a different start and goal position, such that agents do not collide. A successful optimal MAPF solver is the conflict-based search (CBS) algorithm. CBS is a two level algorithm where special conditions ensure it returns the optimal solution. Solving MAPF optimally is proven to be NP-hard, hence CBS and all other optimal solvers do not scale up. We propose several ways to relax the optimality conditions of CBS trading solution quality for runtime as well as bounded-suboptimal variants, where the returned solution is guaranteed to be within a constant factor from optimal solution cost. Experimental results show the benefits of our new approach; a massive reduction in running time is presented while sacrificing a minor loss in solution quality. Our new algorithms outperform other existing algorithms in most of the cases.

The task in the multi-agent path finding problem (MAPF) is to find paths for multiple agents, each with a different start and goal position, such that agents do not collide. A successful optimal MAPF solver is the conflict-based search (CBS) algorithm. CBS is a two level algorithm where special conditions ensure it returns the optimal solution. Solving MAPF optimally is proven to be NP-hard, hence CBS and all other optimal solvers do not scale up. We propose several ways to relax the optimality conditions of CBS trading solution quality for runtime as well as bounded-suboptimal variants, where the returned solution is guaranteed to be within a constant factor from optimal solution cost. Experimental results show the benefits of our new approach; a massive reduction in running time is presented while sacrificing a minor loss in solution quality. Our new algorithms outperform other existing algorithms in most of the cases.

This paper introduces Exponential Deepening A* (EDA*), an Iterative Deepening (ID) algorithm where the threshold between successive Depth-First calls is increased exponentially. EDA* can be viewed as a Real-Time Agent-Centered (RTACS) algorithm. Unlike most existing RTACS algorithms, EDA* is proven to hold a worst case bound that is linear in the state space. Experimental results demonstrate up to 5x reduction over existing RTACS solvers wrt distance traveled, states expanded and CPU runtime. A full version of this paper appears in AAAI-14.

When solving instances of problem domains that feature a large branching factor, A* may generate a large number of nodes whose cost is greater than the cost of the optimal solution. We designate such nodes as surplus. Generating surplus nodes and adding them to the OPEN list may dominate both time and memory of the search. A recently introduced variant of A* called Partial Expansion A* (PEA*) deals with the memory aspect of this problem. When expanding a node n, PEA* generates all of its children and puts into OPEN only the children with f = f (n). n is re-inserted in the OPEN list with the f -cost of the best discarded child. This guarantees that surplus nodes are not inserted into OPEN. In this paper, we present a novel variant of A* called Enhanced Partial Expansion A* (EPEA*) that advances the idea of PEA* to address the time aspect. Given a priori domain- and heuristic- specific knowledge, EPEA* generates only the nodes with f = f(n). Although EPEA* is not always applicable or practical, we study several variants of EPEA*, which make it applicable to a large number of domains and heuristics. In particular, the ideas of EPEA* are applicable to IDA* and to the domains where pattern databases are traditionally used. Experimental studies show significant improvements in run-time and memory performance for several standard benchmark applications. We provide several theoretical studies to facilitate an understanding of the new algorithm.

In this paper we introduce techniques for state pruning atruntime in a priori unknown domains. We describe how toidentify states that can be deleted from the state-space whenlooking for both optimal and suboptimal solutions. We discussgeneral graphs and special cases like 8-connected grids.Experimental results show a speed up of up to an order ofmagnitude when applying our techniques on real-time agentcenteredsearch problems.

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.

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* (PEA*) 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. We introduce an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* only generates the children with the same f-cost as the parent. State-of-the-art results were obtained for a number of domains. Drawbacks of EPEA* are also discussed. A full version of this paper appears in the proceedings of AAAI-2012

The task in the multi-agent path finding problem (MAPF) isto find paths for multiple agents, each with a different startand goal position, such that agents do not collide. It is possibleto solve this problem optimally with algorithms that arebased on the A* algorithm. Recently, we proposed an alternativealgorithm called Conflict-Based Search (CBS) (Sharonet al. 2012), which was shown to outperform the A*-basedalgorithms in some cases. CBS is a two-level algorithm. Atthe high level, a search is performed on a tree based on conflictsbetween agents. At the low level, a search is performedonly for a single agent at a time. While in some cases CBSis very efficient, in other cases it is worse than A*-based algorithms.This paper focuses on the latter case by generalizingCBS to Meta-Agent CBS (MA-CBS). The main idea isto couple groups of agents into meta-agents if the number ofinternal conflicts between them exceeds a given bound. MACBSacts as a framework that can run on top of any completeMAPF solver. We analyze our new approach and provideexperimental results demonstrating that it outperforms basicCBS and other A*-based optimal solvers in many cases.

We present a new two-level search algorithm for optimal multi-agent path finding called Conflict Based Search (CBS). 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. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm that finds optimal solutions. We analyze this new formalization and compare it to the previous state-of-the-art A*-based approach. Experimental results on various domains show the benefits and drawbacks of this approach. A speedup of up to 3 orders of magnitude was obtained in a number of cases.

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. In Sharon et. al. (2011), we introduced a novel two-level search algorithm framework for this problem. The high-level searches a novel search tree called increasing cost tree (ICT). The low-level performs a goal test on each ICT node. The new framework, called ICT search (ICTS), showed to run faster than the previous state-of-the-art A* approach by up to three orders of magnitude in many cases. In this paper we focus on the low-level of ICTS which performs the goal test. We introduce a number of optional pruning techniques that can significantly speed up the goal test. We discuss these pruning techniques and provide supporting experimental results.