Contacts:
Stefan Jorgensen
Stefan Jorgensen is a Ph.D. Candidate in Electrical Engineering (expected graduation early 2018). He received a B.S. in Electrical Engineering at the University of California, Los Angeles in 2013, and M.S. from Stanford University in 2015. Prior to joining Stanford, he spent three summers working on the swarms vs. swarms project with the Advanced Robotic Systems Engineering Laboratory at the Naval Postgraduate School.
Stefan is currently developing algorithms for deployment and coordination of heterogeneous teams in risky environments. In particular, this focuses on extending vehicle routing problems to settings where vehicles can fail permanently. The key insight is to use submodularity and other tools from combinatorial optimization in order to develop relatively efficient algorithms with guaranteed performance. This work has wide applications such as environmental monitoring, delivery in dangerous environments, or search and rescue during storms.
In his free time, Stefan aspires to turn a dirt patch into a garden. Currently it’s still dirt.
Awards:
- NSF Graduate Research Fellowship
- Stanford Engineering Graduate Fellowship
Currently at Area17
ASL Publications
-
S. Jorgensen and M. Pavone, “The Matroid Team Servicing Orienteers Problem and its Variants: Constrained Routing of Heterogeneous Teams with Risky Traversal,” Int. Journal of Robotics Research, vol. 43, no. 1, pp. 34–52, 2024.
Abstract: Consider deploying a team of robots in order to visit sites in a risky environment (i.e., where a robot might be lost during a traversal), subject to team-based operational constraints such as limits on team composition, traffic throughputs, and launch constraints. We formalize this problem using a graph to represent the environment, enforcing probabilistic survival constraints for each robot, and using a matroid (which generalizes linear independence to sets) to capture the team-based operational constraints. The resulting “Matroid Team Surviving Orienteers” (MTSO) problem has broad applications for robotics such as informative path planning, resource delivery, and search and rescue. We demonstrate that the objective for the MTSO problem has submodular structure, which leads us to develop two polynomial time algorithms which are guaranteed to find a solution with value within a constant factor of the optimum. The second of our algorithms is an extension of the accelerated continuous greedy algorithm, and can be applied to much broader classes of constraints while maintaining bounds on suboptimality. In addition to in-depth analysis, we demonstrate the efficiency of our approaches by applying them to a scenario where a team of robots must gather information while avoiding dangers in the Coral Triangle and characterize scaling and parameter selection using a synthetic dataset.
@article{JorgensenPavone2019, author = {Jorgensen, S. and Pavone, M.}, title = {The Matroid Team Servicing Orienteers Problem and its Variants: Constrained Routing of Heterogeneous Teams with Risky Traversal}, journal = {{Int. Journal of Robotics Research}}, volume = {43}, number = {1}, pages = {34--52}, year = {2024}, url = {https://doi.org/10.1177/02783649231210326}, owner = {somrita}, timestamp = {2024-12-29} } -
S. Jorgensen, “Submodular Optimization for Risk-Aware Coordination of Multi-Robot Systems,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2018.
Abstract: Robots are often designed for dangerous environments such as severe storms, but routing algorithms rarely are. This dissertation introduces a new class of routing problems with "risky traversal" where a robot may fail when travelling between two sites. Our key insight is that many objectives in the risky traversal model satisfy a diminishing returns property known as submodularity. We develop a set of tools based on submodular optimization which lead to efficient solutions for a wide variety of problems: (1) The "Team Surviving Orienteers" (TSO) problem, where the size of the team is fixed and we seek routes which maximize the expected rewards collected at nodes, subject to survival probability constraints on each robot. (2) The "On-line TSO" problem, where observations are incorporated to update the paths on-line in a parallel fashion (in response to survival events). (3) The "Heterogeneous TSO" problem, which allows robots to have different capabilities such as sensors (affecting rewards collected), actuation (affecting ability to traverse between sites), and robustness (affecting survival probabilities). (4) The "Matroid TSO" problem, where the set of routes must satisfy an "independence" constraint represented by a matroid, for example limits on the number of each type of robot available, traffic through regions of the environment, total risk budgets for the team, or combinations of these limits. (5) The "Risk Sensitive Coverage" problem, which is the dual to the TSO where the team must satisfy a coverage constraint (e.g., ensure that nodes are visited with specified probabilities) while using minimum resources (e.g., number of robots deployed, distance travelled, or expected number of failures). Our algorithms are based on the approximate greedy algorithm, where we iteratively select a path which approximately maximizes the expected incremental rewards subject to some constraints. Due to the submodular structure of the problems considered in this dissertation, we can prove bounds on the suboptimality of our algorithms. The approach developed in this dissertation provides a foundational set of tools for routing large scale teams in dangerous environments while explicitly planning for robot failure.
@phdthesis{Jorgensen2018, author = {Jorgensen, S.}, title = {Submodular Optimization for Risk-Aware Coordination of Multi-Robot Systems}, school = {{Stanford University, Dept. of Aeronautics and Astronautics}}, year = {2018}, address = {Stanford, California}, month = jun, url = {/wp-content/papercite-data/pdf/Jorgensen.PhD18.pdf}, owner = {bylard}, timestamp = {2019-08-02} } -
S. Jorgensen, R. H. Chen, M. B. Milam, and M. Pavone, “The Team Surviving Orienteers Problem: Routing Teams of Robots in Uncertain Environments with Survival Constraints,” Autonomous Robots, vol. 42, no. 4, pp. 927–952, 2018.
Abstract: We study the following multi-robot coordination problem: given a graph, where each edge is weighted by the probability of surviving while traversing it, find a set of paths for K robots that maximizes the expected number of nodes collectively visited, subject to constraints on the probabilities that each robot survives to its destination. We call this the Team Surviving Orienteers (TSO) problem, which is motivated by scenarios where a team of robots must traverse a dangerous environment, such as aid delivery after disasters. We present the TSO problem formally along with several variants, which represent “survivability-aware" counterparts for a wide range of multi-robot coordination problems such as vehicle routing, patrolling, and informative path planning. We propose an approximate greedy approach for selecting paths, and prove that the value of its output is within a factor 1-exp(-p_s/lambda) of the optimum where p_s is the per-robot survival probability threshold, and 1/lambda < 1 is the approximation factor of an oracle routine for the well-known orienteering problem. We also formalize an on-line update version of the TSO problem, and a generalization to heterogeneous teams where both robot types and paths are selected. Using numerical simulations, we verify that our approach works well in practice and that it scales to problems with hundreds of nodes and tens of robots.
@article{JorgensenChenEtAl2017b, author = {Jorgensen, S. and Chen, R.H. and Milam, M.B. and Pavone, M.}, title = {The Team Surviving Orienteers Problem: Routing Teams of Robots in Uncertain Environments with Survival Constraints}, journal = {{Autonomous Robots}}, volume = {42}, number = {4}, pages = {927--952}, year = {2018}, url = {/wp-content/papercite-data/pdf/Jorgensen.Chen.Milam.Pavone.AURO2017.pdf}, owner = {stefantj}, timestamp = {2018-04-10} } -
S. Jorgensen, R. H. Chen, M. B. Milam, and M. Pavone, “The Risk-Sensitive Coverage Problem: Multi-Robot Routing Under Uncertainty with Service Level and Survival Constraints,” in Proc. IEEE Conf. on Decision and Control, Melbourne, Australia, 2017.
Abstract: Consider a scenario where robots traverse a graph, but crossing each edge bears a risk of failure. A team operator seeks a set of paths for the smallest team which guarantee the probabilities that at least one robot visits each node satisfies specified per-node visit thresholds, and the probabilities each robot reaches its destination satisfy a per-robot survival threshold. We present the Risk-Sensitive Coverage (RSC) problem formally as an instance of the submodular set cover problem and propose an efficient cost-benefit greedy algorithm for finding a feasible set of paths. We prove that the number of robots deployed by our algorithm is no more than (lambda/p_s)(1+log( lambda Delta_K/p_s)) times the smallest team, where Delta_K quantifies the relative benefit of the first and last paths, p_s is the per-robot survival probability threshold and 1/lambda < 1 is the approximation factor of an oracle routine for the well-known orienteering problem. We demonstrate the quality of our solutions by comparing to optimal solutions computed for special cases of the RSC and the efficiency of our approach by applying it to a search and rescue scenario where 225 sites must be visited, each with probability at least 0.95.
@inproceedings{JorgensenChenEtAl2017d, author = {Jorgensen, S. and Chen, R.H. and Milam, M.B. and Pavone, M.}, title = {The Risk-Sensitive Coverage Problem: Multi-Robot Routing Under Uncertainty with Service Level and Survival Constraints}, booktitle = {{Proc. IEEE Conf. on Decision and Control}}, year = {2017}, address = {Melbourne, Australia}, month = dec, url = {/wp-content/papercite-data/pdf/Jorgensen.Chen.Milam.Pavone.CDC17.pdf}, owner = {stefantj}, timestamp = {2018-04-10} } -
S. Jorgensen, R. H. Chen, M. B. Milam, and M. Pavone, “The Matroid Team Surviving Orienteers Problem: Constrained Routing of Heterogeneous Teams with Risky Traversal,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Vancouver, Canada, 2017.
Abstract: Consider a setting where robots must visit nodes in a graph, but each robot may fail when traversing an edge. The goal is to find a set of paths for a team of robots which maximizes the expected number of nodes collectively visited, while guaranteeing that the paths satisfy a notion of "independence" formalized by a matroid (e.g. limits on team size, number of visits to regions), and that the probabilities that each robot survives to its destination are above a given threshold. We call this problem the Matroid Team Surviving Orienteers (MTSO) problem, which has broad applications such as environmental monitoring in risky regions and search and rescue in dangerous conditions. We present the MTSO formally and detail numerous examples of matroids in a path planning context. We then propose an approximate greedy algorithm for selecting a feasible set of paths and prove that the value of the output is within a factor p_s/(p_s+lambda) of the optimum, where p_s is the per-robot survival probability threshold and 1/lambda < 1 is the approximation factor of an oracle routine for the well known orienteering problem. We demonstrate the efficiency of our approach by applying it to a scenario where a team of robots must gather information while avoiding pirates in the Coral Triangle.
@inproceedings{JorgensenChenEtAl2017c, author = {Jorgensen, S. and Chen, R.H. and Milam, M.B. and Pavone, M.}, title = {The Matroid Team Surviving Orienteers Problem: Constrained Routing of Heterogeneous Teams with Risky Traversal}, booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}}, year = {2017}, address = {Vancouver, Canada}, month = sep, url = {/wp-content/papercite-data/pdf/Jorgensen.Chen.Milam.Pavone.IROS2017.pdf}, owner = {stefantj}, timestamp = {2018-04-10} } -
S. Jorgensen, R. H. Chen, M. B. Milam, and M. Pavone, “The Team Surviving Orienteers Problem: Routing Robots in Uncertain Environments with Survival Constraints,” in IEEE Int. Conf. on Robotic Computing, Taichung, Taiwan, 2017.
Abstract: In this paper we study the following multi-robot coordination problem: given a graph, where each edge is weighted by the probability of surviving while traversing it, find a set of paths for K robots that maximizes the expected number of nodes collectively visited, subject to constraints on the probability that each robot survives to its destination. We call this problem the Team Surviving Orienteers (TSO) problem. The TSO problem is motivated by scenarios where a team of robots must traverse a dangerous, uncertain environment, such as aid delivery in disaster or war zones. We present the TSO problem formally along with several variants, which represent "survivability-aware" counterparts for a wide range of multi-robot coordination problems such as vehicle routing, patrolling, and informative path planning. We propose an approximate greedy approach for selecting paths, and prove that the value of its output is bounded within a factor 1 - exp(-p_s/lambda) of the optimum where p_s is the per-robot survival probability threshold, and 1/lambda < 1 is the approximation factor of an oracle routine for the well-known orienteering problem. Our approach has linear time complexity in the team size and polynomial complexity in the graph size. Using numerical simulations, we verify that our approach is close to the optimum in practice and that it scales to problems with hundreds of nodes and tens of robots.
@inproceedings{JorgensenChenEtAl2017, author = {Jorgensen, S. and Chen, R.H. and Milam, M.B. and Pavone, M.}, title = {The Team Surviving Orienteers Problem: Routing Robots in Uncertain Environments with Survival Constraints}, booktitle = {{IEEE Int. Conf. on Robotic Computing}}, year = {2017}, address = {Taichung, Taiwan}, month = apr, url = {/wp-content/papercite-data/pdf/Jorgensen.Chen.Milam.Pavone.ICRC2017.pdf}, owner = {bylard}, timestamp = {2018-04-10} }