• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Ji Dong, Wei Yangjie, Li Yuxi, Wang Yi. Priority Assignment Method of DAG Task on ROS2 Multithreaded Executor[J]. Journal of Computer Research and Development, 2023, 60(5): 1086-1098. DOI: 10.7544/issn1000-1239.202220741
Citation: Ji Dong, Wei Yangjie, Li Yuxi, Wang Yi. Priority Assignment Method of DAG Task on ROS2 Multithreaded Executor[J]. Journal of Computer Research and Development, 2023, 60(5): 1086-1098. DOI: 10.7544/issn1000-1239.202220741

Priority Assignment Method of DAG Task on ROS2 Multithreaded Executor

Funds: This work was supported by the National Natural Science Foundation of China (61973059) and the Fundamental Research Funds for the Central Universities (N2116006).
More Information
  • Author Bio:

    Ji Dong: born in 1989. PhD. Student member of CCF. His main research interests include timing analysis in embedded systems, machine learning and its various applications in renewable energy

    Wei Yangjie: born in 1978. PhD, professor, PhD supervisor. Member of CCF. Her main research interests include speech and audio signal processing, image processing, and computer vision

    Li Yuxi: born in 1990. PhD, lecturer. Member of CCF. Her main research interests include cyberspace security and Internet of things security

    Wang Yi: born in 1961. PhD, professor, PhD supervisor. Member of CCF. His main research interests include modeling and validation of timed systems, timing analysis of embedded software on multicores and multiprocessor real-time scheduling

  • Received Date: August 21, 2022
  • Revised Date: February 16, 2023
  • Available Online: March 28, 2023
  • With the growing popularity of the robot operating system (ROS), these systems are becoming increasingly complex, and the computing platforms they run on are transforming into multi-core platforms. In ROS, the order of task execution is determined by the underlying task scheduling strategy and the priorities assigned to the tasks. Minimizing the execution time of all tasks is a crucial goal in task scheduling for parallel systems. To address this challenge, we propose a reinforcement learning-based task priority assignment method, inspired by recent achievements in using reinforcement learning for handling various combinatorial optimization problems and considering the scheduling mechanisms and execution constraints of ROS2 multi-threaded executors. This method extracts the temporal and structural features of the task set, which is represented in the form of a directed acyclic graph (DAG), and efficiently learns the ROS2 scheduling policy through a combination of policy gradient and Monte Carlo tree search (MCTS) methods, providing a reasonable priority setting scheme. The goal of minimizing the completion time of DAG parallel tasks is achieved through this method. The proposed method is evaluated by simulating randomly generated task graphs in a simulation platform environment. The results show that it outperforms the benchmark methods. As an off-line analysis method, the proposed method can be easily extended to more complex ROS and can find a near-optimal solution in an acceptable amount of time.

  • [1]
    Macenski S, Foote T, Gerkey B, et al. Robot operating system 2: Design, architecture, and uses in the wild[J]. Science Robotics 2022, 7(66): eabm6074
    [2]
    Casini D, Blaß T, Lütkebohle I, et al. Response-time analysis of ROS 2 processing chains under reservation-based scheduling[C]// Proc of the 31st Euromicro Conf on Real-Time Systems (ECRTS). Dagstuhl, Germany: LIPIcs, 2019: 6: 1−6: 23
    [3]
    Tang Yue, Feng Zhiwei, Guan Nan, et al. Response time analysis and priority assignment of processing chains on ROS 2 executors[C]// Proc of the 41st IEEE Real-Time Systems Symp (RTSS). Piscataway, NJ: IEEE, 2020: 231−243
    [4]
    Bédard C, Lütkebohle I, Dagenais M. ROS2_tracing: Multipurpose low-overhead framework for real-time tracing of ROS 2[J]. IEEE Robotics and Automation Letters, 2022, 7(3): 6511−6518 doi: 10.1109/LRA.2022.3174346
    [5]
    Blaß T, Casini D, Bozhko S, et al. A ROS 2 response-time analysis exploiting starvation freedom and execution-time variance[C]// Proc of the 42nd IEEE Real-Time Systems Symp (RTSS). Piscataway, NJ: IEEE, 2021: 41−53
    [6]
    Kronauer T, Pohlmann J, Matthe M, et al. Latency analysis of ROS2 multi-node systems[J]. arXiv preprint, arXiv: 2101.02074, 2021
    [7]
    Vazirani V V. Approximation Algorithms[M]. Berlin: Springer, 2001
    [8]
    Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem[J]. Operations Research, 2000, 48(2): 256−267 doi: 10.1287/opre.48.2.256.12386
    [9]
    Li Jing, Chen Jianjia, Agrawal K, et al. Analysis of federated and global scheduling for parallel real-time tasks[C]// Proc of the 26th Euromicro Conf on Real-Time Systems(ECRTS). Piscataway, NJ: IEEE, 2014: 85−96
    [10]
    Melani A, Bertogna M, Bonifaci V, et al. Response-time analysis of conditional dag tasks in multiprocessor systems[C]// Proc of the 27th Euromicro Conf on Real-Time Systems(ECRTS). Piscataway, NJ: IEEE, 2015: 211−221
    [11]
    Jiang Xu, Guan Nan, Long Xiang, et al. Semi-federated scheduling of parallel real-time tasks on multiprocessors[C] //Proc of the 38th IEEE Real-Time Systems Symp (RTSS). Piscataway, NJ: IEEE, 2017: 80−91
    [12]
    Baruah S, Bonifaci V, Marchetti-Spaccamela A. The global EDF scheduling of systems of conditional sporadic DAG tasks[C]// Proc of the 27th Euromicro Conf on Real-Time Systems(ECRTS). Piscataway, NJ: IEEE, 2015: 222−231
    [13]
    Clausen J. Branch and bound algorithms-principles and examples[EB/OL]. Department of Computer Science, University of Copenhagen, 1999[2023-02-11].https://imada.sdu.dk/u/jbj/heuristikker/TSPtext.pdf
    [14]
    Kohler W H, Steiglitz K. Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems[J]. Journal of the ACM, 1974, 21(1): 140−156 doi: 10.1145/321796.321808
    [15]
    Kwok Y K, Ahmad I. Static scheduling algorithms for allocating directed task graphs to multiprocessors[J]. ACM Computing Surveys, 1999, 31(4): 406−471 doi: 10.1145/344588.344618
    [16]
    Wei Hongxing, Shao Zhenzhou, Huang Zhen , et al. RT-ROS: A real-time ROS architecture on multi-core processors[J]. Future Generation Computer Systems, 2016, 56: 171−178 doi: 10.1016/j.future.2015.05.008
    [17]
    Saito Y, Azumi T, Kato S, et al. Priority and synchronization support for ROS[C]// Proc of the 4th IEEE Int Conf on Cyber-Physical Systems, Networks, and Applications (CPSNA). Piscataway, NJ: IEEE, 2016: 77−82
    [18]
    Choi H, Xiang Yecheng, Kim H. PiCAS: New design of priority-driven chain-aware scheduling for ROS2[C]// Proc of the 27th IEEE Real-Time and Embedded Technology and Applications Symp (RTAS). Piscataway, NJ: IEEE, 2021: 251−263
    [19]
    Li Jing, Agrawal K, Lu Chenyang, et al. Outstanding paper award: Analysis of global EDF for parallel tasks[C]// Proc of the 25th Euromicro Conf on Real-Time Systems(ECRTS). Piscataway, NJ: IEEE, 2013: 3−13
    [20]
    Baruah S. Improved multiprocessor global schedulability analysis of sporadic DAG task systems[C]// Proc of the 26th Euromicro Conf on Real-Time Systems (ECRTS). Piscataway, NJ: IEEE, 2014: 97−105
    [21]
    Fonseca J, Nelissen G, Nélis V. Improved response time analysis of sporadic DAG tasks for global FP scheduling[C]// Proc of the 25th Int Conf on Real-time Networks and Systems. New York: ACM, 2017: 28−37
    [22]
    Fonseca J, Nelissen G, Nélis V. Schedulability analysis of dag tasks with arbitrary deadlines under global fixed-priority scheduling[J]. Real-Time Systems, 2019, 55(2): 387−432 doi: 10.1007/s11241-018-09325-5
    [23]
    Baruah S. The federated scheduling of constrained-deadline sporadic DAG task systems[C]// Proc of the 18th Design, Automation & Test in Europe Conf & Exhibition (DATE). Piscataway, NJ: IEEE, 2015: 1323−1328
    [24]
    Li Jing, Ferry D, Ahuja S, et al. Mixed-criticality federated scheduling for parallel real-time tasks[J]. Real-Time Systems, 2017, 53(5): 760−811 doi: 10.1007/s11241-017-9281-8
    [25]
    Zhao Shuai, Dai Xiaotian, Bate I, et al. DAG scheduling and analysis on multiprocessor systems: Exploitation of parallelism and dependency[C]// Proc of the 41st IEEE Real-Time Systems Symp (RTSS). Piscataway, NJ: IEEE, 2020: 128−140
    [26]
    Pathan R, Voudouris P, Stenström P. Scheduling parallel real-time recurrent tasks on multicore platforms[J]. IEEE Transactions on Parallel and Distributed Systems, 2017, 29(4): 915−928
    [27]
    He Qingqiang, Guan Nan, Guo Zhishan. Intra-task priority assignment in real-time scheduling of dag tasks on multi-cores[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(10): 2283−2295 doi: 10.1109/TPDS.2019.2910525
    [28]
    He Qingqiang, Lv Mingsong, Guan Nan. Response time bounds for DAG tasks with arbitrary intra-task priority assignment[C]// Proc of the 33rd Euromicro Conf on Real-Time Systems (ECRTS). Dagstuhl, Germany: LIPIcs, 2021: 8: 1−8: 21
    [29]
    Kasahara H, Narita S. Practical multiprocessor scheduling algorithms for efficient parallel processing[J]. IEEE Transactions on Computers, 1984, 33(11): 1023−1029
    [30]
    Kwok Y K, Ahmad I. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(5): 506−521 doi: 10.1109/71.503776
    [31]
    Mao Hongzi, Mohammad A, Ishai M, et al. Resource management with deep reinforcement learning[C]// Proc of the 15th ACM Workshop on Hot Topics in Networks. New York: ACM, 2016: 50−56
    [32]
    Chen Xinyun, Tian Yuandong. Learning to perform local rewriting for combinatorial optimization[C]// Proc of the 33rd Int Conf on Neural Information Processing Systems. New York: ACM, 2019: 6281–6292
    [33]
    Kober J, Bagnell J A, Peters J. Reinforcement learning in robotics: A survey[J]. The International Journal of Robotics Research, 2013, 32(11): 1238−1274 doi: 10.1177/0278364913495721
    [34]
    Lee H, Cho S, Jang Y, et al. A global DAG task scheduler using deep reinforcement learning and graph convolution network[J]. IEEE Access, 2021, 9: 158548−158561 doi: 10.1109/ACCESS.2021.3130407
    [35]
    Mao Hongzi, Schwarzkopf M, Venkatakrishnan S B, et al. Learning scheduling algorithms for data processing clusters[C]// Proc of the 33rd ACM Special Interest Group on Data Communication. New York: ACM, 2019: 270−288
    [36]
    Macenski S, Foote T, Gerkey B, et al. ROS 2 Foxy Fitzroy [CP/OL]. 2020[2022-11-05].https://docs.ros.org/en/foxy/
    [37]
    Foote T, Scott K. ROS community metrics report 2020[EB/OL]. 2021 [2022-11-05]. http://download.ros.org/downloads/metrics/metrics-report-2021-07.pdf
    [38]
    Bello I, Pham H, Le Q V, et al. Neural combinatorial optimization with reinforcement learning[J]. arXiv preprint, arXiv: 1611.09940, 2016
    [39]
    Coulom R. Efficient selectivity and backup operators in Monte-Carlo tree search[C] //Proc of the 5th Int Conf on Computers and Games. Berlin: Springer, 2006: 72−83
    [40]
    Saqlain M, Ali S, Lee J Y. A Monte-Carlo tree search algorithm for the flexible job-shop scheduling in manufacturing systems[J/OL]. Flexible Services and Manufacturing Journal, 2022[2023-02-11].https://doi.org/10.1007/s10696−021-09437−4
    [41]
    Hu Zhiming, Tu J, Li Baochun. Spear: Optimized dependency-aware task scheduling with deep reinforcement learning[C]// Proc of the 39th IEEE Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2019: 2037−2046
    [42]
    Arabnejad H, Barbosa J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 682−694
    [43]
    Topcuoglu H, Hariri S, Wu Minyou. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260−274 doi: 10.1109/71.993206
    [44]
    Schulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms[J]. arXiv preprint, arXiv: 1707.06347, 2017
    [45]
    Brockman G, Cheung V, Pettersson L, et al. OpenAI gym[J]. arXiv preprint, arXiv: 1606.01540, 2016
  • Cited by

    Periodical cited type(1)

    1. 李燊阳,邓三鹏,权利红,祁宇明,丁昊然,刘天慧. 基于激光雷达增强的视觉SLAM多机器人协作地图构建方法的研究. 机器人技术与应用. 2023(06): 20-23 .

    Other cited types(1)

Catalog

    Article views (186) PDF downloads (93) Cited by(2)

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return