This article investigates the reliable navigation problem, which requires that the ego vehicle navigates itself to the destination with the maximized stochastic on-time arrival (SOTA) probability in a givenuncertaintopological transportation network. One distinctive characteristic of the SOTA problem explored in this paper is the inherent uncertainty stemming from the underlying network's topology, i.e., some of the edges might become untraversable during navigation. To the best of our knowledge, almost all conventional SOTA solutions presume that the network topology remains the same during the ego vehicle's navigation process. However, when facing uncertainties in the network's topology, these algorithms may experience a significant performance degradation. To address the challenge of uncertain network topology, we first formulate the special reliable navigation problem into thevariationalMarkov decision process (MDP) framework, and then initiate a new reinforcement learning (RL)-based algorithm, namely sample efficient variational actor critic (SEVAC) as its solution. SEVAC comprises the variational policy gradient (VPG) module, which optimizes the vehicle's routing policy, and the masked temporal difference (MTD) module, which approximates the underlying routing policy's SOTA probability. Both modules are extended to their off-policy counterparts, namely off-policy VPG and off-policy MTD, to improve the algorithm's sample efficiency. SEVAC is compared with several conventional SOTA solutions as well as Canadian traveller problem (CTP) algorithms in a variety of commonly used transportation test networks, and achieves the best overall SOTA performance. Furthermore, we validate SEVAC's application to real-world scenarios by navigating a physical robot in a self-constructed indoor environment as well as a real-world building environment with uncertain topology.

Multi-robot navigation in complex environments relies on inter-robot communication and mutual observation for situational awareness. This paper studies the multi-robot navigation problem in unknown environments with line-ofsight (LoS) connectivity constraints. While previous works are limited to known environment models to derive the LoS constraints between robots, this paper eliminates such requirements by directly formulating the LoS constraints from realtime LiDAR scans, adopting techniques in point cloud visibility analysis. Based on that, we propose a novel LoS-distance metric to quantify both the urgency and sensitivity of losing LoS between robots considering their potential movements. Moreover, to address the imbalanced urgency of losing LoS between two robots, we design a fusion function to capture the overall urgency while generating gradients that facilitate robots' collaborative behavior to maintain LoS. The team connectivity is guaranteed by encoding the LoS constraints into a potential function that preserves the positivity of the Fiedler eigenvalue of robots' underlying graph. Finally, we establish a LoS-constrained exploration framework integrating the proposed connectivity controller. We showcase its applications in multi-robot exploration in complex unknown environments, where robots can always maintain the LoS connectivity through distributed sensing and communication while collaboratively exploring unknown environments. Our implementations are available at https://github.com/bairuofei/LoS_constrained_navigation.

This paper investigates theresilientmulti-robot efficient search problem (R-MuRES), which aims at coordinating multiple robots to detect a ‘non-adversarial’ moving target with the minimal expected time. One unique characteristic of R-MuRES among others is the possibility of individual robot's malfunction and withdrawal from the team during task execution, which results in avariablenumber of searchers in the deployment phase and entails that the possibility of team member failures must be considered during the planning stage, particularly in the training phase. We propose a resilient value function factorization (R-FAC) paradigm, which constructs the central value function from individual ones in a resilient manner, taking into account individual robots' failures, and ensures that the constructed central value function has the minimal mean squared temporal difference error across various team compositions. R-FAC stipulates that the individual global maximum (IGM) principle is satisfied for whichever team configuration and thus any functioning robot contributes positively to the remaining team, as long as it executes the greedy policy with respect to the factorized individual value function. Subsequently, we introduce thevariationalvalue decomposition network (V2DN) as one of the instantiated R-FAC algorithms. V2DN employs the$\log$-sum-$\exp$mechanism to construct the central value function from individual ones, enabling it to take a varying number of robots' individual value functions as inputs. Then, we explain why, specifically for the multi-robot search task, the$\log$-sum-$\exp$mechanism is superior to the brute-force summation operation used in the canonical value decomposition network (VDN), and compare V2DN with state-of-the-art MuRES solutions as well as the vanilla VDN algorithm in two canonical MuRES testing environments and show that it achieves the best resiliency score when one or several individual robots quit the team during task execution. Furthermore, we validate V2DN with a real multi-robot system in a self-constructed indoor environment as the proof of concept.

This paper considers the multi-robot active graph exploration problem, where robots need to collaboratively cover a graph environment while maintaining reliable pose estimation in collaborative Simultaneous Localization and Mapping (SLAM). Considering both objectives presents challenges for multi-robot pathfinding, as it involves the expensive covariance propagation for SLAM uncertainty evaluation, especially when considering various combinations of robots’ paths. To reduce the computational complexity, we propose an efficient two-stage strategy where exploration paths are first generated for quick coverage, and then enhanced by adding informative loop-closing actions along the paths for reliable pose estimation. We formulate the latter problem as a non-monotone submodular maximization problem by relating SLAM uncertainty with pose graph topology, which (1) facilitates a more efficient evaluation of SLAM uncertainty than covariance inference, and (2) allows the employment of approximation algorithms in submodular optimization to provide suboptimality guarantees. We further introduce ordering heuristics to improve the objective values while preserving the optimality bound. Simulation experiments over randomly generated graph environments verify the effectiveness of our methods to achieve quick coverage and enhanced pose graph reliability, and benchmark the performance of the approximation algorithms and the greedy-based algorithm in the loop edge selection problem. Our implementations will be open-source at https://github.com/bairuofei/CGE.

Recent advances in multi-agent reinforcement learning (MARL) have significantly enhanced cooperation capabilities within multi-robot teams. However, the application to heterogeneous teams poses the critical challenge of combinatorial generalization—adapting learned policies to teams with new compositions of varying sizes and robots capabilities. This challenge is paramount for dynamic real-world scenarios where teams must swiftly adapt to changing environmental and task conditions. To address this, we introduce a novel transformer-based MARL method for heterogeneous multirobot cooperation. Our approach leverages graph neural networks and self-attention mechanisms to effectively capture the intricate dynamics among heterogeneous robots, facilitating policy adaptation to team size variations. Moreover, by treating robot team decisions as sequential inputs, a capability-oriented decoder is introduced to generate actions in an auto-regressive manner, enabling decentralized decision-making that tailored each robot’s varying capabilities and heterogeneity type. Furthermore, we evaluate our method across two heterogeneous cooperation scenarios in both simulated and real-world environments, featuring variations in team number and robot capabilities. Comparative results reveal our method’s superior generalization performance compared to existing MARL methodologies, marking its potential for real-world multi-robot applications.

This paper studies the problem in transportation networks and introduces a novel reinforcement learning-based algorithm, namely. Different from almost all canonical sota solutions, which are usually computationally expensive and lack generalizability to unforeseen destination nodes, segac offers the following appealing characteristics. segac updates the ego vehicle’s navigation policy in a sample efficient manner, reduces the variance of both value network and policy network during training, and is automatically adaptive to new destinations. Furthermore, the pre-trained segac policy network enables its real-time decision-making ability within seconds, outperforming state-of-the-art sota algorithms in simulations across various transportation networks. We also successfully deploy segac to two real metropolitan transportation networks, namely Chengdu and Beijing, using real traffic data, with satisfying results.

This article studies the multirobot efficient search (MuRES) for a nonadversarial moving target problem, whose objective is usually defined as either minimizing the target's expected capture time or maximizing the target's capture probability within a given time budget. Different from canonical MuRES algorithms, which target only one specific objective, our proposed algorithm, named distributional reinforcement learning-based searcher (DRL-Searcher), serves as a unified solution to both MuRES objectives. DRL-Searcher employs distributional reinforcement learning (DRL) to evaluate the full distribution of a given search policy's return, that is, the target's capture time, and thereafter makes improvements with respect to the particularly specified objective. We further adapt DRL-Searcher to the use case without the target's real-time location information, where only the probabilistic target belief (PTB) information is provided. Lastly, the recency reward is designed for implicit coordination among multiple robots. Comparative simulation results in a range of MuRES test environments show the superior performance of DRL-Searcher to state of the arts. Additionally, we deploy DRL-Searcher to a real multirobot system for moving target search in a self-constructed indoor environment with satisfying results.

Autonomous driving in the rain remains a challenge. One main problem is performance degradation caused by rain. This work introduces a new dataset to study this problem. Our dataset is collected from a full-scale vehicle equipped with a 3D LiDAR sensor and multiple forward-facing cameras under various rainy conditions. In addition, rainfall intensity is recorded in real-time from a rain sensor. The combination of sensor and rainfall intensity measurement is designed for studying algorithm performance under different levels of rainfall. In this work, in addition to presenting dataset creation details, we also introduce three degradation evaluation tasks with baseline results, including rainfall intensity estimation, LiDAR degradation estimation, and 2D object detection evaluation. This dataset, development kit, and baseline codes will be made available at https://smart-rain-dataset.github.io/

This paper studies the reliable shortest path (RSP) problem in stochastic transportation networks. State-of-the-art RSP solutions usually target one specific RSP problem; moreover, the corresponding algorithm’s computational complexity scales at least linearly with the size of the underlying transportation network. While in this paper, we propose a graph embedding and deep distributional reinforcement learning (GE-DDRL) method, which serves as a universal and scale-free solution to the RSP problem. GE-DDRL uses deep distributional reinforcement learning (DDRL) to estimate the full travel-time distribution of a given routing policy, and improves the given routing policy with the generalized policy iteration (GPI) scheme. Further, in order to achieve the generalization ability to new destination nodes, we employ one of the canonical graph embedding techniques (Skip-Gram) to compress the nodes’ representation into$d$-dimensional real-valued vectors. With the properly compressed node features, GE-DDRL is able to generalize its estimation of the routing policy’s travel-time distribution to untrained destination nodes, and hence achieve the ‘all-to-all’ navigation functionality. To the best of our knowledge, GE-DDRL serves as the first RSP planner, which applies simultaneously to almost all RSP objectives and in the meanwhile, is scale free with the size of the transportation network in terms of the online decision-making time and memory complexity. Experimental results and comparisons with state of the arts show the efficacy and efficiency of GE-DDRL in a range of transportation networks.

This article investigates the multirobot efficient search (MuRES) for a nonadversarial moving target problem from the multiagent reinforcement learning (MARL) perspective. MARL is deemed as a promising research field for cooperative multiagent applications. However, one of the main bottlenecks of applying MARL to the MuRES problem is the nonstationarity introduced by multiple learning agents. With learning agents simultaneously updating their policies, the environment cannot be modeled as astationaryMarkov decision process, which results in the inapplicability of fundamental reinforcement learning techniques such as deep$Q$-network and policy gradient (PG). In view of that, we adopt the centralized training and decentralized execution scheme and thereby propose a cross-entropy regularized policy gradient (CE-PG) method to train the learning agents/robots. We let the robotscommitto a predetermined policy during execution, collect the trajectories, and then perform centralized training for the corresponding policy improvement. In this way, the nonstationarity problem is overcome, in that the robots do not update their policies during execution. During the centralized training stage, we improve the canonical PG method to consider the interactions among robots by adding a cross-entropy regularization term, which essentially functions to “disperse” the robots in the environment. Extensive simulation results and comparisons with state of the art show CE-PG's superior performance, and we also validate the algorithm with a real multirobot system in an indoor moving target search scenario.

This paper investigates the reliable shortest path (RSP) problem in Gaussian process (GP) regulated transportation networks. Specifically, the RSP problem that we are targeting at is to minimize the (weighted) linear combination of mean and standard deviation of the path’s travel time. With the reasonable assumption that the travel times of the underlying transportation network follow a multi-variate Gaussian distribution, we propose a Gaussian process path planning (GP3) algorithm to calculate the a priori optimal path as the RSP solution. With a series of equivalent RSP problem transformations, we are able to reach a polynomial time complexity algorithm with guaranteed solution accuracy. Extensive experimental results over various sizes of realistic transportation networks demonstrate the superior performance of GP3 over the state-of-the-art algorithms.

This paper investigates the stochastic on-time arrival (SOTA) problem in transportation networks. We propose a fourth moment approach (FMA), which calculates the tight lower bound of a given routing policy’s on-time-arrival probability, through estimating the first four moments of the policy’s travel time. Then, we employ the generalized policy iteration (GPI) scheme to gradually improve the policy towards the optimal one. Different from state-of-the-art algorithms for the SOTA problem, which require the full travel time distribution and usually incur high computational cost due to the convolution integration operation, FMA only requires the moments of travel-time statistics, which are easily estimated from the statistics perspective. Moreover, the algorithm’s computational complexity analysis indicates the relatively light computational load requirement of FMA. Experimental results in a range of transportation networks show FMA’s superior performance over state of the arts.

This paper investigates the reliable shortest path (RSP) planning problem from the reinforcement learning perspective. Different from canonical path planning methods, which require at least the first- order statistic (mean) and second-order statistic (variance) information of travel time distribution, we target at the RSP planning problem without the assumption of knowing any travel time distribution characteristic beforehand, and propose a cascaded temporal difference learning (CTD) method, which simultaneously estimates the mean and variance of the executing path and thereby gradually makes improvements through the generalized policy iteration (GPI) scheme, as the ego vehicle interacts with the environment. Extensive simulation results demonstrate the applicability of the proposed method for RSP learning in various transportation networks.

This paper addresses the safe path planning problem for autonomous mobility with multi-modal perception uncertainties. Specifically, we assume that different sensor inputs lead to different Gaussian process regulated perception uncertainties (named as multi-modal perception uncertainties). We implement a Bayesian inference algorithm, which merges the multi-modal GP-regulated uncertainties into a unified one and translates the unified uncertainty into a dynamic risk map. With the safe path planner taking the risk map as input, we are able to plan a safe path for the autonomous vehicle to follow. Experimental results on an autonomous golf cart testbed validate the applicability and efficiency of the proposed algorithm.

Navigation through dynamic pedestrian environments in a socially compliant manner is still a challenging task for autonomous vehicles. Classical methods usually lead to unnatural vehicle behaviours for pedestrian navigation due to the difficulty in modeling social conventions mathematically. This paper presents an end-to-end path planning system that achieves autonomous navigation in dynamic environments through imitation learning. The proposed system is based on a fully convolutional neural network that maps the raw sensory data into a confidence map for path extraction. Additionally, a classification network is introduced to reduce the unnecessary re-plannings and ensures that the vehicle goes back to the global path when re-planning is not needed. The imitation learning based path planner is implemented on an autonomous wheelchair and tested in a new real-world dynamic pedestrian environment. Experimental results show that the proposed system is able to generate paths for different driving tasks, such as pedestrian following, static and dynamic obstacles avoidance, etc. In comparison to the state-of-the-art method, our system is superior in terms of generating human-like trajectories.

This paper studies the group multi-object tracking (MOT) problem in dynamic pedestrian environments, with intended application to safe navigation for autonomous vehicles. We complete a full autonomous vehicle navigation pipeline from object detection, tracking, grouping, to risk map generation and safe path planning. Our main contribution is to instantiate a group multi-object tracking algorithm, which provides the crucial grouped activity information, i.e. group position, group velocity, group size, to the risk map generator, and therewith produce a stable and robust risk map for the downstream safe path planner. Experimental results with real world data show the socially acceptable, robust and stable performance of the proposed algorithm over its individual MOT counterpart.

This paper investigates the safe path planning problem for an autonomous vehicle operating in unstructured, cluttered environments. While some objects may be accurately with canonical perception algorithms, other objects and clutter may be harder to track. We present an approach that combines two methods of risk assessment: for objects with reliable tracking, we use a Gaussian Process (GP) regulated risk map to describe the risk map information; for unknown objects that we fail to accurately track, we compute a Dynamic Risk Density (DRD) from the overall occupancy and velocity field from LiDAR scan snapshots. Several methods are proposed for combining the GP risk map and DRD, and the resultant hybrid risk map is used for the proposed safe path planning algorithm. Experimental results on an autonomous buggy show that the hybrid risk map is able to yield a safe path planner to navigate the autonomous testbed within the cluttered environments.

Government data identifies driver behaviour errors as a factor in 94% of car crashes, and autonomous vehicles (AVs), which avoids risky driver behaviours completely, are expected to reduce the number of road crashes significantly. Thus, one of the central focuses of developing AVs is to ensure safety during navigation. However, in reality, AV safety has been far below its expectation, and so far, no government has allowed for complete autonomous driving without human supervision. This paper proposes a dynamic safe path planning algorithm for AVs with Gaussian process regulated risk map. By reasonably assuming that the output of the object detection and tracking module follows a multi-variate Gaussian distribution, we put forward a safe path planning paradigm with Gaussian process regulated risk map, ensuring safety with high confidence. Both simulation results and in-vehicle tests demonstrate the effectiveness of the proposed algorithm.

Arriving on time and total travel time are two important properties for vehicle routing. Existing route guidance approaches always consider them independently, because they may conflict with each other. In this article, we develop a semi-decentralized multiagent-based vehicle routing approach where vehicle agents follow the local route guidance by infrastructure agents at each intersection, and infrastructure agents perform the route guidance by solving a route assignment problem. It integrates the two properties by expressing them as two objective terms of the route assignment problem. Regarding arriving on time, it is formulated based on the probability tail model, which aims to maximize the probability of reaching destination before deadline. Regarding total travel time, it is formulated as a weighted quadratic term, which aims to minimize the expected travel time from the current location to the destination based on the potential route assignment. The weight for total travel time is designed to be comparatively large if the deadline is loose. Additionally, we improve the proposed approach in two aspects, including travel time prediction and computational efficiency. Experimental results on real road networks justify its ability to increase the average probability of arriving on time, reduce total travel time, and enhance the overall routing performance.

The stochastic shortest path problem is of crucial importance for the development of sustainable transportation systems. Existing methods based on the probability tail model seek for the path that maximizes the probability of arriving at the destination before a deadline. However, they suffer from low accuracy and/or high computational cost. We design a novel Q-learning method where the converged Q-values have the practical meaning as the actual probabilities of arriving on time so as to improve accuracy. By further adopting dynamic neural networks to learn the value function, our method can scale well to large road networks with arbitrary deadlines. Experimental results on real road networks demonstrate the significant advantages of our method over other counterparts.

As the number of vehicles grows rapidly each year, more and more traffic congestion occurs, becoming a big issue for civil engineers in almost all metropolitan cities. In this paper, we propose a novel pheromone-based traffic management framework for reducing traffic congestion, which unifies the strategies of both dynamic vehicle rerouting and traffic light control. Specifically, each vehicle, represented as an agent, deposits digital pheromones over its route, while roadside infrastructure agents collect the pheromones and fuse them to evaluate real-time traffic conditions as well as to predict expected road congestion levels in near future. Once road congestion is predicted, a proactive vehicle rerouting strategy based on global distance and local pheromone is employed to assign alternative routes to selected vehicles before they enter congested roads. In the meanwhile, traffic light control agents take online strategies to further alleviate traffic congestion levels. We propose and evaluate two traffic light control strategies, depending on whether or not to consider downstream traffic conditions. The unified pheromone-based traffic management framework is compared with seven other approaches in simulation environments. Experimental results show that the proposed framework outperforms other approaches in terms of traffic congestion levels and several other transportation metrics, such as air pollution and fuel consumption. Moreover, experiments over various compliance and penetration rates show the robustness of the proposed framework.

Transportation and mobility are central to sustainable urban development, where multiagent-based route guidance is widely applied. Traditional multiagent-based route guidance always seeks LET (least expected travel time) paths. However, drivers usually have specific expectations, i.e., tight or loose deadlines, which may not be all met by LET paths. We thus adopt and extend the probability tail model that aims to maximize the probability of reaching destinations before deadlines. Specifically, we propose a decentralized multiagent approach, where infrastructure agents locally collect intentions of concerned vehicle agents and formulate route guidance as a route assignment problem, to guarantee their arrival on time. Experimental results on real road networks justify its ability to increase the chance of arrival on time.

This paper aims at solving the stochastic shortest path problem in vehicle routing, the objective of which is to determine an optimal path that maximizes the probability of arriving at the destination before a given deadline. To solve this problem, we propose a data-driven approach, which directly explores the big data generated in traffic. Specifically, we first reformulate the original shortest path problem as a cardinality minimization problem directly based on samples of travel time on each road link, which can be obtained from the GPS trajectory of vehicles. Then, we apply an ℓ1-norm minimization technique and its variants to solve the cardinality problem. Finally, we transform this problem into a mixed-integer linear programming problem, which can be solved using standard solvers. The proposed approach has three advantages over traditional methods. First, it can handle various or even unknown travel time probability distributions, while traditional stochastic routing methods can only work on specified probability distributions. Second, it does not rely on the assumption that travel time on different road segments is independent of each other, which is usually the case in traditional stochastic routing methods. Third, unlike other existing methods which require that deadlines must be larger than certain values, the proposed approach supports more flexible deadlines. We further analyze the influence of important parameters to the performances, i.e., accuracy and time complexity. Finally, we implement the proposed approach and evaluate its performance based on a real road network of Munich city. With real traffic data, the results show that it outperforms traditional methods.

Embryonic development of multicellular organisms, also known as morphogenesis, is regarded as a robust self-organization process for pattern generation. Inspired by the recent findings in biology indicating that morphogen gradients, together with a Gene Regulatory Network (GRN), play a key role in biological patterning, we propose a framework for self-organized multirobot pattern formation and boundary coverage based on an artificial GRN model. The proposed framework does not need a global coordinate system, which makes it more practical to be implemented in a physical robotic system. Moreover, an adaptation mechanism is included in the framework so that the self-organization algorithm is robust to changes in the number of robots. Various case studies of multirobot pattern formation and boundary coverage show the effectiveness of the framework.

Most existing multirobot systems for pattern formation rely on a predefined pattern, which is impractical for dynamic environments where the pattern to be formed should be able to change as the environment changes. In addition, adaptation to environmental changes should be realized based only on local perception of the robots. In this paper, we propose a hierarchical gene regulatory network (H-GRN) for adaptive multirobot pattern generation and formation in changing environments. The proposed model is a two-layer gene regulatory network (GRN), where the first layer is responsible for adaptive pattern generation for the given environment, while the second layer is a decentralized control mechanism that drives the robots onto the pattern generated by the first layer. An evolutionary algorithm is adopted to evolve the parameters of the GRN subnetwork in layer 1 for optimizing the generated pattern. The parameters of the GRN in layer 2 are also optimized to improve the convergence performance. Simulation results demonstrate that the H-GRN is effective in forming the desired pattern in a changing environment. Robustness of the H-GRN to robot failure is also examined. A proof-of-concept experiment using e-puck robots confirms the feasibility and effectiveness of the proposed model.

Inspired by the major principles of gene regulation and cellular interactions in multi-cellular organism's development, we propose a distributed self-organizing algorithm for swarm robot pattern formation. In this approach, swarm robots are able to self-organize themselves into complex shapes driven by the dynamics of a gene regulatory network based model. This is a distributed approach, since only local interaction is needed for each robot to make decisions during shape formation without any global controller. The target shape is represented by the non-uniform rational B-spline (NURBS) and embedded into the gene regulation model, analogous to the morphogen gradients in morphogenesis. Since the self-organization algorithm does not need a global coordinate system, the target shape can be formed anywhere within the environment based on the current distribution of the robots. Simulation and experimental results demonstrate that the proposed algorithm is effective for complex shape construction and robust to environmental changes and system failures.

Morphogenesis is the biological process that governs self-organized spatial pattern formation of cells during the embryonic development of multi-cellular organisms. Inspired by this process, we have proposed a morphogenetic framework for pattern formation and boundary coverage in a distributed swarm robotic system. The framework is based only on local communications among robots and will set up a local coordinate system. This paper focuses on the theoretical and empirical analysis of the framework regarding two aspects, namely, local communication load among the robots, and system performance such as system convergence time and average travel distance of robots for several pattern formation tasks. Results show that the proposed framework is efficient and scalable for self-organizing distributed swarm robotic systems with reasonable local communication load among robots.

Biological organisms have evolved to perform and survive in a world characterized by rapid changes, high uncertainty, infinite richness, and limited availability of information. Gene regulatory networks (GRNs) are models of genes and gene interactions at the expression level. In this paper, inspired by the biological organisms and GRNs models, a distributed multi-robot self-construction method is proposed. By using this method, a multi-robot system can self-construct to different predefined shapes, and self-reorganize to adapt to dynamic environments. Various case studies have been conducted in the simulation, and the simulation results demonstrate the efficiency and convergence of the proposed method.