Some real-world transportation systems require moving robots from their start points to goal points without collision, which can be formalized as the multi-agent pathfinding (MAPF) problem. The Priority Inheritance with Backtracking (PIBT) algorithm is an efficient approach for MAPF with low-degree polynomial time complexity and proven completeness. PIBT employs a dynamic prioritization scheme to determine the order of sequential agent planning. However, this scheme may lead to low solution quality, which is measured by the sum of time steps each agent takes to reach its goal for the first time. In this work, we propose two greedy variants of the PIBT algorithm that improve solution quality while preserving completeness: Backflow-based Greedy PIBT (GPIBT-B) and Reduction-based Greedy PIBT (GPIBT-R). GPIBT-B introduces a backflow mechanism that allows a determined agent to adjust its plan during the planning of another agent, achieving higher solution quality while maintaining the same low time complexity as PIBT. GPIBT-R formulates the planning problem as a Mixed-Integer Linear Programming (MILP), enabling the use of efficient MILP solvers to find high-quality solutions. Experimental results show that GPIBT-B substantially improves solution quality with minimal additional computation time, while GPIBT-R achieves even better solution quality at the cost of increased computational time.

The task of the multi-agent pathfinding (MAPF) problem is to navigate a team of agents from their start point to the goal points. However, this setup is unsuitable in the assembly line scenario, which is periodic with a long working hour. To address this issue, the study formalizes the streaming MAPF (S-MAPF) problem, which assumes that the agents in the same agent stream have a periodic start time and share the same action sequence. The proposed solution, Agent Stream Conflict-Based Search (ASCBS), is designed to tackle this problem by incorporating a cyclic vertex/edge constraint to handle conflicts. Additionally, this work explores the potential usage of the disjoint splitting strategy within ASCBS. Experimental results indicate that ASCBS surpasses traditional MAPF solvers in terms of runtime for scenarios with prolonged working hours.

Considerable research efforts have been devoted to the development of motion planning algorithms, which form a cornerstone of the autonomous driving system (ADS). Nonetheless, acquiring an interactive and secure trajectory for the ADS remains challenging due to the complex nature of interaction modeling in planning. Modern planning methods still employ a uniform treatment of prediction outcomes and solely rely on collision-avoidance strategies, leading to suboptimal planning performance. To address this limitation, this paper presents a novel prediction-based interactive planning framework for autonomous driving. Our method incorporates interaction reasoning into spatio-temporal (s-t) planning by defining interaction conditions and constraints. Specifically, it records and continually updates interaction relations for each planned state throughout the forward search. We assess the performance of our approach alongside state-of-the-art methods in the CommonRoad environment. Our experiments include a total of 232 scenarios, with variations in the accuracy of prediction outcomes, modality, and degrees of planner aggressiveness. The experimental findings demonstrate the effectiveness and robustness of our method. It leads to a reduction of collision times by approximately 17.6% in 3-modal scenarios, along with improvements of nearly 7.6% in distance completeness and 31.7% in the fail rate in single-modal scenarios. For the community’s reference, our code is accessible at https://github.com/ChenYingbing/IR-STP-Planner.

Real-time kinodynamic trajectory planning in dy-namic environments is critical yet challenging for autonomous driving. In this paper, we propose an efficient trajectory plan-ning system for autonomous driving in complex dynamic sce-narios through iterative and incremental path-speed optimization. Exploiting the decoupled structure of the planning prob-lem, a path planner based on Gaussian process first generates a continuous arc-length parameterized path in the Frenét frame, considering static obstacle avoidance and curvature constraints. We theoretically prove that it is a good generalization of the well-known jerk optimal solution. An efficient s-t graph search method is introduced to find a speed profile along the generated path to deal with dynamic environments. Finally, the path and speed are optimized incrementally and iteratively to ensure kinodynamic feasibility. Various simulated scenarios with both static obstacles and dynamic agents verify the effectiveness and robustness of our proposed method. Experimental results show that our method can run at 20 Hz. The source code is released as an open-source package.

Road network graphs provide critical information for autonomous-vehicle applications, such as drivable areas that can be used for motion planning algorithms. To find road network graphs, manual annotation is usually inefficient and labor-intensive. Automatically detecting road network graphs could alleviate this issue, but existing works still have some limitations. For example, segmentation-based approaches could not ensure satisfactory topology correctness, and graph-based approaches could not present precise enough detection results. To provide a solution to these problems, we propose a novel approach based on transformer and imitation learning in this article. In view of that high-resolution aerial images could be easily accessed all over the world nowadays, we make use of aerial images in our approach. Taken as input an aerial image, our approach iteratively generates road network graphs vertex-by-vertex. Our approach can handle complicated intersection points with various numbers of incident road segments. We evaluate our approach on a publicly available dataset. The superiority of our approach is demonstrated through comparative experiments. Our work is accompanied by a demonstration video which is available athttps://tonyxuqaq.github.io/projects/RNGDet/.

Due to the simplicity of its implementation and the impressive performance, Extreme Learning Machine (ELM) has been widely used in applications of machine learning. However, there are two potential problems in ELM: 1) lack of an efficient method for minimizing error; 2) consideration of little inherent structural information about correlations among output components. To overcome those problems, this paper proposes two improvements of ELM: Optimal Distribution Extreme Learning Machine (OD-ELM) and Space Embedded Extreme Learning Machine (SE-ELM). Based on our recent discovery that the distributions of the input weights and the bias of hidden nodes in ELM play an important role in the performance of ELM, OD-ELM can reduce the training error by the usage of the derivatives of training error w.r.t the distributions. Simulation results tested on the UCI dataset demonstrate and verify that OD-ELM has better generalization performance than traditional ELM. SE-ELM can `embed' the inherent structural information among outputs into the predictor. SE-ELM captures not only the interdependencies between variables, as in a typical ELM, but also those responses, so correlations among both inputs and outputs are considered. Meanwhile, SE-ELM retains some characteristics of ELM, such as the simplicity of implementation and the hidden layer without tuning. We examine the three methods of embedding on HumanEva benchmark, which is a well-known benchmark about 3D human pose reconstruction. As verified by the simulation results, SE-ELM tends to have better generalization performance than classical ELM.

The triplet Markov fields (TMF) model is suitable for dealing with nonstationary synthetic aperture radar (SAR) images. Existing optimization approaches for the TMF model cannot balance segmentation accuracy and computational efficiency. Focusing on efficient optimization of the TMF model, we propose an unsupervised SAR image segmentation algorithm based on TMF with graph cuts (GCs) in this letter. Considering the existence of two label fields in the TMF model, an iterative optimization strategy under the criterion of maximum a posteriori is proposed, which iteratively estimates one label field with the other fixed. GCs are is used to find the optimal estimation of each label field. GCs optimization and parameter estimation using iterative conditional estimation perform iteratively, leading to an unsupervised segmentation algorithm. Experiments on simulated and real SAR images demonstrate that the proposed algorithm can obtain accurate segmentation results with reasonable computational cost.

The triplet Markov field (TMF) model recently proposed is suitable for dealing with nonstationary synthetic aperture radar (SAR) image segmentation. In this letter, we propose a multiscale TMF model in wavelet domain, named as the wavelet-domain TMF (WTMF) model. In the WTMF model, a multiscale causal WTMF energy function is constructed to capture the intra- and interscale dependences in random fields$(X, U)$. Moreover, multiscale likelihoods of the WTMF model are derived based on a wavelet hidden Markov tree to capture the statistical properties of wavelet coefficients. The proposed model can integrate the global and local information in terms of spatial configuration and image features in a more complete manner. The coarser scale information is utilized to guide the finer scale segmentation, and the coarse-to-fine causal interactions are considered using a Markov chain. Experimental results prove that the proposed model can segment SAR images better than several models previously proposed.