Robust Route Planning for Sidewalk Delivery Robots
Pith reviewed 2026-05-19 04:50 UTC · model grok-4.3
The pith
Robust optimization with simulated uncertainty sets improves route reliability for sidewalk delivery robots over shortest paths.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Integrating robust optimization with simulation of robot-pedestrian-obstacle interactions to derive uncertainty sets shows that robust routing significantly enhances operational reliability under variable sidewalk conditions; the ellipsoidal and DRSP methods outperform budgeted and SVC-based alternatives as well as standard shortest-path planning in both average and worst-case delay.
What carries the argument
Robust optimization combined with simulation-generated uncertainty sets for travel times, including ellipsoidal sets and distributionally robust shortest path (DRSP) formulations.
If this is right
- Wider, slower, and more conservative robots gain the largest reliability improvements from robust planning.
- Adverse weather and high pedestrian congestion amplify the advantage of ellipsoidal and DRSP methods over conventional approaches.
- Robust routes maintain better performance across varying environmental conditions than shortest-path routes.
- Operational reliability increases for last-mile sidewalk delivery tasks when uncertainty is explicitly modeled.
- Sensitivity analyses indicate that route planning should be tailored to specific robot designs and congestion levels.
Where Pith is reading between the lines
- The same simulation-plus-robust-optimization pattern could transfer to other slow-moving autonomous vehicles sharing space with people.
- Live sensor data from robots could be used to refresh the uncertainty sets in real time instead of relying on precomputed simulations.
- Extending the model to include predictive crowd dynamics might further tighten the worst-case delay bounds.
- City planners could use these reliability metrics when deciding where to allow or restrict sidewalk robot operations.
Load-bearing premise
The travel times produced by simulating interactions between robots, pedestrians, and obstacles accurately represent real-world uncertainty for constructing the uncertainty sets.
What would settle it
Deploying the computed robust routes on actual robots in Stockholm sidewalks and comparing measured delays against the simulation predictions would confirm or refute the uncertainty models.
Figures
read the original abstract
Sidewalk delivery robots are a promising solution for last-mile freight distribution. Yet, they operate in dynamic environments characterized by pedestrian flows and potential obstacles, which make travel times highly uncertain and can significantly affect their efficiency. This study addresses the robust route planning problem for sidewalk robots by explicitly accounting for travel time uncertainty generated through simulated interactions between robots, pedestrians, and obstacles. Robust optimization is integrated with simulation to reproduce the effect of obstacles and pedestrian flows and generate realistic travel times. Three different approaches to derive uncertainty sets are investigated, including budgeted, ellipsoidal, and support vector clustering (SVC)-based methods, together with a distributionally robust shortest path (DRSP) method based on ambiguity sets that model uncertainty in travel-time distributions. A realistic case study reproducing pedestrian patterns in Stockholm's city center is used to evaluate the efficiency of robust routing across various robot designs and environmental conditions. Results show that, when compared to a conventional shortest path (SP) method, robust routing significantly enhances operational reliability under variable sidewalk conditions. The ellipsoidal and DRSP approaches outperform the other methods in terms of average and worst-case delay. Sensitivity analyses reveal that robust approaches are higher for sidewalk delivery robots that are wider, slower, and more conservative in their navigation behaviors, especially in adverse weather and high pedestrian congestion scenarios.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes robust route planning for sidewalk delivery robots by integrating Monte Carlo simulation of robot-pedestrian-obstacle interactions to generate travel-time uncertainty sets on a Stockholm network model. It compares budgeted, ellipsoidal, SVC-based, and distributionally robust shortest-path (DRSP) methods against conventional shortest-path routing, reporting that ellipsoidal and DRSP approaches yield lower average and worst-case delays under variable conditions, with sensitivity analyses on robot width, speed, and navigation behavior.
Significance. If the simulated uncertainty sets prove representative of real sidewalk dynamics, the framework offers a concrete way to improve reliability for last-mile delivery robots without requiring perfect real-time sensing. The explicit coupling of simulation-derived ambiguity sets with robust optimization, together with the Stockholm case study and parameter-sensitivity results, supplies a reproducible template that other researchers can adapt to different urban networks or robot platforms.
major comments (2)
- [§4] §4: Travel-time uncertainty sets are generated by Monte Carlo runs of the same robot-pedestrian-obstacle simulator that later supplies the test instances used to compute reported delays. Because no calibration to field measurements or out-of-sample real-robot traces is described, any mismatch between simulated kinematics (e.g., pedestrian avoidance, friction under weather) and actual sidewalk behavior directly undermines the claimed reliability gains.
- [Abstract and §5] Abstract and §5: The claim that ellipsoidal and DRSP methods outperform others in average and worst-case delay is presented without quantitative metrics on simulation fidelity, explicit values of the uncertainty-budget parameter, or statistical significance tests (e.g., confidence intervals or p-values across the Monte Carlo replications).
minor comments (2)
- [§5] The post-hoc sensitivity analyses on robot width, speed, and conservative navigation would be stronger if they were part of the primary experimental design rather than presented as supplementary checks.
- [§3] Notation for the three uncertainty-set constructions (budgeted, ellipsoidal, SVC) and the DRSP ambiguity set could be unified in a single table to improve readability.
Simulated Author's Rebuttal
We thank the referee for the constructive and detailed feedback. We address each major comment below, clarifying our approach and outlining the revisions we will implement to improve the manuscript's rigor and transparency.
read point-by-point responses
-
Referee: [§4] §4: Travel-time uncertainty sets are generated by Monte Carlo runs of the same robot-pedestrian-obstacle simulator that later supplies the test instances used to compute reported delays. Because no calibration to field measurements or out-of-sample real-robot traces is described, any mismatch between simulated kinematics (e.g., pedestrian avoidance, friction under weather) and actual sidewalk behavior directly undermines the claimed reliability gains.
Authors: We acknowledge the validity of this concern. Generating uncertainty sets and evaluation instances from the same simulator introduces a risk of optimistic bias if the model does not perfectly replicate real sidewalk dynamics. This is an inherent limitation of purely simulation-based studies when real-world traces are unavailable. In the revised manuscript we will add an explicit limitations subsection in §4 that details the simulator's kinematic assumptions, discusses potential mismatches (including weather effects on friction and more complex pedestrian interactions), and states that all reported reliability gains are conditional on simulation fidelity. We will also expand the conclusions to recommend future calibration against field measurements or out-of-sample robot data as a necessary next step. Because the current work is a simulation-driven proof-of-concept on the Stockholm network, we cannot supply actual calibration results at this time. revision: partial
-
Referee: [Abstract and §5] Abstract and §5: The claim that ellipsoidal and DRSP methods outperform others in average and worst-case delay is presented without quantitative metrics on simulation fidelity, explicit values of the uncertainty-budget parameter, or statistical significance tests (e.g., confidence intervals or p-values across the Monte Carlo replications).
Authors: We agree that additional quantitative detail would strengthen the presentation. The original manuscript reported comparative average and worst-case delays but omitted explicit parameter values and statistical tests for conciseness. In the revision we will: (i) state the concrete uncertainty-budget values (Γ) used for the budgeted and ellipsoidal formulations in §5 and the abstract; (ii) report quantitative simulation-fidelity metrics such as the coefficient of variation of travel times across Monte Carlo runs and the number of replications required for convergence; and (iii) add statistical significance tests, including p-values and 95 % confidence intervals on the performance differences between methods. These additions will be incorporated into the text, tables, and a new supplementary table of replication statistics. revision: yes
Circularity Check
No significant circularity; derivation self-contained within simulation framework
full rationale
The paper generates travel-time uncertainty sets (budgeted, ellipsoidal, SVC, and ambiguity sets for DRSP) from Monte Carlo simulation runs modeling robot-pedestrian-obstacle interactions on a Stockholm network. These sets are then input to robust optimization formulations to compute routes, which are evaluated for average and worst-case delay on case-study instances. No equation or step reduces the reported performance gains to the input data by construction, nor are there load-bearing self-citations, fitted parameters renamed as predictions, or ansatzes smuggled via prior work. The approach is a standard integrated simulation-optimization study whose central claims remain independent of the specific fitted values.
Axiom & Free-Parameter Ledger
free parameters (1)
- uncertainty budget parameter
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We integrate robust and distributionally robust methods with pedestrian simulation to capture realistic sidewalk interactions... three different approaches to derive uncertainty sets... budgeted, ellipsoidal, and support vector clustering (SVC)-based methods, together with a distributionally robust shortest path (DRSP) method
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
The framework of the integration of simulation and optimization is shown in Figure 1... VISWALK is based on the Social Force Model
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
Alves Pessoa, A., Di Puglia Pugliese, L., Guerriero, F., and Poss, M. (2015). Robust constrained shortest path problems under budgeted uncertainty. Networks , 66(2):98--111
work page 2015
-
[2]
Anvari, B. and Wurdemann, H. A. (2020). Modelling social interaction between humans and service robots in large public spaces. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , pages 11189--11196
work page 2020
-
[3]
Ben-Tal, A. and Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research , 23(4):769--805
work page 1998
-
[4]
Ben-Tal, A. and Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters , 25(1):1--13
work page 1999
-
[5]
Bertsimas, D. and Brown, D. (2009). Constructing uncertainty sets for robust linear optimization. Operations Research , 57:1483--1495
work page 2009
-
[6]
Bertsimas, D. and Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming , 98:49--71
work page 2003
- [7]
-
[8]
Bliss, J. (2023). On airport delivery & investor revenue demands. https://www.ottomate.news/p/on-airport-delivery-and-investor
work page 2023
-
[9]
Boysen, N., Fedtke, S., and Schwerdfeger, S. (2021). Last-mile delivery concepts: a survey from an operational research perspective. Or Spectrum , 43(1):1--58
work page 2021
-
[10]
Boysen, N., Schwerdfeger, S., and Weidinger, F. (2018). Scheduling last-mile deliveries with truck-based autonomous robots. European Journal of Operational Research , 271(3):1085--1099
work page 2018
-
[11]
Burns, J. (2016). Domino's pizza robot making deliveries in australia. https://www.forbes.com/sites/janetwburns/2016/03/18/dominos-pizza-robot-is-making-deliveries-in-australia/
work page 2016
-
[12]
Chassein, A., Dokka, T., and Goerigk, M. (2019). Algorithms and uncertainty sets for data-driven robust shortest path problems. European Journal of Operational Research , 274(2):671--686
work page 2019
-
[13]
Chassein, A. B. and Goerigk, M. (2015). A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem. European Journal of Operational Research , 244(3):739--747
work page 2015
-
[14]
Chen, C., Demir, E., Huang, Y., and Qiu, R. (2021). The adoption of self-driving delivery robots in last mile logistics. Transportation Research Part E: Logistics and Transportation Review , 146:102214
work page 2021
-
[15]
Cheng, J., Lisser, A., and Letournel, M. (2013). Distributionally robust stochastic shortest path problem. Electronic Notes in Discrete Mathematics , 41:511--518
work page 2013
-
[16]
Coldewey, D. (2019). Kiwi’s food delivery bots are rolling out to 12 more colleges. https://techcrunch.com/2019/04/25/kiwis-food-delivery-bots-are-rolling-out-to-12-new-colleges/
work page 2019
-
[17]
De Maio , A., Ghiani, G., Laganà, D., and Manni, E. (2024). Sustainable last-mile distribution with autonomous delivery robots and public transportation. Transportation Research Part C: Emerging Technologies , 163:104615
work page 2024
-
[18]
An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems
Dokka, T. and Goerigk, M. (2017). An experimental comparison of uncertainty sets for robust shortest path problems. arXiv preprint arXiv:1704.08470
work page internal anchor Pith review Pith/arXiv arXiv 2017
-
[19]
Du, Y., Hetherington, N. J., Oon, C. L., Chan, W. P., Quintero, C. P., Croft, E., and Machiel Van der Loos, H. (2019). Group surfing: A pedestrian-based approach to sidewalk robot navigation. In 2019 International Conference on Robotics and Automation (ICRA) , pages 6518--6524
work page 2019
-
[20]
G., Glenn Geers , D., Kilby, P., and Li, J
Ensafian, H., Zare Andaryan , A., Bell, M. G., Glenn Geers , D., Kilby, P., and Li, J. (2023). Cost-optimal deployment of autonomous mobile lockers co-operating with couriers for simultaneous pickup and delivery operations. Transportation Research Part C: Emerging Technologies , 146:103958
work page 2023
-
[21]
Ferrer, G., Garrell, A., and Sanfeliu, A. (2013a). Robot companion: A social-force based approach with human awareness-navigation in crowded environments. In 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems , pages 1688--1694
work page 2013
-
[22]
Ferrer, G., Garrell, A., and Sanfeliu, A. (2013b). Social-aware robot navigation in urban environments. In 2013 European Conference on Mobile Robots , pages 331--336
work page 2013
-
[23]
Fossum, M. and Ryeng, E. O. (2021). The walking speed of pedestrians on various pavement surface conditions during winter. Transportation Research Part D: Transport and Environment , 97:102934
work page 2021
-
[24]
Gehrke, S. R., Phair, C. D., Russo, B. J., and Smaglik, E. J. (2023). Observed sidewalk autonomous delivery robot interactions with pedestrians and bicyclists. Transportation Research Interdisciplinary Perspectives , 18:100789
work page 2023
-
[25]
Ghiasvand, M. R. and Rahmani, D. (2023). A novel weighted data-driven robust optimization approach for creating adjustable uncertainty sets. Computers & Chemical Engineering , 178:108390
work page 2023
-
[26]
Giannoulaki, M. and Christoforou, Z. (2024). Pedestrian walking speed analysis: A systematic review. Sustainability , 16(11)
work page 2024
-
[27]
Goerigk, M. and Kurtz, J. (2023). Data-driven robust optimization using deep neural networks. Computers & Operations Research , 151:106087
work page 2023
-
[28]
Algorithm Engineering in Robust Optimization
Goerigk, M. and Sch \"o bel, A. (2015). Algorithm engineering in robust optimization. arXiv preprint arXiv:1505.04901
work page internal anchor Pith review Pith/arXiv arXiv 2015
-
[29]
Gruden, C., I s toka Otkovi \'c , I., S raml, M., et al. (2022). Three-step performance assessment of a pedestrian crossing time prediction model. Transactions on transport sciences , 12(3):13--21
work page 2022
-
[30]
Han, B., Shang, C., and Huang, D. (2021). Multiple kernel learning-aided robust optimization: Learning algorithm, computational tractability, and usage in multi-stage decision-making. European Journal of Operational Research , 292(3):1004--1018
work page 2021
-
[31]
Heimfarth, A., Ostermeier, M., and Hübner, A. (2022). A mixed truck and robot delivery approach for the daily supply of customers. European Journal of Operational Research , 303(1):401--421
work page 2022
-
[32]
Helbing, D. and Molnar, P. (1995). Social force model for pedestrian dynamics. Physical review E , 51(5):4282
work page 1995
-
[33]
Hossain, M. (2022). Self-driving robots: A revolution in the local delivery. https://cmr.berkeley.edu/2022/04/self-driving-robots-a-revolution-in-the-local-delivery/?utm_source=chatgpt.com
work page 2022
-
[34]
Jennings, D. and Figliozzi, M. (2019). Study of sidewalk autonomous delivery robots and their potential impacts on freight efficiency and travel. Transportation Research Record , 2673(6):317--326
work page 2019
-
[35]
Johansson, A., Helbing, D., and Shukla, P. (2008). Specification of a microscopic pedestrian mo del by evolutionary adjustment to video tracking data. arXiv preprint arXiv:0810.4587
work page internal anchor Pith review Pith/arXiv arXiv 2008
-
[36]
Kasperski, A. and Zielinski, P. (2016). Robust Discrete Optimization Under Discrete and Interval Uncertainty: A Survey , volume 241, pages 113--143. Springer International Publishing
work page 2016
-
[37]
Ketkov, S. S., Prokopyev, O. A., and Burashnikov, E. P. (2021). An approach to the distributionally robust shortest path problem. Computers & Operations Research , 130:105212
work page 2021
-
[38]
Kumawat, S., Dudeja, C., and Kumar, P. (2021). An extensive review of shortest path problem solving algorithms. In 2021 5th International Conference on Intelligent Computing and Control Systems (ICICCS) , pages 176--184
work page 2021
-
[39]
Kwon, C., Lee, T., and Berglund, P. G. (2013). Robust shortest path problems with two uncertain multiplicative cost coefficients. Naval Research Logistics (NRL) , 60
work page 2013
-
[40]
Lemardel \'e , C., Estrada, M., Pag \`e s, L., and Bachofner, M. (2021). Potentialities of drones and ground autonomous delivery devices for last-mile logistics. Transportation Research Part E: Logistics and Transportation Review , 149:102325
work page 2021
-
[41]
Li, J., Ensafian, H., Bell, M. G., and Geers, D. G. (2021). Deploying autonomous mobile lockers in a two-echelon parcel operation. Transportation Research Part C: Emerging Technologies , 128:103155
work page 2021
-
[42]
Liang, S., Leng, H., Yuan, Q., Wang, B., and Yuan, C. (2020). How does weather and climate affect pedestrian walking speed during cool and cold seasons in severely cold areas? Building and Environment , 175:106811
work page 2020
-
[43]
Liu, D., Yan, P., Pu, Z., Wang, Y., and Kaisar, E. I. (2021). Hybrid artificial immune algorithm for optimizing a van-robot e-grocery delivery system. Transportation Research Part E: Logistics and Transportation Review , 154:102466
work page 2021
-
[44]
Marks, M. (2019). Robots in space: Sharing the sidewalk with autonomous delivery vehicles. Available at SSRN 3347466
work page 2019
-
[45]
Murray, C. C. and Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies , 54:86--109
work page 2015
-
[46]
Ning, C. and You, F. (2018). Data-driven decision making under uncertainty integrating robust optimization with principal component analysis and kernel smoothing methods. Computers & Chemical Engineering , 112:190--210
work page 2018
- [47]
-
[48]
Roytvand Ghiasvand , M., Rahmani, D., and Moshref-Javadi, M. (2024). Data-driven robust optimization for a multi-trip truck-drone routing problem. Expert Systems with Applications , 241:122485
work page 2024
-
[49]
Shang, C., Huang, X., and You, F. (2017). Data-driven robust optimization based on kernel learning. Computers & Chemical Engineering , 106:464--479. ESCAPE-26
work page 2017
-
[50]
Shang, C. and You, F. (2018). Robust optimization in high-dimensional data space with support vector clustering. IFAC-PapersOnLine , 51(18):19--24. 10th IFAC Symposium on Advanced Control of Chemical Processes ADCHEM 2018
work page 2018
-
[51]
Sharan, S., Surya, R., and Suchithra, R. (2022). Autonomous robot-driven deliveries: A review of recent developments and future directions. Transportation research part E: logistics and transportation review , 165:102834
work page 2022
-
[52]
Shi, X., Xue, S., Feliciani, C., Shiwakoti, N., Lin, J., Li, D., and Ye, Z. (2021). Verifying the applicability of a pedestrian simulation model to reproduce the effect of exit design on egress flow under normal and emergency conditions. Physica A: statistical mechanics and its applications , 562:125347
work page 2021
-
[53]
D., Kutanoglu, E., and Claudel, C
Simoni, M. D., Kutanoglu, E., and Claudel, C. G. (2020). Optimization and analysis of a robot-assisted last mile delivery system. Transportation Research Part E: Logistics and Transportation Review , 142:102049
work page 2020
-
[54]
Resvanor i stockholms län 2015
Stockhlom County (2016). Resvanor i stockholms län 2015. ‘Travel habits in Stockholm County’; in Swedish. https://miljobarometern.stockholm.se/content/docs/tema/trafik/resvanor/RVU-stockholms-lan-2015.pdf
work page 2016
-
[55]
Stockhlom County (2025). Clean air zone class 3. https://trafik.stockholm/en/traffic-safety-and-rules/clean-air-zones/clean-air-zone-class-3/
work page 2025
-
[56]
Stockhloms County (2017). Flödeskarta för gångtrafik. ‘Gångflödeskarta över city’; in Swedish. https://miljobarometern.stockholm.se/content/Trafikrelaterat/G
work page 2017
-
[57]
Truong, X.-T. and Ngo, T. D. (2017). Toward socially aware robot navigation in dynamic and crowded environments: A proactive social motion model. IEEE Transactions on Automation Science and Engineering , 14(4):1743--1760
work page 2017
-
[58]
Ulmer, M. W. and Streng, S. (2019). Same-day delivery with pickup stations and autonomous vehicles. Computers & Operations Research , 108:1--19
work page 2019
- [59]
-
[60]
Wang, Z., You, K., Song, S., and Shang, C. (2019). Data-driven distributionally robust shortest path problem using the wasserstein ambiguity set. In 2019 IEEE 15th International Conference on Control and Automation (ICCA) , pages 1391--1396
work page 2019
-
[61]
Wang, Z., You, K., Song, S., and Zhang, Y. (2020). Wasserstein distributionally robust shortest path problem. European Journal of Operational Research , 284(1):31--43
work page 2020
-
[62]
Yang, Y., Quan, X., and Sun, Y. (2023). Enhanced social force model for service robots in various environments: Calibration and simulation. In 2023 IEEE 13th International Conference on CYBER Technology in Automation, Control, and Intelligent Systems (CYBER) , pages 89--94
work page 2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.