A globally consistent map is the basis of indoor robot localization and navigation. However, map built by Rao-Blackwellized Particle Filter (RBPF) doesn’t have high global consistency which is not suitable for long-term application in large scene. To address the problem, we present an improved RBPF Lidar SLAM system with loop detection and correction named LCPF. The efficiency and accuracy of loop detection depend on the segmentation of submaps. Instead of dividing the submap at fixed number of laser scan like existing method, Dynamic Submap Segmentation is proposed in LCPF. This segmentation algorithm decreases the error inside the submap by splitting the submap where there is high scan match error and later rectifies the error by an improved pose graph optimization between submaps. In order to segment the submap at appropriate point, when to create a new submap is determined by both the accumulation of scan match error and the particle distribution. Furthermore, LCPF uses branch and bound algorithm as basic detector for loop detection and multiple criteria to judge the reliability of a loop. In the criteria, a novel parameter called usable ratio was proposed to measure the useful information that a laser scan containing. Finally, comparisons to existing 2D-Lidar mapping algorithm are performed with a series of open dataset simulations and real robot experiments to demonstrate the effectiveness of LCPF.

Path planning under two-dimensional (2D) maps is a fundamental problem in mobile robotics and other real-world applications (unmanned vehicles, navigation apps for mobile phones, and so forth). However, traditional algorithms (graph searching, artificial potential field, genetic, and so forth) rely on grid-by-grid searching. Thus, these methods generally do not find the global optimal path, and as the map scale increases, their time cost sharply increases, except artificial potential field. A few algorithms that do not rely on grid-by-grid searching (RRT, visibility graph, and tangent graph) have special requirements for maps. Considering that the shortest path is often composed of tangents between obstacles, in this paper, we propose a method called ReinforcedRimJump (RRJ) that does not rely on point-by-point traversal but rather obtains the shortest path by finding the tangent multiple times between obstacles. The first improvement of this method is the precomputation of tangents, which causes the method to have a lower time cost than traditional methods. The second improvement of RRJ is edge segmentation, which allows RRJ to be used when the target is in the depression of the obstacle. To verify the theoretical advantages of RRJ, some comparative experiments under various maps are performed. The experimental results show that RRJ can always find the shortest path in the shortest time. Furthermore, the time cost of RRJ is insensitive compared to other methods. The experimental results presented herein demonstrate that RRJ meets the theoretical expectations.

Summary: Path planning under 2D map is a key issue in robot applications. However, most related algorithms rely on point-by-point traversal. This causes them usually cannot find the strict shortest path, and their time cost increases dramatically as the map scale increases. So we proposed RimJump to solve the above problem, and it is a new path planning method that generates the strict shortest path for a 2D map. RimJump selects points on the edge of barriers to form the strict shortest path. Simulation and experimentation prove that RimJump meets the expected requirements.

Multi-Agent Path Finding (MAPF) has been widely studied in recent years. However, most existing MAPF algorithms assume that an agent occupies only a single cell in a grid-based map. This assumption limits their applicability in many real-world domains where agents have geometric shapes rather than being point-like. These agents, which can occupy multiple cells simultaneously, are referred to as “large” agents. When considering the shape and size of agents in MAPF, i.e., MAPF for large agents (LA-MAPF), the computational complexity increases significantly as the number of agents increases, primarily because of the increased overhead in conflict detection between geometric agents. This paper introduces Layered Decomposition, a method that decomposes a MAPF problem into subproblems through iterative bipartitioning. This approach aims to reduce the time cost when solving LA-MAPF problems. To address unsolvable subproblems, we propose a solvability safeguard mechanism that merges subproblems until a solvable subproblem is formed. Experiments show that our LA-MAPF method with decomposition reduces time cost and increases the success rate of state-of-art MAPF methods significantly. To facilitate further research, we have made the source code for the Layered decomposition of LA-MAPF publicly available¹.

Multi-agent pathfinding (MAPF) holds significant utility within autonomous systems, however, the calculation and memory space required for multi-agent path finding (MAPF) grows exponentially as the number of agents increases. This often results in some MAPF instances being unsolvable under limited computational resources and memory space, thereby limiting the application of MAPF in complex scenarios. Hence, we propose a decomposition approach for MAPF instances, which breaks down instances involving a large number of agents into multiple isolated subproblems involving fewer agents. Moreover, we present a framework to enable general MAPF algorithms to solve each subproblem independently and merge their solutions into one conflict-free final solution, and avoid loss of solvability as much as possible. Unlike existing works that propose isolated methods aimed at reducing the time cost of MAPF, our method is applicable to all MAPF methods. In our results, we apply decomposition to multiple state-of-the-art MAPF methods using a classic MAPF benchmark\footnote{https://movingai.com/benchmarks/mapf.html}. The decomposition of MAPF instances is completed on average within 1s, and its application to seven MAPF methods reduces the memory usage or time cost significantly, particularly for serial methods. Based on massive experiments, we speculate the possibilty about loss of solvability caused by our method is $<$ 1\%. To facilitate further research within the community, we have made the source code of the proposed algorithm publicly available\footnote{https://github.com/JoeYao-bit/LayeredMAPF/tree/minimize\_dependence}.

Line-Of-Sight (LOS) check plays a crucial role in collision avoidance and time comsuming, particularly in scenarios involving large-scale maps with sparse obstacles, as it necessitates a grid-by-grid state check. Specifically, LOS check consumes more than half of the computational time in any-angle path planning algorithms, such as Theta*, Visibility Graph, and RRT. To address this issue, we propose an efficient LOS checker for maps of arbitrary dimensions with sparse obstacles. Our approach involves a two-step process. Firstly, we partition the passable space into blocks until there is no vacancy for a minimum-sized block. When the adapted Bresenham algorithm reaches a surface of a block, it bypasses grid-by-grid traversal within the block and directly jumps to the opposing surface. This method significantly reduces the number of grids examined, resulting in higher efficiency compared to traditional LOS checks. We refer to our approach as Jump Over Block (JOB). To demonstrate the advantages of JOB, we compare its performance against traditional LOS checks using a widely recognized public dataset. The results indicate that JOB incurs only 1/6 to 1/5 of the computational cost associated with raw LOS checks, making it a valuable tool for both researchers and practitioners in the field. In order to facilitate further research within the community, we have made the source code of the proposed algorithm publicly available. We anticipate that this framework will contribute to the development of more efficient path planning algorithms and expedite various aspects of robotics that involve collision checks.