In this paper, we study the “Multi-Robot Routing problem” with min–max objective (MRR-MM) in detail. It involves the assignment of sequentially ordered tasks to robots such that the maximum cost of the slowest robot is minimized. The problem description, the different types of formulations, and the methods used across various research communities are discussed in this paper. We propose a new problem formulation by treating this problem as a bipartite graph with a permutation matrix to solve it. A comparative study is done between three methods: Stochastic simulated annealing, deterministic mean-field annealing, and a heuristic-based graph search method. Each method is investigated in detail with several data sets (simulation and real-world), and the results are analysed and compared with respect to scalability, computational complexity, optimality, and its application to real-world scenarios. The paper shows that the heuristic method produces results very quickly with good scalability. However, the solution quality is sub-optimal. On the other hand, when optimal or near-optimal results are required with considerable computational resources, the simulated annealing method proves to be more efficient. However, the results show that the optimal choice of algorithm depends on the dataset size and the available computational budget. The contribution of the paper is three-fold: We study the MRR-MM problem in detail across various research communities. This study also shows the lack of inter-research terminology that has led to different names for the same problem. Secondly, formulating the task allocation problem as a permutation matrix formulation (bipartite graph) has opened up new approaches to solve this problem. Thirdly, we applied our problem formulation to three different methods and conducted a detailed comparative study using real-world and simulation data. © 2021 by the authors.

A deterministic annealing (DA) method is presented for solving the multi-robot routing problem with min–max objective. This is an NP-hard problem belonging to the multi-robot task allocation set of problems where robots are assigned to a group of sequentially ordered tasks such that the cost of the slowest robot is minimized. The problem is first formulated in a matrix form where the optimal solution of the problem is the minimum-cost permutation matrix without any loops. The solution matrix is then found using the DA method is based on mean field theory applied to a Potts spin model which has been proven to yield near-optimal results for NP-hard problems. Our method is bench-marked against simulated annealing and a heuristic search method. The results show that the proposed method is promising for small-medium sized problems in terms of computation time and solution quality compared to the other two methods. © The Author(s) 2022

This paper discusses the possibilities of extending and adapting the CHOMP motion planner to work with a non-holonomic vehicle such as an autonomous truck with a single trailer. A detailed study has been done to find out the different ways of implementing these constraints on the motion planner. CHOMP, which is a successful motion planner for articulated robots produces very fast and collision-free trajectories. This nature is important for a local path adaptor in a multi-vehicle path planning for resolving path-conflicts in a very fast manner and hence, CHOMP was adapted. Secondly, this paper also details the experimental integration of the modified CHOMP with the sensor fusion and control system of an autonomous Volvo FH-16 truck. Integration experiments were conducted in a real-time environment with the developed autonomous truck. Finally, additional simulations were also conducted to compare the performance of the different approaches developed to study the feasibility of employing CHOMP to autonomous vehicles. ©2017 IEEE

Recently, functional gradient algorithms like CHOMP have been very successful in producing locally optimal motion plans for articulated robots. In this paper, we have adapted CHOMP to work with a non-holonomic vehicle such as an autonomous truck with a single trailer and a differential drive robot. An extended CHOMP with rolling constraints have been implemented on both of these setup which yielded feasible curvatures. This paper details the experimental integration of the extended CHOMP motion planner with the sensor fusion and control system of an autonomous Volvo FH-16 truck. It also explains the experiments conducted on the differential-drive robot. Initial experimental investigations and results conducted in a real-world environment show that CHOMP can produce smooth and collision-free trajectories for mobile robots and vehicles as well. In conclusion, this paper discusses the feasibility of employing CHOMP to mobile robots. © 2018, Springer International Publishing AG.

We consider the problem of finding collision-free trajectories for a fleet of automated guided vehicles (AGVs) working in ship ports and freight terminals. Our solution computes collision-free trajectories for a fleet of AGVs to pick up one or more containers and transport it to a given goal without colliding with other AGVs and obstacles. We propose an integrated framework for solving the goal assignment and trajectory planning problem minimizing the maximum cost overall vehicle trajectories using the classical Hungarian algorithm.To deal with the dynamics in the environment, we refine our final trajectories with CHOMP (Covariant Hamiltonianoptimization for motion planning) in order to trade off between path smoothness and dynamic obstacle avoidance.

This paper addresses the challenge of coordinating task allocation and generating collision-free trajectories for a fleet of mobile robots in dynamic environments. Our approach introduces an integrated framework comprising a centralized task allocation system and a distributed trajectory planner. The centralized task allocation system, employing a heuristic approach, aims to minimize the maximum spatial cost among the slowest robots. Tasks and trajectories are continuously refined using a distributed version of CHOMP (Covariant Hamiltonian Optimization for Motion Planning), tailored for multiple-wheeled mobile robots where the spatial costs are derived from a high-level global path planner. By employing this combined methodology, we are able to achieve near-optimal solutions and collision-free trajectories with computational performance for up to 50 robots within seconds. © 2025 the authors.