A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 11 Issue 2
Feb.  2024

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 11.8, Top 4% (SCI Q1)
    CiteScore: 17.6, Top 3% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2024  >  11(2): 529-538
S. Feng, L. Zeng, J. Liu, Y. Yang, and  W. Song,  “Multi-UAVs collaborative path planning in the cramped environment,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 2, pp. 529–538, Feb. 2024. doi: 10.1109/JAS.2023.123945
Citation: S. Feng, L. Zeng, J. Liu, Y. Yang, and  W. Song,  “Multi-UAVs collaborative path planning in the cramped environment,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 2, pp. 529–538, Feb. 2024. doi: 10.1109/JAS.2023.123945
shu

Multi-UAVs Collaborative Path Planning in the Cramped Environment

doi: 10.1109/JAS.2023.123945
Funds:  This work was partly supported by Program for the National Natural Science Foundation of China (62373052, U1913203, 61903034), Youth Talent Promotion Project of China Association for Science and Technology, Beijing Institute of Technology Research Fund Program for Young Scholars
More Information
    Abstract

  • Due to its flexibility and complementarity, the multi-UAVs system is well adapted to complex and cramped workspaces, with great application potential in the search and rescue (SAR) and indoor goods delivery fields. However, safe and effective path planning of multiple unmanned aerial vehicles (UAVs) in the cramped environment is always challenging: conflicts with each other are frequent because of high-density flight paths, collision probability increases because of space constraints, and the search space increases significantly, including time scale, 3D scale and model scale. Thus, this paper proposes a hierarchical collaborative planning framework with a conflict avoidance module at the high level and a path generation module at the low level. The enhanced conflict-base search (ECBS) in our framework is improved to handle the conflicts in the global path planning and avoid the occurrence of local deadlock. And both the collision and kinematic models of UAVs are considered to improve path smoothness and flight safety. Moreover, we specifically designed and published the cramped environment test set containing various unique obstacles to evaluating our framework performance thoroughly. Experiments are carried out relying on Rviz, with multiple flight missions: random, opposite, and staggered, which showed that the proposed method can generate smooth cooperative paths without conflict for at least 60 UAVs in a few minutes. The benchmark and source code are released in

    https://github.com/inin-xingtian/multi-UAVs-path-planner

    .

     

    • FullText(HTML)
  • loading
    • References(31)
  • [1]
    Y. Zhao, X. Wang, C. Wang, Y. Cong, and L. Shen, “Systemic design of distributed multi-UAV cooperative decision-making for multi-target tracking,” Auton. Agents Multi-Agent Syst., vol. 33, no. 1–2, pp. 132–158, Mar. 2019. doi: 10.1007/s10458-019-09401-5
    [2]
    S. J. Chung, A. A. Paranjape, P. Dames, S. Shen, and V. Kumar, “A survey on aerial swarm robotics,” IEEE Trans. Rob., vol. 34, no. 4, pp. 837–855, Aug. 2018. doi: 10.1109/TRO.2018.2857475
    [3]
    Y. Tian, K. Liu, K. Ok, L. Tran, D. Allen, N. Roy, and J. P. How, “Search and rescue under the forest canopy using multiple UAS,” in Proc. Int. Symp. Experimental Robotics, J. Xiao, T. Kröger, and O. Khatib, Eds. Cham, Germany: Springer, 2020.
    [4]
    K. Miyano, R. Shinkuma, N. B. Mandayam, T. Sato, and E. Oki, “Utility based scheduling for multi-UAV search systems in disaster-hit areas,” IEEE Access, vol. 7, pp. 26810–26820, Feb. 2019. doi: 10.1109/ACCESS.2019.2900865
    [5]
    X. Zhu, F. Vanegas, F. Gonzalez, and C. Sanderson, “A multi-UAV system for exploration and target finding in cluttered and GPS-denied environments,” in Proc. Int. Conf. Unmanned Aircraft Systems, Athens, Greece, 2021.
    [6]
    J. Tang, X. Chen, X. Zhu, and F. Zhu, “Dynamic reallocation model of multiple unmanned aerial vehicle tasks in emergent adjustment scenarios,” IEEE Trans. Aerosp. Electron. Syst., vol. 59, no. 2, pp. 1139–1155, Apr. 2023.
    [7]
    X. Huang, X. Cheng, Q. Geng, B. Cao, D. Zhou, P. Wang, Y. Lin, and R. Yang, “The ApolloScape dataset for autonomous driving,” in Proc. IEEE/CVF Conf. Computer Vision and Pattern Recognition Workshops, Salt Lake City, USA, 2018, pp. 954–960.
    [8]
    J. van den Berg, S. J. Guy, M. Lin, and D. Manocha, “Reciprocal n-body collision avoidance,” in Robotics Research: The 14th Int. Symposium ISRR, C. Pradalier, R. Siegwart, and G. Hirzinger, Eds. Berlin, Germany: Springer, 2011.
    [9]
    J. van den Berg, J. Snape, S. J. Guy, and D. Manocha, “Reciprocal collision avoidance with acceleration-velocity obstacles,” in Proc. IEEE Int. Conf. Robotics and Automation, Shanghai, China, 2011.
    [10]
    J. van den Berg, M. Lin, and D. Manocha, “Reciprocal velocity obstacles for real-time multi-agent navigation,” in Proc. Int. Conf. Robotics and Automation, Pasadena, USA, 2008.
    [11]
    C. E. Luis and A. P. Schoellig, “Trajectory generation for multiagent point-to-point transitions via distributed model predictive control,” IEEE Rob. Autom. Lett., vol. 4, no. 2, pp. 375–382, Apr. 2019. doi: 10.1109/LRA.2018.2890572
    [12]
    J. Li, M. Ran, and L. Xie, “Efficient trajectory planning for multiple non-holonomic mobile robots via prioritized trajectory optimization,” IEEE Rob. Autom. Lett., vol. 6, no. 2, pp. 405–412, Apr. 2021. doi: 10.1109/LRA.2020.3044834
    [13]
    J. Park, J. Kim, I. Jang, and H. J. Kim, “Efficient multi-agent trajectory planning with feasibility guarantee using relative Bernstein polynomial,” in Proc. IEEE Int. Conf. Robotics and Automation, Paris, France, 2020.
    [14]
    Y. F. Chen, M. Cutler, and J. P. How, “Decoupled multiagent path planning via incremental sequential convex programming,” in Proc. IEEE Int. Conf. Robotics and Automation, Seattle, USA, 2015.
    [15]
    D. Mellinger, A. Kushleyev, and V. Kumar, “Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams,” in Proc. Int. Conf. Robotics and Automation, Saint Paul, USA, 2012.
    [16]
    J. Tang, G. Liu, and Q. Pan, “A review on representative swarm intelligence algorithms for solving optimization problems: Applications and trends,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 10, pp. 1627–1643, Oct. 2021. doi: 10.1109/JAS.2021.1004129
    [17]
    G. Röger and M. Helmert, “The more, the merrier: Combining heuristic estimators for satisficing planning,” in Proc. 20th Int. Conf. Automated Planning and Scheduling, Toronto, Canada, 2010.
    [18]
    E. Boyarski, A. Felner, R. Stern, G. Sharon, D. Tolpin, O. Betzalel, and E. Shimony, “ICBS: Improved conflict-based search algorithm for multi-agent pathfinding,” in Proc. 8th Int. Symp. Combinatorial Search, Ein Gedi, Israel, 2015.
    [19]
    D. Atzmon, R. Stern, A. Felner, G. Wagner, R. Bartak, and N.-F. Zhou, “Robust multi-agent path finding,” in Proc. 17th Int. Conf. Autonomous Agents and MultiAgent Systems, Stockholm, Sweden, 2018.
    [20]
    S. Tang, J. Thomas, and V. Kumar, “Hold or take optimal plan (HOOP): A quadratic programming approach to multi-robot trajectory generation,” Int. J. Rob. Res., vol. 37, no. 9, pp. 1062–1084, Aug. 2018. doi: 10.1177/0278364917741532
    [21]
    W. Hönig, J. A. Preiss, T. K. S. Kumar, G. S. Sukhatme, and N. Ayanian, “Trajectory planning for quadrotor swarms,” IEEE Trans. Rob., vol. 34, no. 4, pp. 856–869, Aug. 2018. doi: 10.1109/TRO.2018.2853613
    [22]
    D. R. Robinson, R. T. Mar, K. Estabridis, and G. Hewer, “An efficient algorithm for optimal trajectory generation for heterogeneous multi-agent systems in non-convex environments,” IEEE Rob. Autom. Lett., vol. 3, no. 2, pp. 1215–1222, Apr. 2018. doi: 10.1109/LRA.2018.2794582
    [23]
    J. Li, P. Surynek, A. Felner, H. Ma, T. K. S. Kumar, and S. Koenig, “Multi-agent path finding for large agents,” in Proc. 33rd AAAI Conf. Artificial Intelligence and 31st Innovative Applications of Artificial Intelligence Conf. and 9th AAAI Symp. Educational Advances in Artificial Intelligence, Honolulu, USA, 2019.
    [24]
    L. Wen, Z. Zhang, Z. Chen, X. Zhao, and Y. Liu, “CL-MAPF: Multi-agent path finding for car-like robots with kinematic and spatiotemporal constraints,” arXiv preprint arXiv: 2011.00441, 2020.
    [25]
    M. Debord, W. Hönig, and N. Ayanian, “Trajectory planning for heterogeneous robot teams,” in Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, Madrid, Spain, 2018.
    [26]
    R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, R. Barták, and E. Boyarski, “Multi-agent pathfinding: Definitions, variants, and benchmarks,” in Proc. 12th Int. Symp. Combinatorial Search, Napa, USA, 2019.
    [27]
    M. Barer, G. Sharon, R. Stern, and A. Felner, “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem,” in Proc. 21st European Conf. Artificial Intelligence, Prague, Czech Republic, 2014, pp. 961–962.
    [28]
    B. Zhou, F. Gao, L. Wang, C. Liu, and S. Shen, “Robust and efficient quadrotor trajectory generation for fast autonomous flight,” IEEE Rob. Autom. Lett., vol. 4, no. 4, pp. 3529–3536, Oct. 2019. doi: 10.1109/LRA.2019.2927938
    [29]
    S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, USA: Cambridge University Press, 2004.
    [30]
    J. Yu and S. M. LaValle, “Optimal multi-robot path planning on graphs: Structure and computational complexity,” arXiv preprint arXiv: 1507.03289, 2015.
    [31]
    X. Zhou, J. Zhu, H. Zhou, C. Xu, and F. Gao, “EGO-SWARM: A fully autonomous and decentralized quadrotor swarm system in cluttered environments,” in Proc. IEEE Int. Conf. Robotics and Automation, Xi’an, China, 2021, pp. 4101–4107.
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(12)  / Tables(3)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (320) PDF downloads(65) Cited by()

    Highlights

    • A hierarchical planning framework based on the ECBS algorithm is proposed for multi-UAVs cooperative path planning problem in cramped environments, which has solved the problems of size-constrained obstacle avoidance and spatiotemporal conflict avoidance
    • Relying on the path search algorithm based on the kinematic model of UAVs, the smoothness of output paths is improved, which is convenient for the tracking control of UAVs
    • Detailed experiments are conducted in the specially designed cramped environment test set, and the source code and test set are published, available for comparison by relevant researchers

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return