Email: greaten23333@gmail.com or 2274880117@qq.com
QQ: 2274880117
Wechat: AnonymousGT666

Robotics, Multi-Robot Planning, AI, Deep Learning, Robotics Control

C++, Unity, Python, Java, ROS, Crazyflie Control

1. Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time (RSS-2022)[paper]
The theoretical contributions of this paper is summarized as follows. Assuming random X_I and X_G on m₁ × m₂ grids , we prove that we can compute in low-polynomial time with high probability:
(i). (7, 10.5] asymptotically optimal solutions at 100% robot density
(ii). (1, 1.5] asymptotically optimal solutions at up to 1/2 robot density, or 2/9 density with obstacles
(iii). Python-based implementations readily scale to over 50,000 robots, with sub-1.5 optimality
(iv). In contrast, MRPP on grids is proven NP-hard. Previous algorithms are either non-polynomial time or very suboptimal






2. Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning (ICRA-2021)[paper]
Due to the intractability of MRPP, it is not practical to find optimal solutions. Instead, a fast and near-optimal algorithm is preferred in real applications. To improve the scalibility of MRPP solvers without sacrificing the optimality too much, we propose two divide-and-conquer based heuristics, time-split heuristic and space-split heuristic. Our experiment shows that the proposed heuristics provide 10x-100x speed boost while the solution optimality is still 1.x.



3. Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination (IROS-2022)[paper]
We extend our RSS2022's work on 3D well-connected grids and conduct experiments and simulations using crazyflies. The resulting algorithm runs in polynomial time and is 1.x asymptotic expected makespan-optimal for random MRPP instances. Our C++ implementations can scale to 100K robots on grids with 300K vertives.




4. Bin Assignment and Decentralized Path Planning for Multi-Robot Parcel Sorting (Submitted to ICRA-2023)
Many e-commerce companies have deployed thousands of robots to sort packages in automated sorting warehouse. On the one hand, the throughput, or the number of parcels sorted per timestep is an important criteria for evaluating the efficiency of the warehouse. On the other hand, due to the NP-hardness of the multi-robot planning, computing optimal solutions is very difficult for large-scale problems. In this paper, we propose bin assignment algorithms and decentralized path planning algorithms aiming to achieve a balance between improving the throughout and reducing the computational costs. Our simulations show that our methods can scale to 400-600 robots in a 30 × 60 grid-like warehouse while the throughput is slightly lower than the throughput of a non-scalable bounded-suboptimal solver.




5. Toward Efficient Physical and Algorithmic Design of Automated Garages (Submitted to ICRA-2023)
As the cost of parking is becoming increasingly expensive, we study an autonomous grid-based system for car parking and retrieving that can support nearly 100% density. We have designed fast and efficient algorithms for parking and retrieving in such systems. Simulations show that our solutions can support nearly 2000+ cars in a 50× 50 grid map with car density more than 90%. Compared to an optimal ILP-based algorithm, our algorithm for car retrieving and parking is more than 100x faster, while the solution quality is acceptable.




6. Team RuBot, 2020 ARIAC Competition (RCIM-2021)[paper]
We joined the 2020 Agile Robotics for Industrial Automation Competition host by NIST. We won the third place. Below is the highlight video.