Anytime multi-agent path finding (MAPF) is a promising approach to scalable and collision-free path optimization in multi-agent systems. MAPF-LNS, based on Large Neighborhood Search (LNS), is the current state-of-the-art approach where a fast initial solution is iteratively optimized by destroying and repairing selected paths, i.e., a neighborhood, of the solution. Delay-based MAPF-LNS has demonstrated particular effectiveness in generating promising neighborhoods via seed agents, according to their delays. Seed agents are selected using handcrafted strategies or online learning, where the former relies on human intuition about underlying structures, while the latter conducts black-box optimization, ignoring any structure. In this paper, we propose Truncated Adaptive Counterfactual K-ranked LEarning (TACKLE) to select seed agents via informed online learning by leveraging handcrafted strategies as human intuition. We show theoretically that TACKLE dominates its handcrafted and black-box learning counterparts in the limit. Our experiments demonstrate cost improvements of at least 60% in instances with one thousand agents, compared with state-of-the-art anytime solvers.

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for a team of agents. Although several MAPF methods that solve full-horizon MAPF have completeness guarantees, very few MAPF methods that plan partial paths have completeness guarantees. Recent work introduced the Windowed Complete MAPF (WinC-MAPF) framework, which shows how windowed optimal MAPF solvers (e.g., SS-CBS) can use heuristic updates and disjoint agent groups to maintain completeness even when planning partial paths. A core limitation of WinC-MAPF is that it requires optimal MAPF solvers. Our main contribution is to extend WinC-MAPF by showing how we can use a bounded suboptimal solver while maintaining completeness. In particular, we design Dynamic Agent Grouping ECBS (DAG-ECBS) which dynamically creates and plans agent groups while maintaining that each agent group solution is bounded suboptimal. We prove how DAG-ECBS can maintain completeness in the WinC-MAPF framework and can improve scalability compared to windowed ECBS which does not have completeness guarantees. More broadly, our work serves as a blueprint for designing more MAPF methods that can use the WinC-MAPF framework

Monte-Carlo Tree Search (MCTS) is a popular approach to online planning under uncertainty. While MCTS uses statistical sampling via multi-armed bandits to avoid exhaustive search in complex domains, common closed-loop approaches typically construct enormous search trees to consider a large number of potential observations and actions. On the other hand, open-loop approaches offer better memory efficiency by ignoring observations but are generally not competitive with closed-loop MCTS in terms of performance - even with commonly integrated human knowledge. In this paper, we propose Counterfactual Open-loop Reasoning with Ad hoc Learning (CORAL) for open-loop MCTS, using a causal multi-armed bandit approach with unobserved confounders (MABUC). CORAL consists of two online learning phases that are conducted during the open-loop search. In the first phase, observational values are learned based on preferred actions. In the second phase, counterfactual values are learned with MABUCs to make a decision via an intent policy obtained from the observational values. We evaluate CORAL in four POMDP benchmark scenarios and compare it with closed-loop and open-loop alternatives. In contrast to standard open-loop MCTS, CORAL achieves competitive performance compared with closed-loop algorithms while constructing significantly smaller search trees.

Anytime multi-agent path finding (MAPF) is a promising approach to scalable and collision-free path optimization in multi-agent systems. MAPF-LNS, based on Large Neighborhood Search (LNS), is the current state-of-the-art approach where a fast initial solution is iteratively optimized by destroying and repairing selected paths of the solution. Current MAPF-LNS variants commonly use an adaptive selection mechanism to choose among multiple destroy heuristics. However, to determine promising destroy heuristics, MAPF-LNS requires a considerable amount of exploration time. As common destroy heuristics are stationary, i.e., non-adaptive, any performance bottleneck caused by them cannot be overcome by adaptive heuristic selection alone, thus limiting the overall effectiveness of MAPF-LNS. In this paper, we propose Adaptive Delay-based Destroy-and-Repair Enhanced with Success-based Self-learning (ADDRESS) as a single-destroy-heuristic variant of MAPF-LNS. ADDRESS applies restricted Thompson Sampling to the top-K set of the most delayed agents to select a seed agent for adaptive LNS neighborhood generation. We evaluate ADDRESS in multiple maps from the MAPF benchmark set and demonstrate cost improvements by at least 50% in large-scale scenarios with up to a thousand agents, compared with the original MAPF-LNS and other state-of-the-art methods.

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths, one for each agent in a shared environment. Its objective is to minimize the sum of path costs (SOC), where the path cost of each agent is defined as the travel time from its start location to its target location. Explicit Estimation Conflict-Based Search (EECBS) is the leading algorithm for bounded-suboptimal MAPF, with the SOC of the solution being at most a user-specified factor w away from optimal. EECBS maintains sets of paths and a lower bound LB on the optimal SOC. Then, it iteratively selects a set of paths whose SOC is at most w times LB and introduces constraints to resolve collisions. For each path in a set, EECBS maintains a lower bound on its optimal path that satisfies constraints. By finding a path with cost at most its threshold, defined as w times its lower bound, EECBS guarantees to find a bounded-suboptimal solution. To speed up EECBS, previous work uses flex distribution to relax the requirement that each path needs to be at most its threshold. Though EECBS with flex distribution guarantees to find a bounded-suboptimal solution, increasing the thresholds may increase the SOC beyond w times LB, forcing EECBS to switch among different sets of paths (whose SOC are still at most w times LB), and thus reducing efficiency. To address this issue, we propose Conflict-Based Flex Distribution that distributes flex in proportion to the number of collisions. We also estimate the extra travel time (i.e., delays) needed to satisfy constraints and propose Delay-Based Flex Distribution. On top of that, we propose Mixed-Strategy Flex Distribution, combining both in a hierarchical framework. We prove that EECBS with our new flex distribution mechanisms is complete and bounded-suboptimal. The experiments show that our approaches outperform the original (greedy) flex distribution. Also, we redesign Focal-A* search from the previous work to improve LB for a congested environment.

In the multi-objective shortest-path problem we are interested in computing a path, or a set of paths that simultaneously balance multiple cost functions. This problem is important for a diverse range of applications such as transporting hazardous materials considering travel distance and risk. This family of problems is not new with results dating back to the 1970's. Nevertheless, the significant progress made in the field of heuristic search resulted in a new and growing interest in the sub-field of multi-objective search. Consequently, in this paper we review the fundamental problems and techniques common to most algorithms and provide a general overview of the field. We then continue to describe recent work with an emphasis on new challenges that emerged and the resulting research opportunities.

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths, one for each agent, in a shared environment, while minimizing their sum of travel times. Since solving MAPF optimally is NP-hard, researchers have explored algorithms that solve MAPF suboptimally but efficiently. Priority-Based Search (PBS) is the leading algorithm for this purpose. It finds paths for individual agents, one at a time, and resolves collisions by assigning priorities to the colliding agents and replanning their paths during its search. However, PBS becomes ineffective for MAPF instances with high densities of agents and obstacles. Therefore, we introduce Greedy PBS (GPBS), which uses greedy strategies to speed up PBS by minimizing the number of collisions between agents. We then propose techniques that speed up GPBS further, namely partial expansions, target reasoning, induced constraints, and soft restarts. We show that GPBS with all these improvements has a higher success rate than the state-of-the-art suboptimal algorithm for a 1-minute runtime limit, especially for MAPF instances with small maps and dense obstacles.

This extended abstract presents a theoretical analysis of node expansions in Multi-Objective Search. We define three categories of nodes, Must-Expand Nodes, Maybe-Expand Nodes, and Never-Expand Nodes. Our analysis establishes that regardless of the Ordering Function or Multi-Objective Search algorithm used, any Multi-Objective Search algorithm must expand all Must-Expand Nodes, some or none of Maybe-Expand Nodes, and none of Never-Expand Nodes. In addition, we conduct experimental evaluations of various Ordering Functions, revealing that they all expand the same number of nodes and compare their efficiency at finding solutions at various stages of the search.

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents that minimize the sum of path costs. EECBS is a leading two-level algorithm that solves MAPF bounded-suboptimally, that is, within some factor w of the minimum sum of path costs C*. It uses focal search to find bounded-suboptimal paths on the low level and Explicit Estimation Search (EES) to resolve collisions on the high level. EES keeps track of a lower bound LB on C* to find paths whose sum of path costs is at most w LB in order to solve MAPF bounded-suboptimally. However, the costs of many paths are often much smaller than w times their minimum path costs, meaning that the sum of path costs is much smaller than w C*. In this paper, we therefore propose Flexible EECBS (FEECBS), which uses a flex(ible) distribution of the path costs (that relaxes the requirement to find bounded-suboptimal paths on the low level) in order to reduce the number of collisions that need to be resolved on the high level while still guaranteeing to solve MAPF bounded suboptimally. We address the drawbacks of flex distribution via techniques such as restrictions on the flex distribution, restarts of the high-level search with EECBS, and low-level focal-A* search. Our empirical evaluation shows that FEECBS substantially improves the efficiency of EECBS on MAPF instances with large maps and large numbers of agents.

In Multi-Agent Pathfinding (MAPF), the task is to find non-colliding paths for a set of agents. This paper focuses on search-based MAPF algorithms from the Conflict-Based Framework, which is introduced here. A common technique in such algorithms is to merge a group of dependent agents into a meta-agent and plan non-colliding paths for the meta-agent using a low-level MAPF sub-solver. We analyze the patterns that emerge when agents are merged in an arbitrary order. We then introduce policies for choosing which agents or meta-agents to merge to achieve improved efficiency in three algorithms: Independence Detection (ID) and Improved Conflict-Based Search (ICBS), which are optimal, and Priority-Based Search (PBS), which is a fast suboptimal algorithm. Experimental results show a significant improvement in efficiency

Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale railway networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF, or in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes.

Solving Multi-Agent Path Finding (MAPF) instances optimally is NP-hard, and existing optimal and bounded suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP is able to solve as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps.

In this paper, we propose a novel system architecture called multi-layer environmental affordance map for social and service companion robots. Based on this architecture, robots can organize the perception and inference information efficiently and generate social friendly navigation strategies. In other words, robots are able to strengthen their perception and inference abilities to interact with domestic environment and users under our efficient framework. The main feature of this architecture is that the relations between layers can be viewed as affordances to improve the accuracy and the robustness of the detection and inference. The results show that our architecture achieves robust indoor localization, scene localization, human event detection and socially friendly navigation in real time under limited computational resource.

The following topics are dealt with: learning (artificial intelligence); medical signal processing; neurophysiology; electroencephalography; mobile robots; feature extraction; brain-computer interfaces; neural nets; convolutional neural nets; production engineering computing.

Recently, as the rise of deep reinforcement learning, it not only can help the robot to convert the complicated environment scene to motor control command directly but also can accomplish the navigation task properly. In this paper, we propose a novel structure, where the objective is to achieve navigation in large-scale indoor complex environment without pre-constructed map. Generally, it requires good understanding of such indoor environment to make complex spatial perception possible, especially when the indoor space consists of many walls and doors which might block the view of robot leading to complex navigation path. By the proposed distributed deep reinforcement learning in different local regions, our method can achieve indoor visual navigation in the aforementioned large-scale environment without extra map information and human instruction. In the experiments, we validate our proposed method by conducting highly promising navigation tasks both in simulation and real environments.

An approach of robust localization for mobile robot working in indoor is proposed in this paper. A novel method for laser SLAM and visual SLAM fusion is introduced to provide robust localization. This architecture can be applied to a situation where any two kinds of laser-based SLAM and monocular camera-based SLAM can be fused together instead of being limited to single specific SLAM algorithm. While laser-based SLAM and monocular camera-based SLAM have their own strengths and drawbacks, the integration of these two kinds of SLAM algorithm can then promote the algorithmic effectiveness. Instead of using feature matching methods to achieve fusion procedure, trajectories matching is proposed with an attempt to achieve the generalization over all different kinds of SLAM algorithms, since localization is a natural function associated with any SLAM algorithm. It turns out that the hereby proposed approach is very lightweight during the run time, and the calculation can run in real-time without unnecessary computation waste. The experimental results show the localization error in terms of the real distance can be less than 5%. Furthermore, through the experiment the proposed system can be shown able to improve the localization when the sensors are not very powerful.