IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0233441.html
   My bibliography  Save this article

Computational load reduction of the agent guidance problem using Mixed Integer Programming

Author

Listed:
  • Vinícius Antonio Battagello
  • Nei Yoshihiro Soma
  • Rubens Junqueira Magalhães Afonso

Abstract

This paper employs a solution to the agent-guidance problem in an environment with obstacles, whose avoidance techniques have been extensively used in the last years. There is still a gap between the solution times required to obtain a trajectory and those demanded by real world applications. These usually face a tradeoff between the limited on-board processing performance and the high volume of computing operations demanded by those real-time applications. In this paper we propose a deferred decision-based technique that produces clusters used for obstacle avoidance as the agent moves in the environment, like a driver that, at night, enlightens the road ahead as her/his car moves along a highway. By considering the spatial and temporal relevance of each obstacle throughout the planning process and pruning areas that belong to the constrained domain, one may relieve the inherent computational burden of avoidance. This strategy reduces the number of operations required and increases it on demand, since a computationally heavier problem is tackled only if the simpler ones are not feasible. It consists in an improvement based solely on problem modeling, which, by example, may offer processing times in the same order of magnitude than the lower-bound given by the relaxed form of the problem.

Suggested Citation

  • Vinícius Antonio Battagello & Nei Yoshihiro Soma & Rubens Junqueira Magalhães Afonso, 2020. "Computational load reduction of the agent guidance problem using Mixed Integer Programming," PLOS ONE, Public Library of Science, vol. 15(6), pages 1-45, June.
  • Handle: RePEc:plo:pone00:0233441
    DOI: 10.1371/journal.pone.0233441
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0233441
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0233441&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0233441?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Benjamin S Cooper & Raghvendra V Cowlagi, 2018. "Path-planning with waiting in spatiotemporally-varying threat fields," PLOS ONE, Public Library of Science, vol. 13(8), pages 1-21, August.
    2. Xinmin Liu & Rodney D Wiersma, 2019. "Optimization based trajectory planning for real-time 6DoF robotic patient motion compensation systems," PLOS ONE, Public Library of Science, vol. 14(1), pages 1-16, January.
    3. He Luo & Zhengzheng Liang & Moning Zhu & Xiaoxuan Hu & Guoqiang Wang, 2018. "Integrated optimization of unmanned aerial vehicle task allocation and path planning under steady wind," PLOS ONE, Public Library of Science, vol. 13(3), pages 1-24, March.
    4. Yu, Chunhui & Feng, Yiheng & Liu, Henry X. & Ma, Wanjing & Yang, Xiaoguang, 2018. "Integrated optimization of traffic signals and vehicle trajectories at isolated urban intersections," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 89-112.
    5. Zengliang Han & Dongqing Wang & Feng Liu & Zhiyong Zhao, 2017. "Multi-AGV path planning with double-path constraints by using an improved genetic algorithm," PLOS ONE, Public Library of Science, vol. 12(7), pages 1-16, July.
    6. Ionela Prodan & Florin Stoican & Sorin Olaru & Silviu-Iulian Niculescu, 2012. "Enhancements on the Hyperplanes Arrangements in Mixed-Integer Programming Techniques," Journal of Optimization Theory and Applications, Springer, vol. 154(2), pages 549-572, August.
    7. Song Wang & Zhixia Li, 2019. "Exploring the mechanism of crashes with automated vehicles using statistical modeling approaches," PLOS ONE, Public Library of Science, vol. 14(3), pages 1-16, March.
    8. Minjie Wang & Su Yang & Yi Sun & Jun Gao, 2017. "Human mobility prediction from region functions with taxi trajectories," PLOS ONE, Public Library of Science, vol. 12(11), pages 1-23, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zhao, Jing & Knoop, Victor L. & Wang, Meng, 2020. "Two-dimensional vehicular movement modelling at intersections based on optimal control," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 1-22.
    2. Nordhoff, Sina & Stapel, Jork & van Arem, Bart & Happee, Riender, 2020. "Passenger opinions of the perceived safety and interaction with automated shuttles: A test ride study with ‘hidden’ safety steward," Transportation Research Part A: Policy and Practice, Elsevier, vol. 138(C), pages 508-524.
    3. Li, Ze-Tao & Nie, Wei-Peng & Cai, Shi-Min & Zhao, Zhi-Dan & Zhou, Tao, 2023. "Exploring the topological characteristics of urban trip networks based on taxi trajectory data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 609(C).
    4. Li, Li & Li, Xiaopeng, 2019. "Parsimonious trajectory design of connected automated traffic," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 1-21.
    5. Tang, Liying & Liu, Yugang & Li, JiaLi & Qi, Ruiting & Zheng, Shuai & Chen, Bin & Yang, Hongtai, 2020. "Pedestrian crossing design and analysis for symmetric intersections: Efficiency and safety," Transportation Research Part A: Policy and Practice, Elsevier, vol. 142(C), pages 187-206.
    6. Yu, Chunhui & Ma, Wanjing & Yang, Xiaoguang, 2020. "A time-slot based signal scheme model for fixed-time control at isolated intersections," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 176-192.
    7. Cui, Shaohua & Xue, Yongjie & Gao, Kun & Wang, Kai & Yu, Bin & Qu, Xiaobo, 2024. "Delay-throughput tradeoffs for signalized networks with finite queue capacity," Transportation Research Part B: Methodological, Elsevier, vol. 180(C).
    8. Xiao Xiao & Yunlong Zhang & Xiubin Bruce Wang & Shu Yang & Tianyi Chen, 2021. "Hierarchical Longitudinal Control for Connected and Automated Vehicles in Mixed Traffic on a Signalized Arterial," Sustainability, MDPI, vol. 13(16), pages 1-17, August.
    9. Mohebifard, Rasool & Hajbabaie, Ali, 2019. "Optimal network-level traffic signal control: A benders decomposition-based solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 252-274.
    10. Manivasakan, Hesavar & Kalra, Riddhi & O'Hern, Steve & Fang, Yihai & Xi, Yinfei & Zheng, Nan, 2021. "Infrastructure requirement for autonomous vehicle integration for future urban and suburban roads – Current practice and a case study of Melbourne, Australia," Transportation Research Part A: Policy and Practice, Elsevier, vol. 152(C), pages 36-53.
    11. Gao, Yuhong & Qu, Zhaowei & Song, Xianmin & Yun, Zhenyu & Xia, Yingji, 2021. "A novel relationship model between signal timing, queue length and travel speed," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 583(C).
    12. Li, Tongfei & Cao, Yaning & Xu, Min & Sun, Huijun, 2023. "Optimal intersection design and signal setting in a transportation network with mixed HVs and CAVs," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    13. Amirgholy, Mahyar & Gao, H. Oliver, 2023. "Optimal traffic operation for maximum energy efficiency in signal-free urban networks: A macroscopic analytical approach," Applied Energy, Elsevier, vol. 329(C).
    14. Xiaoqiu Shi & Wei Long & Yanyan Li & Dingshan Deng, 2020. "Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems," PLOS ONE, Public Library of Science, vol. 15(5), pages 1-23, May.
    15. Joey Huchette & Joey Huchette, 2019. "A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 793-820, August.
    16. Yuanying Cao & Xi Fang, 2023. "Optimized-Weighted-Speedy Q-Learning Algorithm for Multi-UGV in Static Environment Path Planning under Anti-Collision Cooperation Mechanism," Mathematics, MDPI, vol. 11(11), pages 1-28, May.
    17. Edward He & Natashia Boland & George Nemhauser & Martin Savelsbergh, 2021. "Time-Dependent Shortest Path Problems with Penalties and Limits on Waiting," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 997-1014, July.
    18. Rubens J. M. Afonso & Roberto K. H. Galvão, 2014. "Comments on “Enhancements on the Hyperplanes Arrangements in Mixed-Integer Programming Techniques”," Journal of Optimization Theory and Applications, Springer, vol. 162(3), pages 996-1003, September.
    19. Lu, Gongyuan & Shen, Zili & Liu, Xiaobo & Nie, Yu (Marco) & Xiong, Zhiqiang, 2022. "Are autonomous vehicles better off without signals at intersections? A comparative computational study," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 26-46.
    20. Chen, Xiangdong & Lin, Xi & Li, Meng & He, Fang & Meng, Qiang, 2023. "A nearly throughput-maximum knotted intersection design and control for connected and automated vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 171(C), pages 44-79.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0233441. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.