Allocation Problem in Remote Teleoperation: Online Matching with Offline Reusable Resources and Delayed Assignments
Authors: 
Osnat Ackerman Viden, Yohai Trabelsi, Pan Xu, Karthik Abinav Sankararaman, Oleg Maksimov, Sarit KrausAuthors Info & Claims
Pages 513 - 521
Abstract
Many applications where tasks should be assigned to agents can be modeled as matching in bipartite graphs. In this paper, we consider applications where tasks arrive dynamically and rejection of a task may have significant adverse effects on the requester, therefore performing the task with some delay is preferred over complete rejection. The performance time of a task depends on the task, the agent, and the assignment, and only its distribution is known in advance. The actual time is known only after the task performance when the agent is available for a new assignment. We consider such applications to be one of two arrival types. With the first type, the arrival distribution is known in advance, while there is no assumption about the arrival times and order with the second type. For the first type, we present an LP-based online algorithm with a competitive ratio of 0.5. For the second type, we show no online algorithm with a constant competitive ratio. We run extensive experiments to evaluate our algorithm in a real-world dataset, demonstrating the advantages of the LP approach.
References
[1]
Ali Aouad and Ömer Saritacc. 2022. Dynamic stochastic matching under limited time. Operations Research (2022).
[2]
Saif Benjaafar, Zicheng Wang, and Xiaotang Yang. 2022. Human in the Loop Automation: Ride-Hailing With Remote (Tele-) Drivers. Available at SSRN 4130757 (2022).
[3]
Daniel Bogdoll, Stefan Orf, Lars Töttel, and J Marius Zöllner. 2022. Taxonomy and Survey on Remote Human Input Systems for Driving Automation Systems. In Future of Information and Communication Conference. Springer, 94--108.
[4]
Holger Caesar, Varun Bankiti, Alex H Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom. 2020. nuscenes: A multimodal dataset for autonomous driving. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 11621--11631.
[5]
Felipe Codevilla, Matthias Müller, Antonio López, Vladlen Koltun, and Alexey Dosovitskiy. 2018. End-to-end driving via conditional imitation learning. In 2018 IEEE international conference on robotics and automation (ICRA). IEEE, 4693--4700.
[6]
Danial Dervovic, Parisa Hassanzadeh, Samuel Assefa, and Prashant Reddy. 2021. Non-Parametric Stochastic Sequential Assignment With Random Arrival Times. In IJCAI '2021. 4214--4220.
[7]
John Dickerson, Karthik Sankararaman, Aravind Srinivasan, and Pan Xu. 2020. Allocation problems in ride-sharing platforms: Online matching with offline reusable resources. ACM Transactions on Economics and Computation (2020).
[8]
Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. 2017. CARLA: An open urban driving simulator. In Conference on robot learning. PMLR, Mountain View, United States, 1--16.
[9]
Ezekiel J Emanuel, Govind Persad, Ross Upshur, Beatriz Thome, Michael Parker, Aaron Glickman, Cathy Zhang, Connor Boyle, Maxwell Smith, and James P Phillips. 2020. Fair allocation of scarce medical resources in the time of Covid-19., 2049--2055 pages.
[10]
Yiding Feng, Rad Niazadeh, and Amin Saberi. 2022. Near-optimal bayesian online assortment of reusable resources. In Proceedings of the 23rd ACM Conference on Economics and Computation. 964--965.
[11]
Jean-Michael Georg and Frank Diermeyer. 2019. An adaptable and immersive real time interface for resolving system limitations of automated vehicles with teleoperation. In 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC). IEEE, 2659--2664.
[12]
Xiao-Yue Gong, Vineet Goyal, Garud Iyengar, David Simchi-Levi, Rajan Udwani, and Shuangyu Wang. 2019. Online assortment optimization with reusable resources. Minor revision in Management Science (2019).
[13]
Xiao-Yue Gong, Vineet Goyal, Garud N Iyengar, David Simchi-Levi, Rajan Udwani, and Shuangyu Wang. 2021. Online assortment optimization with reusable resources. Management Science (2021).
[14]
Vineet Goyal, Garud Iyengar, and Rajan Udwani. 2020. Online Allocation of Reusable Resources: Achieving Optimal Competitive Ratio. CoRR, Vol. abs/2002.02430 (2020). arxiv: 2002.02430 https://arxiv.org/abs/2002.02430
[15]
Gaetano Graf and Heinrich Hussmann. 2020. User Requirements for Remote Teleoperation-based Interfaces. In 12th International Conference on Automotive User Interfaces and Interactive Vehicular Applications. 85--88.
[16]
Robert C Hampshire, Shan Bao, Walter S Lasecki, Andrew Daw, and Jamol Pender. 2020. Beyond safety drivers: Applying air traffic control principles to support the deployment of driverless vehicles. PLoS one, Vol. 15, 5 (2020), e0232837.
[17]
C.-J. Ho and J. Vaughan. 2012a. Online Task Assignment in Crowdsourcing Markets. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1) (2012).
[18]
Chien-Ju Ho and Jennifer Wortman Vaughan. 2012b. Online task assignment in crowdsourcing markets. In Twenty-sixth AAAI conference on artificial intelligence.
[19]
Kuhn H.W. and Yaw B. 1955. The Hungarian method for the assignment problem. Naval Res. Logist. (1955), 83--97.
[20]
KE Jintao, Hai Yang, Jieping Ye, et al. 2020. Learning to delay in ride-sourcing systems: a multi-agent deep reinforcement learning framework. IEEE Transactions on Knowledge and Data Engineering (2020).
[21]
Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An Optimal Algorithm for On-line Bipartite Matching. STOC-90 (1990).
[22]
Zihao Li, Hao Wang, and Zhenzhen Yan. 2023. Fully Online Matching with Stochastic Arrivals and Departures. In AAAI 2023(to be published).
[23]
Philip Almestrand Linné and Jeanette Andersson. 2021. Regulating Road Vehicle Teleoperation: Back to the Near Future. In 2021 IEEE Intelligent Vehicles Symposium Workshops (IV Workshops). IEEE, 135--140.
[24]
Cheng Long, Raymond Chi-Wing Wong, Yu Peng, and Liangliang Ye. 2013. On Good and Fair Paper-Reviewer Assignment. In 2013 IEEE 13th International Conference on Data Mining. 1145--1150. https://doi.org/10.1109/ICDM.2013.13
[25]
Vahideh Manshadi and Scott Rodilitz. 2022. Online policies for efficient volunteer crowdsourcing. Management Science (2022).
[26]
Vahideh H Manshadi, Shayan Oveis Gharan, and Amin Saberi. 2012. Online stochastic matching: Online actions based on offline statistics. Mathematics of Operations Research, Vol. 37, 4 (2012), 559--573.
[27]
Vedant Nanda, Pan Xu, Karthik Abhinav Sankararaman, John Dickerson, and Aravind Srinivasan. 2020. Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34. 2210--2217.
[28]
A. E. Phillips, H. Waterer, M. Ehrgott, and D. M. Ryan. 2015. Integer programming methods for large-scale practical classroom assignment problems. Computers & Operations Research, Vol. 53 (2015), 42--53.
[29]
Guoyang Qin, Qi Luo, Yafeng Yin, Jian Sun, and Jieping Ye. 2021. Optimizing matching time intervals for ride-hailing services using reinforcement learning. Transportation Research Part C: Emerging Technologies, Vol. 129 (2021), 103239.
[30]
Rhonda Righter. 1987. The stochastic sequential assignment problem with random deadlines. Probability in the Engineering and Informational Sciences, Vol. 1, 2 (1987), 189--202.
[31]
Marc Rigter, Danial Dervovic, Parisa Hassanzadeh, Jason Long, Parisa Zehtabi, and Daniele Magazzeni. 2022. Optimal Admission Control for Multiclass Queues with Time-Varying Arrival Rates via State Abstraction. arXiv preprint arXiv:2203.08019 (2022).
[32]
Hanan Rosemarin, Ariel Rosenfeld, Steven Lapp, and Sarit Kraus. 2021. LBA: Online Learning-Based Assignment of Patients to Medical Professionals. Sensors, Vol. 21, 9 (2021), 3021.
[33]
Andreas Schrank and Carmen Kettwich. 2021. Roles in the Teleoperation of Highly Automated Vehicles in Public Transport. (2021).
[34]
Autonomous Solutions. 2022. Teleoperated Mining Vehicles. https://asirobots.com/teleoperated-mining-vehicles/. Accessed: 2022-08--11.
[35]
Felix Tener and Joel Lanir. 2022. Driving from a Distance: Challenges and Guidelines for Autonomous Vehicle Teleoperation Interfaces. In CHI Conference on Human Factors in Computing Systems. 1--13.
[36]
Y. Tong, J. She, B. Ding, L. Wang, and L. Chen. 2016. Online mobile Micro-Task Allocation in spatial crowdsourcing. IEEE 32nd International Conference on Data Engineering (ICDE), 2016 (2016), 49--60.
[37]
Yansheng Wang, Yongxin Tong, Cheng Long, Pan Xu, Ke Xu, and Weifeng Lv. 2019. Adaptive dynamic bipartite graph matching: A reinforcement learning approach. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1478--1489.
[38]
Yifan Xu and Pan Xu. 2020. Trade the System Efficiency for the Income Equality of Drivers in Rideshare. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. 4199--4205.
[39]
Seunghwan Yoon and Mark E Lewis. 2004. Optimal pricing and admission control in a queueing system with periodically varying parameters. Queueing Systems, Vol. 47, 3 (2004), 177--199.
[40]
Tao Zhang. 2020. Toward Automated Vehicle Teleoperation: Vision, Opportunities, and Challenges. IEEE Internet of Things Journal, Vol. 7, 12 (2020), 11347--11354.
Index Terms
- Allocation Problem in Remote Teleoperation: Online Matching with Offline Reusable Resources and Delayed Assignments
Recommendations
Online bipartite matching with unknown distributions
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computingWe consider the online bipartite matching problem in the unknown distribution input model. We show that the Ranking algorithm of [KVV90] achieves a competitive ratio of at least 0.653. This is the first analysis to show an algorithm which breaks the ...
Bipartite Matching for Repeated Allocation Problems
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent SystemsMany applications involving the allocation of resources or tasks can be modeled as matching problems in bipartite graphs. In many of these applications, allocation is performed multiple times. An example is the allocation of classrooms to course ...
Periodic Reranking for Online Matching of Reusable Resources
EC '22: Proceedings of the 23rd ACM Conference on Economics and ComputationWe consider a generalization of the vertex weighted online bipartite matching problem where the offline vertices, called resources, are reusable. In particular, when a resource is matched it is unavailable for a deterministic time duration d after which ...
Comments
Information & Contributors
Information
Published In
May 2023
3131 pages
ISBN:9781450394321
- General Chairs:
- Noa Agmon,
- Bo An,
- Program Chairs:
- Alessandro Ricci,
- William Yeoh
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 30 May 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Israeli Innovation Authority through the Andromeda consortium
- Israel Science Foundation
- EU Project TAILOR
- NSF CRII
Conference
AAMAS '23
Sponsor:
AAMAS '23: International Conference on Autonomous Agents and Multiagent Systems
May 29 - June 2, 2023
London, United Kingdom
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 64Total Downloads
- Downloads (Last 12 months)30
- Downloads (Last 6 weeks)3
Reflects downloads up to 01 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in