The Moving Target Traveling Salesman Problem (MT-TSP) seeks a trajectory that intercepts several moving targets, within a particular time window for each target. When generic nonlinear target trajectories or kinematic constraints on the agent are present, no prior algorithm guarantees convergence to an optimal MT-TSP solution. Therefore, we introduce the Iterated Random Generalized (IRG) TSP framework. The idea behind IRG is to alternate between randomly sampling a set of agent configuration-time points, corresponding to interceptions of targets, and finding a sequence of interception points by solving a generalized TSP (GTSP). This alternation asymptotically converges to the optimum. We introduce two parallel algorithms within the IRG framework. The first algorithm, IRG-PGLNS, solves GTSPs using PGLNS, our parallelized extension of state-of-the-art solver GLNS. The second algorithm, Parallel Communicating GTSPs (PCG), solves GTSPs for several sets of points simultaneously. We present numerical results for three MT-TSP variants: one where intercepting a target only requires coming within a particular distance, another where the agent is a variable-speed Dubins car, and a third where the agent is a robot arm. We show that IRG-PGLNS and PCG converge faster than a baseline based on prior work. We further validate our framework with physical robot experiments.

Given a graph representing the workspace, Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start vertex to their respective goal vertex while minimizing path costs. Although many MAPF algorithms were developed and can handle up to thousands of agents, they usually rely on the assumption that each action of the agent takes a time unit, and the actions of all agents are synchronized in a sense that the actions of agents start at the same discrete time step, which may limit their use in practice. Only a few algorithms have been developed to address asynchronous actions, and they all lie on one end of the spectrum, focusing on finding optimal solutions with limited scalability. This paper develops new planners that lie on the other end of the spectrum, trading off solution quality for scalability, by finding an unbounded sub-optimal solution for many agents. Our method leverages both search-based methods in handling asynchronous actions and techniques in rule-based planning for MAPF. We analyze the properties of our method and test it against several baselines with up to a thousand agents with asynchronous actions in various maps. Given a runtime limit, our method can handle an order of magnitude more agents than the existing methods with about 25% longer makespan.

The moving target traveling salesman problem with obstacles (MT-TSP-O) seeks an obstacle-free trajectory for an agent that intercepts a given set of moving targets, each within specified time windows, and returns to the agent's starting position. Each target moves with a constant velocity within its time windows, and the agent has a speed limit no smaller than any target's speed. We present FMC*-TSP, the first complete and bounded-suboptimal algorithm for the MT-TSP-O, and results for an agent whose configuration space is$\mathbb{R}^{3}$. Our algorithm interleaves a high-level search and a lowlevel search, where the high-level search solves a generalized traveling salesman problem with time windows (GTSP-TW) to find a sequence of targets and corresponding time windows for the agent to visit. Given such a sequence, the low-level search then finds an associated agent trajectory. To solve the low-level planning problem, we develop a new algorithm called FMC*, which finds a shortest path on a graph of convex sets (GCS) via implicit graph search and pruning techniques specialized for problems with moving targets. We test FMC*-TSP on 280 problem instances with up to 40 targets and demonstrate its smaller median runtime than a baseline based on prior work.

This paper focuses on the motion planning problem for serial articulated robots with revolute joints under kinematic constraints. Many motion planners leverage iterative local optimization methods but are often trapped in local minima due to non-convexity of the problem. A key reason for the non-convexity is the trigonometric term when parameterizing the kinematics using joint angles. Recent distance-based formulations can eliminate these trigonometric terms by formulating the kinematics based on distances, and has shown superior performance against classic joint angle based formulations in domains like inverse kinematics (IK). However, distance-based kinematics formulations have not yet been studied for motion planning, and naively applying them for motion planning may lead to poor computational efficiency. In particular, IK seeks one configuration while motion planning seeks a sequence of configurations, which greatly increases the scale of the underlying optimization problem. This paper proposes Propagative Distance Optimization for Motion Planning (PDOMP), which addresses the challenge by (i) introducing a new compact representation that reduces the number of variables in the distance-based formulation, and (ii) leveraging the chain structure to efficiently compute forward kinematics and Jacobians of the robot among waypoints along a path. Test results show that PDOMP runs up to 10 times faster than the sampling-based and angle-based-optimization baseline methods.

This paper investigates Path planning Among Movable Obstacles (PAMO), which seeks a minimum cost collision-free path among static obstacles from start to goal while allowing the robot to push away movable obstacles (i.e., objects) along its path when needed. To develop planners that are complete and optimal for PAMO, the planner has to search a giant state space involving both the location of the robot as well as the locations of the objects, which grows exponentially with respect to the number of objects. This paper leverages a simple yet under-explored idea that, only a small fraction of this giant state space needs to be searched during planning as guided by a heuristic, and most of the objects far away from the robot are intact, which thus leads to runtime efficient algorithms. Based on this idea, this paper introduces two PAMO formulations, i.e., bi-objective and resource constrained problems in an occupancy grid, and develops PAMO*, a planning method with completeness and solution optimality guarantees, to solve the two problems. We then further extend PAMO* to hybrid-state PAMO* to plan in continuous spaces with high-fidelity interaction between the robot and the objects. Our results show that, PAMO* can often find optimal solutions within a second in cluttered maps with up to 400 objects.

This paper considers a multi-robot trajectory planning problem with inter-robot connectivity maintenance for information gathering. Given an information map in the form of a distribution over the workspace, ergodic search plans trajectories, along which, the time spent in any region is proportional to the amount of information in that region, and can balance between exploration and exploitation. Existing ergodic search rarely considers the limited communication range among robots or connectivity maintenance, and this paper takes a step to fill this gap. Besides, multi-robot connectivity maintenance was studied a lot, including continual, periodic, intermittent connectivity, etc. Naively combining these methods with ergodic search may prevent the planner from finding high-quality ergodic trajectories or lead to poor connectivity among the robots. To handle the challenge, this paper adapts an intermittent connectivity maintenance strategy to the ergodic search framework, and develops a two-phase trajectory planning approach utilizing the augmented Lagrangian method. Our simulation and real drone experiments show that under the same connectivity maintenance requirement, our approach plans trajectories that are about 10 times better than the baselines in terms of the ergodic metric.

This paper investigates a problem called Multi-Agent Combinatorial Path Finding for Tractor-Trailers (MCPF-TT), which seeks collision-free paths for multiple agents from their start to goal locations, visiting a set of intermediate target locations in the middle of the paths, while minimizing the sum of arrival times. Additionally, each agent behaves like a tractor, and a trailer is attached to the agent at each intermediate target location, which increases the "body length" of that agent by one unit. Planning for those tractor-trailers in a cluttered environment introduces additional challenges, since the planner has to plan each agent in a larger state space that includes the position of the attached trailers to avoid self-collision. Furthermore, agents are more likely to collide with each other due to the increasing body lengths, and the conventional collision resolution techniques turn out to be computationally inefficient. This paper develops a new planner called CBSS-TT that includes both novel inter-agent conflict resolution techniques, and a new single-agent planner TTCA* that finds optimal single-agent path while avoiding self-collision. Our test results show that CBSS-TT sometimes requires 60% fewer number of iterations while finding solutions with cheaper costs than the baselines.

Multi-Agent Motion Planning (MAMP) seeks collision-free trajectories for multiple agents from their respective start to goal locations among static obstacles, while minimizing a cost function over the trajectories. Existing approaches for this problem include graph-based, Mix-Integer Programming (MIP) based and trajectory optimization-based, each with its own limitations. This paper introduces a new approach for MAMP based on Mixed Integer Conic Programming (MICP) formulation that complements these existing approaches. We show that our formulation is valid and test our approach against various baselines, including a graph-based method that combines search and sampling, as well as different MIP formulations. The numerical results show that the solutions found by our approach are sometimes eight times closer to the true optimum than the ones found by the baseline when given the same amount of runtime limit. We also verify our approach with multiple drones in a lab setting.

This paper investigates a Traveling Salesman Problem with Time Windows and Vacant Penalties (TSP-TW-VP), which plans a path to service a set of machines at different locations within their respective time windows while minimizing two objective functions: the finish time and penalty for machine vacancy. There is often no single solution that optimizes both objectives simultaneously, and the problem thus seeks the Pareto-optimal solutions. TSP-TW-VP generalizes TSP-TW and is therefore NP-hard. To solve the problem, this paper develops an algorithm called Search with Look-Ahead Pruning (S-LAP) that is guaranteed to find all Pareto-optimal solutions for TSP-TW-VP. S-LAP gains computational efficiency by introducing a novel look-ahead pruning rule, and a fast dominance checking method based on both the objective functions and path history. Experimental results show that the proposed look-ahead pruning and fast dominance can speed up the search for 2-8 times over 4 different datasets.

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-Based Planning (LSRP) is proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSPR* and test it against several baselines with up to 1000 agents in various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from start to goal locations. This paper considers a generalization of MAPF called Multi-Agent Combinatorial Path Finding (MCPF) where agents must collectively visit a set of intermediate target locations before reaching their goals. MCPF is challenging as it involves both planning collision-free paths for multiple agents and target sequencing, i.e., assigning targets to and computing the visiting order for each agent. A recent method Conflict-Based Steiner Search (CBSS) is developed to solve MCPF to optimality, which, however, does not scale well when the number of agents or targets is large (e.g. 50 targets). While MAPF research has developed methods to plan bounded sub-optimality paths for many agents, it remains unknown how to find bounded sub-optimal solutions in the presence of many targets. This paper fills this gap by developing a methodAK*for target sequencing (A for Approximation and K* for K-best), which leverages approximation algorithms for traveling salesman problems.AK*is motivated by MCPF, but is a standalone method that can solve K-best routing problems in general. We prove thatAK*has worst-case polynomial runtime complexity and finds bounded sub-optimal solutions. WithAK*, we develop twoCBSSvariants that find bounded sub-optimal paths for MCPF. Our results verify the fast running speeds of our methods with up to 200 targets. Note to Practitioners—The motivation of this paper originates from the need to plan conflict-free paths for multiple mobile robots in cluttered environment in warehouse logistics, manufacturing and inspection. While existing methods for multi-agent planning typically consider finding paths from starts to goals, this paper investigates the case, where agents must collectively visit a set of intermediate target locations before reaching their goals, for the purpose of inspection, picking or placing parts, etc. To solve the problem, this paper first develops an algorithm to find K-best solutions for traveling salesman problems with bounded sub-optimality, which then leads to two multi-agent planners that can handle hundreds of targets and tens of agents. We provide a Gazebo simulation to showcase the usage of the planner in a warehouse like environment.

We introduce a new bounding approach called Continuity* (C$^{*}$), which provides optimality guarantees for the Moving-Target Traveling Salesman Problem (MT-TSP). Our approach relaxes the continuity constraints on the agent's tour by partitioning the targets' trajectories into smaller segments. This allows the agent to arrive at any point within a segment and depart from any point in the same segment when visiting each target. This formulation enables us to pose the bounding problem as a Generalized Traveling Salesman Problem (GTSP) on a graph, where the cost of traveling along an edge requires solving a new problem called the Shortest Feasible Travel (SFT). We present various methods for computing bounds for the SFT problem, leading to several variants of C$^{*}$. We first prove that the proposed algorithms provide valid lower-bounds for the MT-TSP. Additionally, we provide computational results to validate the performance of all C$^{*}$variants on instances with up to 15 targets. For the special case where targets move along straight lines, we compare our C$^{*}$variants with a mixed-integer Second Order Conic Program (SOCP) based method, the current state-of-the-art solver for the MT-TSP. While the SOCP-based method performs well on instances with 5 and 10 targets, C$^{*}$outperforms it on instances with 15 targets. For the general case, on average, our approaches find feasible solutions within approximately 4.5$\%$of the lower-bounds for the tested instances.

This paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP), where the goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tour. Though MTSP has been widely studied, obtaining near-optimal solutions for large-scale problems is still challenging due to its NP-hardness. Recent efforts in data-driven methods face challenges of the need for hard-to-obtain supervision and issues with high variance in gradient estimations, leading to slow convergence and highly sub-optimal solutions. We address these issues by reformulating MTSP as a bilevel optimization problem, using the concept of imperative learning (IL). This involves introducing an allocation network that decomposes the MTSP into multiple single-agent traveling salesman problems (TSPs). The longest tour from these TSP solutions is then used to self-supervise the allocation network, resulting in a new self-supervised, bilevel, end-to-end learning framework, which we refer to as imperative MTSP (iMTSP). Additionally, to tackle the high-variance gradient issues during the optimization, we introduce a control variate-based gradient estimation algorithm. Our experiments showed that these innovative designs enable our gradient estimator to converge 20× faster than the advanced reinforcement learning baseline, and find up to 80% shorter tour length compared with Google OR-Tools MTSP solver, especially in large-scale problems (e.g. 1000 cities and 15 agents).

This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP), which seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving targets exactly once within their assigned time-windows, and returns to the depot. The formulation relies on the key idea that when the targets move along lines, their trajectories become convex sets within the space-time coordinate system. The problem then reduces to finding the shortest path within a graph of convex sets, subject to some speed constraints. We compare our formulation with the current state-of-the-art Mixed Integer Conic Program (MICP) formulation for the MT-TSP. The experimental results show that our formulation outperforms the MICP for instances with up to 20 targets, with up to two orders of magnitude reduction in runtime, and up to a 60% tighter optimality gap. We also show that the solution cost from the convex relaxation of our formulation provides significantly tighter lower-bounds for the MT-TSP than the ones from the MICP.

When coordinating the motion of connected autonomous vehicles at a signal-free intersection, the vehicles from each direction naturally forms a team and each team seeks to minimize their own traversal time through the intersection, without concerning the traversal times of other teams. Since the intersection is shared by all teams and agent-agent collision must be avoided, the coordination has to trade the traversal time of one team for the other. This paper thus investigates a problem called Multi-Agent Teamwise Cooperative Path Finding (TCPF), which seeks a set of collision-free paths for the agents from their respective start to goal locations, and agents are grouped into multiple teams with each team having its own objective function to optimize. In general, there are more than one teams and hence multiple objectives. TCPF thus seeks the Pareto-optimal front that represents possible trade-offs among the teams. We develop a centralized planner for TCPF by leveraging the Multi-Agent Path Finding techniques to resolve agent-agent collision, and Multi-Objective Optimization to find Pareto-optimal solutions. We analyze the completeness and optimality of the planner, which is then tested in various settings with up to 40 agents to verify the runtime efficiency and showcase the usage in intersection coordination.

The Orienteering Problem (OP) seeks a path on a graph to maximize total rewards collected subject to a path length budget. Typically, a reward is achieved by visiting a vertex in the graph, and such a reward is constant for all time. This paper considers a variant of OP where the reward of each vertex is an arbitrary time-dependent function, and hence the name time-varying reward OP (TR-OP). To solve this problem, we develop a novel heuristic search algorithm called Reward Maximization A* (RMA*), which is guaranteed to find an optimal solution to TR-OP. We also develop a fast method to compute an admissible heuristic for RMA* that can effectively direct the search to save computational effort. Furthermore, we introduce a hyper-parameter in RMA* that trades off between solution quality and runtime efficiency for RMA*. We benchmark RMA* against a recent dynamic programming (DP) approach, which runs fast in practice, but has no guarantee of the solution optimality. In our tests, RMA* reduces the runtime by up to 70% compared to DP. By adjusting the hyper-parameter, RMA* is able to find solutions with up to 30% more rewards than those found by DP.

Multi-Agent Combinatorial Path Finding (MCPF) seeks collision-free paths for multiple agents from their initial locations to destinations, visiting a set of intermediate target locations in the middle of the paths, while minimizing the sum of arrival times. While a few approaches have been developed to handle MCPF, most of them simply direct the agent to visit the targets without considering the task duration, i.e., the amount of time needed for an agent to execute the task (such as picking an item) at a target location. MCPF is NP-hard to solve to optimality, and the inclusion of task duration further complicates the problem. To handle task duration, we develop two methods, where the first method post-processes the paths planned by any MCPF planner to include the task duration and has no solution optimality guarantee; and the second method considers task duration during planning and is able to ensure solution optimality. The numerical and simulation results show that our methods can handle up to 20 agents and 50 targets in the presence of task duration, and can execute the paths subject to robot motion disturbance.

Deep learning has had remarkable success in robotic perception, but its data-centric nature suffers when it comes to generalizing to ever-changing environments. By contrast, physics-based optimization generalizes better, but it does not perform as well in complicated tasks due to the lack of high-level semantic information and reliance on manual parametric tuning. To take advantage of these two complementary worlds, we present PyPose: a robotics-oriented, PyTorch-based library that combines deep perceptual models with physics-based optimization. PyPose's architecture is tidy and well-organized, it has an imperative style interface and is efficient and user-friendly, making it easy to integrate into real-world robotic applications. Besides, it supports parallel computing of any order gradients of Lie groups and Lie algebras and 2nd-order optimizers, such as trust region methods. Experiments show that PyPose achieves more than 10× speedup in computation compared to the state-of-the-art libraries. To boost future research, we provide concrete examples for several fields of robot learning, including SLAM, planning, control, and inertial navigation.

Multi-Agent Path Finding (MA-PF) computes a set of collision-free paths for multiple agents from their respective starting locations to destinations. This paper considers a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to be minimized. For example, an objective can be the sum or max of individual arrival times of the agents. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Pareto-optimal front that represents all possible trade-offs among the objectives of the teams. To solve MA-TC-PF, we propose two algorithms TC-CBS and TC-M*, which leverage the existing CBS and M* for conventional MA-PF. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front. We present numerical results for several types of MA-TC-PF problems.

Search and rescue applications often need multiple agents to complete a set of conflicting tasks. This paper studies a Multi-Agent Multi-Objective Ergodic Search (MA-MO-ES) approach to this problem where each objective or task is to cover a domain subject to an information map. The goal is to allocate coverage tasks to agents so that all maps are explored ergodically. The combinatorial nature of task allocation makes it computationally expensive to solve for optimal allocation using brute force. Apart from a large number of possible allocations, computing the cost of a task allocation is itself an expensive planning problem. To mitigate the computational challenge, we present a branch and bound-based algorithm with pruning techniques that reduce the number of allocations to be searched to find optimal coverage task allocation. We also present an approach to leverage the similarity between information maps to further reduce computation. Extensive testing on 147 randomly generated test cases shows an order of magnitude improvement in runtime compared to an exhaustive brute force approach.

Multi-Agent Path Finding (MA-PF) finds collision-free paths for multiple agents from their respective start to goal locations. This paper investigates a generalization of MA-PF called Multi-Agent Teamwise Cooperative Path Finding (MA-TC-PF), where agents are grouped as multiple teams and each team has its own objective to minimize. In general, there is more than one team, and MA-TC-PF is thus a multi-objective planning problem with the goal of finding the entire Pareto-optimal front that represents all possible trade-offs among the objectives of the teams. We show that the existing CBS and M* for MA-PF can be modified to solve MA-TC-PF, which is verified with tests. We discuss the conditions under which the proposed algorithms are complete and are guaranteed to find the Pareto-optimal front for MA-TC-PF.

Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. The goal of the problem is thus to find a Pareto-optimal set of solutions instead of a single optimal solution. Naively applying existing multi-objective search algorithms, such as multi-objective A* (MOA*), to multi-agent path finding may prove to be inefficient as the dimensionality of the search space grows exponentially with the number of agents. This article presents an approach named Multi-Objective Conflict-Based Search (MO-CBS) that attempts to address this so-called curse of dimensionality by leveraging prior Conflict-Based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We also develop several variants of MO-CBS to improve its performance. We prove that MO-CBS and its variants can compute the entire Pareto-optimal set. Numerical results show that MO-CBS outperforms MOM*, a recently developed state-of-the-art multi-objective multi-agent planner. Note to Practitioners—The motivation of this article originates from the need to optimize multiple path criteria when planning conflict-free paths for multiple mobile robots in applications such as warehouse logistics, surveillance, construction site routing, and hazardous material transportation. Existing methods for multi-agent planning typically consider optimizing a single path criteria. This article develops a novel multi-objective multi-agent planner as well as its variants that are guaranteed to find all Pareto-optimal solutions for the problem. We also provide an illustrative example of the algorithm to plan paths for multiple agents that transport materials in a construction site while optimizing both path length and risk. In this example, computing and visualizing a set of Pareto-optimal solutions makes it intuitive for the practitioner to understand the underlying trade-off between conflicting objectives and to choose the most preferred solution for execution based on their domain knowledge.

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.

Conventional multiagent path finding (MAPF) problems aim to compute an ensemble of collision-free paths for multiple agents from their respective starting locations to preallocated destinations. This article considers a generalized version of MAPF called multiagent combinatorial path finding, where agents must collectively visit a large number of intermediate target locations along their paths before arriving at destinations. This problem involves not only planning collision-free paths for multiple agents but also assigning targets and specifying the visiting order for each agent (i.e., target sequencing). To solve the problem, we leverage conflict-based search (CBS) for MAPF and propose a novel approach called conflict-based Steiner search (CBSS). CBSS interleaves 1) the collision resolution strategy in CBS to bypass the curse of dimensionality in MAPF and 2) multiple traveling salesman algorithms to handle the combinatorics in target sequencing, to compute optimal or bounded suboptimal paths for agents while visiting all the targets. We also develop two variants of CBSS that trade off runtime against solution optimality. Our test results verify the advantage of CBSS over the baselines in terms of computing cheaper paths and improving success rates within a runtime limit for up to 20 agents and 50 targets. Finally, we run both Gazebo simulation and physical robot tests to validate that the planned paths are executable.

Our work is motivated by humanitarian assistant and disaster relief (HADR) where often it is critical to find signs of life in the presence of conflicting criteria, objectives, and information. We believe ergodic search can provide a framework for exploiting available information as well as exploring for new information in applications, such as HADR. Existing ergodic search methods typically consider search using only a single information map. However, one can readily envision many scenarios where multiple information maps that encode different types of relevant information are used. Ergodic search methods currently do not possess the ability to simultaneously search multiple information maps, nor do they have a way to balance which information gets priority. This leads us to formulate a multiobjective ergodic search (MO-ES) problem, which aims to find the so-called Pareto-optimal solutions, for the purpose of providing human decision makers various solutions that trade off among conflicting criteria. To efficiently solve MO-ES, we develop a framework called sequential local ergodic search (SL-ES), which leverages the recent advances in ergodic search methods as well as the idea of local optimization to efficiently compute Pareto-optimal solutions. Our numerical results show that SL-ES computes solutions of better quality and runs faster than the baselines.

This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a "frontier" set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude.

Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. Naively applying existing multi-objective search algorithms to multi-agent path finding may prove to be inefficient as the size of the space of possible solutions, i.e., the Pareto-optimal set, can grow exponentially with the number of agents (the dimension of the search space). This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality by leveraging prior Conflict-based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We prove that MO-CBS is able to compute the entire Pareto-optimal set. Our results show that MO-CBS can solve problem instances with hundreds of Pareto-optimal solutions which the standard multi-objective A* algorithms could not find within a bounded time.

In multi-agent applications such as surveillance and logistics, fleets of mobile agents are often expected to coordinate and safely visit a large number of goal locations as efficiently as possible. The multi-agent planning problem in these applications involves allocating and sequencing goals for each agent while simultaneously producing conflict-free paths for the agents. In this article, we introduce a new algorithm called MS* which computes an optimal solution for this multi-agent problem by fusing and advancing state of the art solvers for multi-agent path finding (MAPF) and multiple travelling salesman problem (mTSP). MS* leverages our prior subdimensional expansion approach for MAPF and embeds the mTSP solvers to optimally allocate and sequence goals for agents. Numerical results show that our new algorithm can solve the multi-agent problem with 20 agents and 50 goals in a minute of CPU time on a standard laptop.

Multi-agent path finding (MAPF) determines an ensemble of collision-free paths for multiple agents between their respective start and goal locations. Among the available MAPF planners for workspace modeled as a graph, A*-based approaches have been widely investigated due to their guarantees on completeness and solution optimality, and have demonstrated their efficiency in many scenarios. However, almost all of these A*-based methods assume that each agent executes an action concurrently in that all agents start and stop together. This article presents a natural generalization of MAPF with asynchronous actions (MAPF-AA) where agents do not necessarily start and stop concurrently. The main contribution of the work is a proposed approach called Loosely Synchronized Search (LSS) that extends A*-based MAPF planners to handle asynchronous actions. We show LSS is complete and finds an optimal solution if one exists. We also combine LSS with other existing MAPF methods that aims to trade-off optimality for computational efficiency. Numerical results are presented to corroborate the performance of LSS and the applicability of the proposed method is verified in the Robotarium, a remotely accessible swarm robotics research platform.

Search-based planning that uses a state lattice has been successfully applied in many applications but its utility is limited when confronted with complex problems represented by a lattice with many nodes and edges with high branching factor. However, in many seemingly complex problems, proper “form-fitting” can reduce the number of nodes and edges needed to represent the problems, provides a concise state lattice and therefore simplifies the computation. This paper proposes a planning framework which strikes to identify concise representations of problems, creates such “form-fitting” state lattice on which a more concise search can take place. In a sense, we take a conventional state lattice and map it onto a deformed space, and then the motion primitives and heuristics follow. Since the contribution of the paper is not the search approach but rather the means by which the lattice is deformed, any search-based planner can then be easily changed to a corresponding deformed version with no increase in time complexity. This paper demonstrate the benifits of the approach which includes 1) planned path can be followed with few changes in motion primitives and thus can provide global smoothness of planned path; 2) fewer states are expanded and thus shorter time to search solution in state space is required, and 3) fewer states are expanded and thus less memory is required to save the state lattice. We demonstrate the benefit of the proposed approach in illustrative toy examples, as well as robot experiments.