Planning collision-free paths for a large group of agents is a challenging problem in many real-world applications. While recent advances in Multi-Agent Path Finding (MAPF) have shown promising progress, standard MAPF planners continue to rely on simplified kinodynamic models, preventing agents from directly following the generated MAPF plan. To bridge this gap, we propose kinodynamic Temporal Plan Graph planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a set of kinodynamically feasible speed profiles. We further incorporate execution timing uncertainty models and provide deterministic guarantees under bounded uncertainty models and probabilistic guarantees under stochastic models. Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism, dynamically incorporating agent information during execution to reduce uncertainty. Experiments show that WinkTPG can generate speed profiles for up to 1,000 agents within 1 second and improves solution quality by up to 51.7% over existing MAPF execution methods. We further validate WinkTPG in high-fidelity physics-based simulation and on real-world robots.

Current state-of-the-art autonomous driving vehicles mainly rely on each individual sensor system to perform perception tasks. Such a framework’s reliability could be limited by occlusion or sensor failure. To address this issue, more recent research proposes using vehicle-to-vehicle (V2V) communication to share perception information with others. However, most relevant works focus only on cooperative detection and leave cooperative tracking an underexplored research field. A few recent datasets, such as V2V4Real, provide 3D multi-object cooperative tracking benchmarks. However, their proposed methods mainly use cooperative detection results as input to a standard single-sensor Kalman Filter-based tracking algorithm. In their approach, the measurement uncertainty of different sensors from different connected autonomous vehicles (CAVs) may not be properly estimated to utilize the theoretical optimality property of Kalman Filter-based tracking algorithms. In this paper, we propose a novel 3D multi-object cooperative tracking algorithm for autonomous driving via a differentiable multi-sensor Kalman Filter. Our algorithm learns to estimate measurement uncertainty for each detection that can better utilize the theoretical property of Kalman Filter-based tracking methods. The experiment results show that our algorithm improves the tracking accuracy by 17% with only 0.037x communication costs compared with the state-of-the-art method in V2V4Real. Our code and videos are available at the URL and the URL.

The Resource Constrained Shortest Path Problem (RCSPP) seeks to determine a minimum-cost path between a start and a goal location while ensuring that one or multiple types of resource consumed along the path do not exceed their limits. This problem is often solved on a graph where a path is incrementally built from the start towards the goal during the search. RCSPP is computationally challenging as comparing these partial solution paths is based on multiple criteria (i.e., the accumulated cost and resource along the path), and in general, there does not exist a single path that optimizes all criteria simultaneously. Consequently, the search needs to maintain and explore a large number of partial paths in order to find an optimal solution. While a variety of algorithms have been developed to solve RCSPP, they either have little consideration about efficiently comparing and maintaining the partial paths, which reduces their overall runtime efficiency, or are restricted to handle only one resource constraint as opposed to multiple resource constraints. This paper develops Enhanced Resource Constrained A* (ERCA*), a fast A*-based algorithm that can find an optimal solution while satisfying multiple resource constraints. ERCA* leverages both the recent advances in multi-objective path planning to efficiently compare and maintain partial paths, and techniques from the existing RCSPP literature. Furthermore, ERCA* has a functional parameter to broker a trade-off between solution quality and runtime efficiency. The results show ERCA* often runs several orders of magnitude faster than an existing leading algorithm for RCSPP.

Key to the effectiveness of schedule-driven approaches to real-time traffic control is an ability to accurately predict when sensed vehicles will arrive at and pass through the intersection. Prior work in schedule-driven traffic control has assumed a static vehicle arrival model. However, this static predictive model ignores the fact that the queue count and the incurred delay should vary as different partial signal timing schedules (i.e., different possible futures) are explored during the online planning process. In this paper, we propose an alternative arrival time model that incorporates queueing dynamics into this forward search process for a signal timing schedule, to more accurately capture how the intersection’s queues vary over time. As each search state is generated, an incremental queueing delay is dynamically projected for each vehicle. The resulting total queueing delay is then considered in addition to the cumulative delay caused by signal operations. We demonstrate the potential of this approach through microscopic traffic simulation of a real-world road network, showing a 10-15% reduction in average wait times over the schedule-driven traffic signal control system in heavy traffic scenarios.

In many applications, uncertainty regarding the duration of activities complicates the generation of accurate plans and schedules. Such is the case for the problem considered in this paper - predicting the arrival times of buses at signalized intersections. Direct vehicle-to-infrastructure communication of location, speed and heading information offers unprecedented opportunities for real-time optimization of traffic signal timing plans, but to be useful bus arrival time prediction must reliably account for bus dwell time at near-side bus stops. To address this problem, we propose a novel, Bayesian hierarchical approach for constructing bus dwell time duration distributions from historical data. Unlike traditional statistical learning techniques, the proposed approach relies on minimal data, is inherently adaptive to time varying task duration distribution, and provides a rich description of confidence for decision making, all of which are important in the bus dwell time prediction context. The effectiveness of this approach is demonstrated using historical data provided by a local transit authority on bus dwell times at urban bus stops. Our results show that the dwell time distributions generated by our approach yield significantly more accurate predictions than those generated by both standard regression techniques and a more data intensive deep learning approach.

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to improve the efficiency of traffic flow in complex urban road networks. In this approach, a scheduling agent is associated with each intersection. Each agent senses the traffic approaching its intersection and in real-time constructs a schedule that minimizes the cumulative wait time of vehicles approaching the intersection over the current look-ahead horizon. In this paper, we propose a cooperative algorithm that utilizes both connected and autonomous vehicles (CAV) and schedule-driven traffic control to create better traffic flow in the city. The algorithm enables an intersection scheduling agent to adjust the arrival time of an approaching platoon through use of wireless communication to control the velocity of vehicles. The sequence of approaching platoons is thus shifted toward a new shape that has smaller cumulative delay. We demonstrate how this algorithm outperforms the original approach in a real-time traffic signal control problem.

This paper proposes a method for learning and utilizing potentially useful interaction patterns among neighborhood-based heuristics. It is built upon a previously proposed framework designed for facilitating the task of combining multiple neighborhood-based heuristics. Basically, an algorithm derived from this framework will operate by chaining the heuristics in a pipelined fashion. Conceptually, we can view this framework as an algorithmic template that contains two user-defined components: 1) the policy H for selecting heuristics, and 2) the policy L for choosing the length of the pipeline that chains the selected heuristics. In this paper, we will develop a method that automatically derives a policy H by analyzing the experience collected from running a baseline algorithm. This analysis will distill potentially useful patterns of interactions among heuristics, and give an estimate for the frequency of using each pattern. The empirical results on three problem domains show the effectiveness of the proposed approach.

We present Expressive Real-time Intersection Scheduling (ERIS), a schedule-driven control strategy for adaptive intersection control to reduce traffic congestion. ERIS maintains separate estimates for each lane approaching a traffic intersection allowing it to more accurately estimate the effects of scheduling decisions than previous schedule-driven approaches. We present a detailed description of the search space and A* search heuristic employed by ERIS to make scheduling decisions in real-time (every second). As a result of its increased expressiveness, ERIS outperforms a less expressive schedule-driven approach and a fully-actuated control method in a variety of simulated traffic environments.

In this paper, we study a simple hyper-heuristic that functions by sampling solution chains. A solution chain in this algorithm is formed by successively applying a randomly chosen heuristic to the previous solution to generate the next solution. Operating in this way, the algorithm can benefit from the accumulated effect of applying multiple heuristics. A key factor in this algorithm is the strategy for choosing the sampling length. We discuss a balanced strategy in a setting that contains two agnostic assumptions: First, we do not have detailed knowledge about the problem domain being solved except that we have access to the objective function and a set of predefined heuristics. Secondly, we have no information about the amount of time allocated for running our algorithm. We present a theoretical guarantee on using this strategy to choose the sampling lengths and derive some variants based on this strategy. Empirical results also confirm that these strategies deliver desired behavior. Finally, we briefly discuss the extension of incorporating a learning mechanism into the algorithm.

We consider the problem of minimizing the the delay of jobs moving through a directed graph of service nodes. In this problem, each node may have several links and is constrained to serve one link at a time. As jobs move through the network, they can pass through a node only after they have been serviced by that node. The objective is to minimize the delay jobs incur sitting on queues waiting to be serviced. Two popular approaches to this problem are backpressure algorithm and schedule-driven control. In this paper, we present a hybrid approach of those two methods that incorporates the stability of queuing theory into the schedule-driven control. We then demonstrate how this hybrid method outperforms the other two in a real-time traffic signal control problem, where the nodes are traffic lights, the links are roads, and the jobs are vehicles. We show through simulations that, in scenarios with heavy congestion, the hybrid method results in 50% and 15% reductions in delay over schedule-driven control and backpressure respectively. A theoretical analysis also justifies our results.

In this paper, we propose a market-driven approach to traffic signal control. In contrast to traditional traffic engineering approaches, our approach gives agency and decision-making influence to individual drivers and exploits auction mechanisms to make traffic control decisions. Drivers make payments to their corresponding movement managers (each responsible for a particular directional flow through the intersection), and movement managers then compete for control of the signal. These financial transactions, if treated literally provide an alternate source of funding transportation infrastructure. Previous work with this model has demonstrated the ability to achieve better overall traffic flow performance than actuated control, a simple adaptive traffic signal control strategy based on detection and monitoring of waiting vehicles. Here we consider the design and analysis of bidding strategies capable of factoring in a given driver's value of time (VOT), as indicated by the amount of voluntary contributions that are made on top of the fixed fee that every driver is charged. We analyze the potential for expediting high VOT drivers without undue disruption of overall traffic flows.

Assembly of large structures requires large fixtures, often referred to as monuments. Their cost and massive size limit flexibility and scalability of the manufacturing process. Numerous small mobile robots can replace these large structures and, therefore, replicate the efficiency of the assembly line with far more flexibility. An assembly line made up of mobile manipulators can easily and rapidly be reconfigured to support scalability and a varied product mix, while allowing for near optimal resource assignment. The challenge to using small robots in place of monuments is making their joint behavior precise enough to accomplish the task and efficient enough to execute subtasks in a reasonable period of time. In this paper, we describe a set of techniques that we combine to achieve the necessary precision and overall efficiency to build a large structure. We describe and demonstrate these techniques in the context of a testbed we implemented for assembling a wing ladder.

This paper investigates the issues of maintaining diversity in the Extended Compact Genetic Algorithm (ECGA) for handling Dynamic Optimization Problems (DOPs). Specifically, we focused on how a diversity maintenance mechanism places samples in the search space, and derive an approach that is more appropriate for DOPs that change progressively. The discussion proceeds in two parts. First, we reaffirm the perspective that the problem structure should be considered when maintaining diversity for addressing DOPs. This point is demonstrated by an additively decomposable DOP in which each subfunction has two complementary optima. Following that, we further discuss how we can better allocate the samples for DOPs that change progressively by thinking about the current promising region, which should contain the current optima, and its neighborhood. Based on this notion, we devise a mechanism that utilizes the information provided by the probabilistic models from ECGA and uses a trade-off between exploration and exploitation to achieve the desired diversity allocation. The empirical results show that our approach follows the changing optima better compared to techniques that use Restricted Tournament Replacement (RTR). Furthermore, it requires only half of the function evaluations needed by approaches that use RTR.

In this paper, we consider the problem of feasibly integrating new pick-up and delivery requests into existing vehicle itineraries in a dynamic, dial-a-ride problem (DARP) setting. Generalizing from previous work in oversubscribed task scheduling, we define a controlled iterative repair search procedure for finding an alternative set of vehicle itineraries in which the overall solution has been feasibly extended to include newly received requests. We first evaluate the performance of this technique on a set of DARP feasibility benchmark problems from the literature. We then consider its use on a real-world DARP problem, where it is necessary to accommodate all requests and constraints must be relaxed when a request cannot be feasibly integrated. For this latter analysis, we introduce a constraint relaxation post processing step and consider the performance impact of using our controlled iterative search over the current greedy search approach.

For some tasks, the use of more than one robot may improve the speed, reliability, or flexibility of completion, but many other tasks can be completed only by multiple robots. This paper investigates controller design using multi-objective genetic programming for a multi-robot system to solve a highly constrained problem, where multiple unmanned aerial vehicles (UAVs) must monitor targets spread sparsely throughout a large area. UAVs have a small communication range, sensor information is limited and noisy, monitoring a target takes an indefinite amount of time, and evolved controllers must continue to perform well even as the number of UAVs and targets changes. An evolved task selection controller dynamically chooses a target for the UAV based on sensor information and communication. Controllers evolved using several communication schemes were compared in simulation on problem scenarios of varying size, and the results suggest that this approach can evolve effective controllers if communication is limited to the nearest other UAV.

We describe a system for scheduling a conference based on incomplete information about available resources and scheduling constraints. We explain the representation of uncertain knowledge, describe a local-search algorithm for generating near-optimal schedules, and give empirical results of automated scheduling under uncertainty.

We characterize the search landscape of random instances of the job shop scheduling problem (JSP). Specifically, we investigate how the expected values of (1) backbone size, (2) distance between near-optimal schedules, and (3) makespan of random schedules vary as a function of the job to machine ratio (N/M). For the limiting cases N/M approaches 0 and N/M approaches infinity we provide analytical results, while for intermediate values of N/M we perform experiments. We prove that as N/M approaches 0, backbone size approaches 100%, while as N/M approaches infinity the backbone vanishes. In the process we show that as N/M approaches 0 (resp. N/M approaches infinity), simple priority rules almost surely generate an optimal schedule, providing theoretical evidence of an "easy-hard-easy" pattern of typical-case instance difficulty in job shop scheduling. We also draw connections between our theoretical results and the "big valley" picture of JSP landscapes.

We introduce a new approach to autonomous decentralized shop floor routing. Our system, which we call Ant Colony Control (AC/sup 2/), applies the analogy of a colony of ants foraging for food to the problem of dynamic shop floor routing. In this system, artificial ants use only indirect communication to make all shop routing decisions by altering and reacting to their dynamically changing common environment through the use of simulated pheromone trails. For simple factory layouts, we show that the emergent behavior of the colony is comparable to using the optimal routing strategy. Furthermore, as the complexity of the factory layout is increased, we show that the adaptive behavior of AC/sup 2/ evolves local decision making policies that lead to near-optimal solutions from the standpoint of global performance.

"Survival of the fittest" is often seen as the driving force behind adaptation and evolution. For sure, all evolutionary algorithms use fitness based selection. However, it is not necessary to know where you are, to know where you are going. Similarly, it is not necessary to know the fitness of a solution, to find a better solution. The GENIE algorithm uses random parent selection and a non-elitist generational replacement scheme. Experiments on a non-trivial instance of the Traveling Salesman Problem show that heuristic operators in GENIE can converge to the optimal solution without evaluating fitness.

When dealing with object classification, each object is defined by a set of features (characteristics) that classify the object to a particular class. The problem is how to choose the best subset of characteristics that provide an accurate classification. Previous research has shown that decision tables are as accurate as C4.5 for classification purposes. Two different genetic search techniques, CHC and CF/RSC, are applied to this problem. Results shows that CF/RSC and decision tables are a very good combination when dealing with large feature spaces. Results also suggest that CHC is better when used for problems with noise added to the features.

Promoting and maintaining diversity is a critical requirement of search in learning classifier systems (LCSs). What is required of the genetic algorithm (GA) in an LCS context is not convergence to a single global maximum, as in the standard optimization framework, but instead the generation of individuals (i.e., rules) that collectively cover the overall problem space. COGIN (COverage-based Genetic INduction) is a system designed to exploit genetic recombination for the purpose of constructing rule-based classification models from examples. The distinguishing characteristic of COGIN is its use of coverage of training set examples as an explicit constraint on the search, which acts to promote appropriate diversity in the population of rules over time. By treating training examples as limited resources, COGIN creates an ecological model that simultaneously accommodates a dynamic range of niches while encouraging superior individuals within a niche, leading to concise and accurate decision models. Previous experimental studies with COGIN have demonstrated its performance advantages over several well-known symbolic induction approaches. In this paper, we examine the effects of two modifications to the original system configuration, each designed to inject additional diversity into the search: increasing the carrying capacity of training set examples (i.e., increasing coverage redundancy) and increasing the level of disruption in the recombination operator used to generate new rules. Experimental results are given that show both types of modifications to yield substantial improvements to previously published results.

The authors describe HSTS, an integrated planning and scheduling architecture that has been applied to the problem of generating observation schedules for the Hubble Space Telescope. HSTS deals with the problem of the interaction of resource allocation and auxiliary task expansion during schedule development by viewing planning and scheduling as two complementary aspects in the construction of the behavior of a system. The authors first describe how HSTS specifies the dynamics of a system, how it represents schedules at multiple levels of abstraction, and the specific problem solving machinery it provides. An example of the use of the architecture in the Hubble Space Telescope domain is given. Performance results that indicate the practicality of the HSTS approach are presented.>