Abstract
Many problems in robotics seek to simultaneously optimize several competing objectives under constraints. A conventional approach to solving such multi-objective optimization problems is to create a single cost function comprised of the weighted sum of the individual objectives. Solutions to this scalarized optimization problem are Pareto optimal solutions to the original multi-objective problem. However, finding an accurate representation of a Pareto front remains an important challenge. Using uniformly spaced weight vectors is often inefficient and does not provide error bounds. Thus, we address the problem of computing a finite set of weight vectors such that for any other weight vector, there exists an element in the set whose error compared to optimal is minimized. To this end, we prove fundamental properties of the optimal cost as a function of the weight vector, including its continuity and concavity. Using these, we propose an algorithm that greedily adds the weight vector least-represented by the current set, and provide bounds on the error. Finally, we illustrate that the proposed approach significantly outperforms uniformly distributed weights for different robot planning problems with varying numbers of objective functions.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ziegler, J., Bender, P., Dang, T., Stiller, C.: Trajectory planning for bertha—a local, continuous method. In: 2014 IEEE Intelligent Vehicles Symposium Proceeding, pp. 450–457 (2014)
Botros, A., Smith, S. L.: Tunable trajectory planner using G3 curves. IEEE Trans. Intell. Veh. (2022)
Bajcsy, A., Losey, D.P., O’Malley, M.K., Dragan, A.D.: Learning robot objectives from physical human interaction. In: Conference on Robot Learning (CoRL). PMLR, pp. 217–226 (2017)
Wilde, N., Blidaru, A., Smith, S.L., Kulić, D.: Improving user specifications for robot behavior through active preference learning: framework and evaluation. Int. J. Robot. Res. 39(6), 651–667 (2020)
Cap, M., Alonso-Mora, J.: Multi-objective analysis of ridesharing in automated mobility-on-demand. In: Robotics: Science and Systems (RSS) (2018)
Marler, R.T., Arora, J.S.: The weighted sum method for multi-objective optimization: new insights. Struct. Multidiscip. Optim. 41(6), 853–862 (2010)
Hwang, C.-L., Masud, A.S.M.: Multiple Objective Decision Making-Methods and Applications: a State-of-the-Art Survey, vol. 164. Springer Science & Business Media (2012)
Sadigh, D., Dragan, A.D., Sastry, S.S., Seshia, S.A.: Active preference-based learning of reward functions. In: Robotics: Science and Systems (RSS) (2017)
Zhang, J.Y., Dragan, A.D.: Learning from extrapolated corrections. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 7034–7040 (2019)
Holladay, R., Javdani, S., Dragan, A., Srinivasa, V.: Active comparison based learning incorporating user uncertainty and noise. In: RSS Workshop on Model Learning for Human-Robot Communication (2016)
Wilde, N., Kulic, D., Smith, S.L.: Active preference learning using maximum regret. In: 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 10 952–10 959 (2020)
Biyik, E., Palan, M., Landolfi, N.C., Losey, D.P., Sadigh, D.: Asking easy questions: a user-friendly approach to active reward learning. In: Conference on Robot Learning (CoRL) (2019)
Levinson, J., Askeland, J., Becker, J., Dolson, J., Held, D., Kammel, S., Kolter, J. Z., Langer, D., Pink, O., Pratt, V., et al. Towards fully autonomous driving: systems and algorithms. In: IEEE Intelligent Vehicles Symposium, pp. 163–168 (2011)
Schütze, O., Cuate, O., Martín, A., Peitz, S., Dellnitz, M.: Pareto explorer: a global/local exploration tool for many-objective optimization problems. Eng. Optim. 52(5), 832–855 (2020)
Dolgov, D., Thrun, S., Montemerlo, M., Diebel, J.: Path planning for autonomous vehicles in unknown semi-structured environments. Int. J. Robot. Res. (IJRR) 29(5), 485–501 (2010)
Zeng, Y., Xu, X., Jin, S., Zhang, R.: Simultaneous navigation and radio mapping for cellular-connected UAV with deep reinforcement learning. IEEE Trans. Wirel. Commun. 20(7), 4205–4220 (2021)
Kent, D., Chernova, S.: Human-centric active perception for autonomous observation. In: 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 1785–1791 (2020)
Cakmak, M., Srinivasa, S.S., Lee, M.K., Forlizzi, J., Kiesler, S.: Human preferences for robot-human hand-over configurations. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1986–1993 (2011)
Basu, C., Singhal, M., Dragan, A.D.: Learning from richer human guidance: augmenting comparison-based learning with feature queries. In: Proceedings of the ACM/IEEE HRI, pp. 132–140 (2018)
Wilde, N., Biyik, E., Sadigh, D., Smith, S. L.: Learning reward functions from scale feedback. In: Conference on Robot Learning (CoRL), pp. 353–362. PMLR (2022)
Bobu, A., Scobee, D.R., Fisac, J.F., Sastry, S.S., Dragan, A.D.: Less is more: rethinking probabilistic models of human behavior. In: Proceedings of the ACM/IEEE HRI, pp. 429–437 (2020)
Pereyra, V., Saunders, M., Castillo, J.: Equispaced pareto front construction for constrained bi-objective optimization. Math. Comput. Model. 57(9–10), 2122–2131 (2013)
Xu, J., Spielberg, A., Zhao, A., Rus, D., Matusik, W.: Multi-objective graph heuristic search for terrestrial robot design. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 9863–9869 (2021)
Parisi, S., Pirotta, M., Peters, J.: Manifold-based multi-objective policy search with sample reuse. Neurocomputing 263, 3–14 (2017)
Lee, J., Yi, D., Srinivasa, S.S.: Sampling of pareto-optimal trajectories using progressive objective evaluation in multi-objective motion planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1–9 (2018)
Wilde, N., Sadeghi, A., Smith, S. L.: Learning submodular objectives for team environmental monitoring. IEEE Robot. Autom. Lett. (RA-L) 7(2), 960–967 (2021)
Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)
Zhang, Q., Li, H.: Moea/d: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)
Wilde, N., Kulic, D., Smith, S.L.: Bayesian active learning for collaborative task specification using equivalence regions. IEEE Robot. Autom. Lett. (RA-L) 4(2), 1691–1698 (2019)
Acknowledgements
This research is partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), as well as by the European Union’s Horizon 2020 research and innovation program under Grant 101017008.
Author information
Authors and Affiliations
Contributions
Alexander Botros, Armin Sadeghi and Nils Wilde contributed equally.
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Botros, A., Sadeghi, A., Wilde, N., Alonso-Mora, J., Smith, S.L. (2023). Error-Bounded Approximation of Pareto Fronts in Robot Planning Problems. In: LaValle, S.M., O’Kane, J.M., Otte, M., Sadigh, D., Tokekar, P. (eds) Algorithmic Foundations of Robotics XV. WAFR 2022. Springer Proceedings in Advanced Robotics, vol 25. Springer, Cham. https://doi.org/10.1007/978-3-031-21090-7_30
Download citation
DOI: https://doi.org/10.1007/978-3-031-21090-7_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-21089-1
Online ISBN: 978-3-031-21090-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)