Code can be found on our GitHub page: StanfordASL

Journal Articles

  1. F. Rossi, R. Zhang, Y. Hindy, and M. Pavone, “Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms,” Autonomous Robots, vol. 42, no. 7, pp. 1427–1442, 2018.

    Abstract: This paper considers the problem of routing and rebalancing a shared fleet of autonomous (i.e., self-driving) vehicles providing on-demand mobility within a capacitated transportation network, where congestion might disrupt throughput. We model the problem within a network flow framework and show that under relatively mild assumptions the rebalancing vehicles, if properly coordinated, do not lead to an increase in congestion (in stark contrast to common belief). From an algorithmic standpoint, such theoretical insight suggests that the problem of routing customers and rebalancing vehicles can be decoupled, which leads to a computationally-efficient routing and rebalancing algorithm for the autonomous vehicles. Numerical experiments and case studies corroborate our theoretical insights and show that the proposed algorithm outperforms state-of-the-art point-to-point methods by avoiding excess congestion on the road. Collectively, this paper provides a rigorous approach to the problem of congestion-aware, system-wide coordination of autonomously driving vehicles, and to the characterization of the sustainability of such robotic systems.

    @article{RossiZhangEtAl2017,
      author = {Rossi, F. and Zhang, R. and Hindy, Y. and Pavone, M.},
      title = {Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms},
      journal = {{Autonomous Robots}},
      volume = {42},
      number = {7},
      pages = {1427--1442},
      year = {2018},
      doi = {10.1007/s10514-018-9750-5},
      url = {../wp-content/papercite-data/pdf/Rossi.Zhang.Hindy.Pavone.AURO17.pdf},
      owner = {frossi2},
      timestamp = {2018-08-07}
    }
    
  2. 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}
    }
    
  3. R. Iglesias, F. Rossi, R. Zhang, and M. Pavone, “A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems,” Int. Journal of Robotics Research, 2018. (In Press)

    Abstract: In this paper we present a queuing network approach to the problem of routing and rebalancing a fleet of self-driving vehicles providing on- demand mobility within a capacitated road network. We refer to such systems as autonomous mobility-on-demand systems, or AMoD. We first cast an AMoD system into a closed, multi-class BCMP queuing network model capable of capturing the passenger arrival process, traffic, the state- of-charge of electric vehicles, and the availability of vehicles at the stations. Second, we propose a scalable method for the synthesis of routing and charging policies, with performance guarantees in the limit of large fleet sizes. Third, we validate the theoretical results on a case study of New York City. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which provides a large set of modeling options (e.g., the inclusion of road capacities and charging constraints), and subsumes earlier Jackson and network flow models.

    @article{IglesiasRossiEtAl2017,
      author = {Iglesias, R. and Rossi, F. and Zhang, R. and Pavone, M.},
      title = {A {BCMP} Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems},
      journal = {{Int. Journal of Robotics Research}},
      year = {2018},
      note = {In Press},
      url = {../wp-content/papercite-data/pdf/Iglesias.Rossi.Zhang.Pavone.IJRR18.pdf},
      keywords = {press},
      owner = {rdit},
      timestamp = {2018-05-06}
    }
    
  4. L. Janson, B. Ichter, and M. Pavone, “Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance,” Int. Journal of Robotics Research, vol. 37, no. 1, pp. 46–61, 2018.

    Abstract: Probabilistic sampling-based algorithms, such as the probabilistic roadmap (PRM) and the rapidly-exploring random tree (RRT) algorithms, represent one of the most successful approaches to robotic motion planning, due to their strong theoretical properties (in terms of probabilistic completeness or even asymptotic optimality) and remarkable practical performance. Such algorithms are probabilistic in that they compute a path by connecting independently and identically distributed (i.i.d.) random points in the configuration space. Their randomization aspect, however, makes several tasks challenging, including certification for safety-critical applications and use of offline computation to improve real-time execution. Hence, an important open question is whether similar (or better) theoretical guarantees and practical performance could be obtained by considering deterministic, as opposed to random sampling sequences. The objective of this paper is to provide a rigorous answer to this question. Specifically, we first show that PRM, for a certain selection of tuning parameters and deterministic low-dispersion sampling sequences, is deterministically asymptotically optimal, i.e., it returns a path whose cost converges deterministically to the optimal one as the number of points goes to infinity. Second, we characterize the convergence rate, and we find that the factor of sub-optimality can be very explicitly upper-bounded in terms of the l2-dispersion of the sampling sequence and the connection radius of PRM. Third, we show that an asymptotically optimal version of PRM exists with computational and space complexity arbitrarily close to O(n) (the theoretical lower bound), where n is the number of points in the sequence. This is in stark contrast to the O(n log n) complexity results for existing asymptotically- optimal probabilistic planners. Fourth, we show that our theoretical results and insights extend to other batch-processing algorithms such as FMT*, to non-uniform sampling strategies, to k-nearest-neighbor implementations, and to differentially- constrained problems. Finally, through numerical experiments, we show that planning with deterministic low-dispersion sampling generally provides superior performance in terms of path cost and success rate.

    @article{JansonIchterEtAl2015,
      author = {Janson, L. and Ichter, B. and Pavone, M.},
      title = {Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance},
      journal = {{Int. Journal of Robotics Research}},
      volume = {37},
      number = {1},
      pages = {46--61},
      year = {2018},
      doi = {10.1177/0278364917714338},
      url = {../wp-content/papercite-data/pdf/Janson.Ichter.Pavone.IJRR18.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  5. F. Rossi, R. Iglesias, M. Alizadeh, and M. Pavone, “On the Interaction Between Autonomous Mobility-on-Demand Systems and the Power Network: Models and Coordination Algorithms,” IEEE Transactions on Control of Network Systems, 2018. (Submitted)

    Abstract: We study the interaction between a fleet of electric, self-driving vehicles servicing on-demand transportation requests (referred to as Autonomous Mobility-on-Demand, or AMoD, system) and the electric power network. We propose a joint model that captures the coupling between the two systems stemming from the vehicles? charging requirements. The model captures time-varying customer demand and power generation costs, road congestion, battery depreciation, and power transmission and distribution constraints. We then leverage the model to jointly optimize the operation of both systems. We devise an algorithmic procedure to losslessly reduce the problem size by bundling customer requests, allowing it to be efficiently solved by off-the-shelf linear programming solvers. Next, we show that the socially optimal solution to the joint problem can be enforced as a general equilibrium, and we provide a dual decomposition algorithm that allows the transportation and power network operators to compute the market clearing prices without sharing private information. We assess the performance of the model and algorithms by studying a hypothetical electric-powered AMoD system in Dallas-Fort Worth and its impact on the Texas power network. Lack of coordination between the AMoD system and the power network would cause a 4.4% increase in the price of electricity in Dallas-Fort Worth; conversely, depending on the maturity of battery technology, coordination between the AMoD system and the power network would reduce the total electricity expenditure compared to the case where no cars are present (despite the increased demand for electricity) and yield savings of up to $147M/year for local power network customers. Agent-based simulations with receding-horizon versions of the algorithms further corroborate these findings. Collectively, the results of this paper provide a first-of-a-kind characterization of the interaction between electric-powered AMoD systems and the power network, and shed additional light on the economic and societal value of AMoD.

    @article{RossiIglesiasEtAl2018b,
      author = {Rossi, F. and Iglesias, R. and Alizadeh, M. and Pavone, M.},
      title = {On the Interaction Between {Autonomous Mobility-on-Demand} Systems and the Power Network: Models and Coordination Algorithms},
      journal = {{IEEE Transactions on Control of Network Systems}},
      year = {2018},
      note = {Submitted. {Extended version available at }\url{https://arxiv.org/abs/1709.04906}},
      url = {../wp-content/papercite-data/pdf/Rossi.Iglesias.Alizadeh.Pavone.TCNS18.pdf},
      keywords = {sub},
      owner = {frossi2},
      timestamp = {2018-06-30}
    }
    
  6. M. Schiffer, N. Boysen, G. Laporte, and M. Pavone, “Optimal picking policies in e-commerce warehouses,” Management Science, 2018. (Submitted)

    Abstract: In e-commerce warehouses, online retailers increase their efficiency by using a mixed-shelves (or scattered storage) concept, where unit loads are purposefully broken down into single items, which are individually stored in multiple locations. Irrespective of the stock keeping units a customer jointly orders, this storage strategy increases the likelihood that somewhere in the warehouse the items of the requested stock keeping units will be in close vicinity, which may significantly reduce an order picker’s unproductive walking time. This paper optimizes picker routing through such mixed-shelves warehouses. Specifically, we introduce a generic exact algorithm that covers a multitude of picking policies, independently of the underlying picking zone layout, and is suitable for real-time applications. Besides its generality, this algorithm provides a new state of the art in terms of solvable instance sizes and computational times, providing average reductions of 67% compared with the best known algorithm. Using this algorithm we compare three different real-world e-commerce warehouse settings that differ slightly in their application of scattered storage and in their picking policies. Our results reveal that the right combination of drop-off points, dynamic batching, the utilization of picking carts, and the picking zone layout can greatly improve the picking performance. In particular, some combinations of policies yield efficiency increases of more than 30%.

    @article{SchifferBoysenEtAl2018,
      author = {Schiffer, M. and Boysen, N. and Laporte, G. and Pavone, M.},
      title = {Optimal picking policies in e-commerce warehouses},
      journal = {{Management Science}},
      year = {2018},
      note = {Submitted},
      keywords = {sub},
      owner = {schiffer},
      timestamp = {2018-08-14}
    }
    
  7. S. P. Chinchali, S. C. Livingston, M. Chen, and M. Pavone, “Multi-objective optimal control for proactive decision-making with temporal logic models,” Int. Journal of Robotics Research, 2018. (Submitted)

    Abstract: The operation of today’s robots entails interactions with humans, e.g., in autonomous driving amidst human-driven vehicles. To effectively do so, robots must proactively decode the intent of humans and concurrently leverage this knowledge for safe, cooperative task satisfaction—a problem we refer to as proactive decision making. However, simultaneous intent decoding and robotic control requires reasoning over several possible human behavioral models, resulting in high-dimensional state trajectories. In this paper, we address the proactive decision making problem using a novel combination of formal methods, control, and data mining techniques. First, we distill high-dimensional state trajectories of human-robot interaction into concise, symbolic behavioral summaries that can be learned from data. Second, we leverage formal methods to model high-level agent goals, safe interaction, and information-seeking behavior with temporal logic formulae. Finally, we design a novel decision-making scheme that maintains a belief distribution over models of human behavior, and proactively plans informative actions. After showing several desirable theoretical properties, we apply our framework to a dataset of humans driving in crowded merging scenarios. For it, temporal logic models are generated and used to synthesize control strategies using tree-based value iteration and deep reinforcement learning (RL). Additionally, we illustrate how data-driven models of human responses to informative robot probes, such as from generative models like Conditional Variational Autoencoders (CVAEs), can be clustered with formal specifications. Results from simulated self-driving car scenarios demonstrate that data-driven strategies enable safe interaction, correct model identification, and significant dimensionality reduction.

    @article{ChinchaliLivingstonEtAl2018,
      author = {Chinchali, S. P. and Livingston, S. C. and Chen, M. and Pavone, M.},
      title = {Multi-objective optimal control for proactive decision-making with temporal logic models},
      journal = {{Int. Journal of Robotics Research}},
      year = {2018},
      note = {Submitted},
      url = {../wp-content/papercite-data/pdf/Chinchali.Livingston.Chen.Pavone.IJRR18.pdf},
      keywords = {sub},
      owner = {SCL},
      timestamp = {2018-06-26}
    }
    
  8. S. Singh, Y.-L. Chow, A. Majumdar, and M. Pavone, “A Framework for Time-Consistent, Risk-Sensitive Model Predictive Control: Theory and Algorithms,” IEEE Transactions on Automatic Control, 2018. (In Press)

    Abstract: In this paper we present a framework for risk-sensitive model predictive control (MPC) of linear systems affected by stochastic multiplicative uncertainty. Our key innovation is to consider a time-consistent, dynamic risk evaluation of the cumulative cost as the objective function to be minimized. This framework is axiomatically justified in terms of time-consistency of risk assessments, is amenable to dynamic optimization, and is unifying in the sense that it captures a full range of risk preferences from risk-neutral (i.e., expectation) to worst case. Within this framework, we propose and analyze an online risk-sensitive MPC algorithm that is provably stabilizing. Furthermore, by exploiting the dual representation of time-consistent, dynamic risk measures, we cast the computation of the MPC control law as a convex optimization problem amenable to real-time implementation. Simulation results are presented and discussed.

    @article{SinghChowEtAl2018b,
      author = {Singh, S. and Chow, Y.-L. and Majumdar, A. and Pavone, M.},
      title = {A Framework for Time-Consistent, Risk-Sensitive Model Predictive Control: Theory and Algorithms},
      journal = {{IEEE Transactions on Automatic Control}},
      year = {2018},
      note = {{In Press, Available at:} \url{http://arxiv.org/abs/1703.01029}},
      url = {http://arxiv.org/pdf/1703.01029.pdf},
      keywords = {press},
      owner = {ssingh19},
      timestamp = {2018-09-21}
    }
    
  9. R. Allen and M. Pavone, “A Real-Time Framework for Kinodynamic Planning in Dynamic Environments with Application to Quadrotor Obstacle Avoidance,” Robotics and Autonomous Systems, 2018. (Submitted)

    Abstract: The objective of this paper is to present a full-stack, real-time motion planning framework for kinodynamic robots and then show how it is applied and demonstrated on a real-world quadrotor system. The proposed framework utilizes an offline-online computation paradigm, neighborhood classification through machine learning, sampling-based motion planning with an optimal cost distance metric, and trajectory smoothing to achieve real-time planning for aerial vehicles. This framework accounts for dynamic obstacles with an event-based replanning structure and a locally reactive control layer that minimizes replanning events. The approach is demonstrated on a quadrotor navigating moving obstacles in an indoor space and stands as, arguably, one of the first demonstrations of full-online kinodynamic motion planning, with execution cycles of 3 Hz to 5 Hz. For the quadrotor, a simplified dynamics model is used during the planning phase to accelerate online computation. A trajectory smoothing phase, which leverages the differentially flat nature of quadrotor dynamics, is then implemented to guarantee a dynamically feasible trajectory.

    @article{AllenPavone2018,
      author = {Allen, R. and Pavone, M.},
      title = {A Real-Time Framework for Kinodynamic Planning in Dynamic Environments with Application to Quadrotor Obstacle Avoidance},
      journal = {{Robotics and Autonomous Systems}},
      year = {2018},
      note = {Submitted},
      url = {../wp-content/papercite-data/pdf/Allen.Pavone.RAS18.pdf},
      keywords = {sub},
      owner = {bylard},
      timestamp = {2018-04-05}
    }
    
  10. S. Singh, J. Lacotte, A. Majumdar, and M. Pavone, “Risk-sensitive Inverse Reinforcement Learning via Semi- and Non-Parametric Methods,” Int. Journal of Robotics Research, 2018. (In Press)

    Abstract: The literature on Inverse Reinforcement Learning (IRL) typically assumes that humans take actions in order to minimize the expected value of a cost function, i.e., that humans are risk neutral. Yet, in practice, humans are often far from being risk neutral. To fill this gap, the objective of this paper is to devise a framework for risk-sensitive IRL in order to explicitly account for a human’s risk sensitivity. To this end, we propose a flexible class of models based on coherent risk measures, which allow us to capture an entire spectrum of risk preferences from risk-neutral to worst-case. We propose efficient non-parametric algorithms based on linear programming and semi-parametric algorithms based on maximum likelihood for inferring a human’s underlying risk measure and cost function for a rich class of static and dynamic decision-making settings. The resulting approach is demonstrated on a simulated driving game with ten human participants. Our method is able to infer and mimic a wide range of qualitatively different driving styles from highly risk-averse to risk-neutral in a data-efficient manner. Moreover, comparisons of the Risk-Sensitive (RS) IRL approach with a risk-neutral model show that the RS-IRL framework more accurately captures observed participant behavior both qualitatively and quantitatively, especially in scenarios where catastrophic outcomes such as collisions can occur.

    @article{SinghLacotteEtAl2018,
      author = {Singh, S. and Lacotte, J. and Majumdar, A. and Pavone, M.},
      title = {Risk-sensitive Inverse Reinforcement Learning via Semi- and Non-Parametric Methods},
      journal = {{Int. Journal of Robotics Research}},
      year = {2018},
      note = {In Press},
      url = {https://arxiv.org/pdf/1711.10055.pdf},
      keywords = {press},
      owner = {ssingh19},
      timestamp = {2018-03-30}
    }
    
  11. R. Zhang, F. Rossi, and M. Pavone, “Analysis, Control, and Evaluation of Mobility-on-Demand Systems: a Queueing-Theoretical Approach,” IEEE Transactions on Control of Network Systems, 2018. (In Press)

    Abstract: This paper presents a queueing-theoretical approach to the analysis, control, and evaluation of mobility-on-demand (MoD) systems for urban personal transportation. A MoD system consists of a fleet of vehicles providing one-way car sharing service and a team of drivers to rebalance such vehicles. The drivers then rebalance themselves by driving select customers similar to a taxi service. We model the MoD system as two coupled closed Jackson networks with passenger loss. We show that the system can be approximately balanced by solving two decoupled linear programs and exactly balanced through nonlinear optimization. The rebalancing techniques are applied to a system sizing example using taxi data in three neighborhoods of Manhattan. Lastly, we formulate a real-time closed-loop rebalancing policy for drivers and perform case studies of two hypothetical MoD systems in Manhattan and Hangzhou, China. We show that the taxi demand in Manhattan can be met with the same number of vehicles in a MoD system, but only require 1/3 to 1/4 the number of drivers; in Hangzhou, where customer demand is highly unbalanced, higher driver-to-vehicle ratios are required to achieve good quality of service.

    @article{ZhangPavone2018,
      author = {Zhang, R. and Rossi, F. and Pavone, M.},
      title = {Analysis, Control, and Evaluation of Mobility-on-Demand Systems: a Queueing-Theoretical Approach},
      journal = {{IEEE Transactions on Control of Network Systems}},
      year = {2018},
      note = {In Press},
      doi = {10.1109/TCNS.2018.2800403},
      url = {../wp-content/papercite-data/pdf/Zhang.Rossi.Pavone.TCNS18.pdf},
      keywords = {press},
      owner = {frossi2},
      timestamp = {2017-12-30}
    }
    
  12. Y. Chow, M. Ghavamzadeh, L. Janson, and M. Pavone, “Risk-Constrained Reinforcement Learning with Percentile Risk Criteria,” Journal of Machine Learning Research, 2018.

    Abstract: In many sequential decision-making problems one is interested in minimizing an expected cumulative cost while taking into account risk, i.e., increased awareness of events of small probability and high consequences. Accordingly, the objective of this paper is to present efficient reinforcement learning algorithms for risk-constrained Markov decision processes (MDPs), where risk is represented via a chance constraint or a constraint on the conditional value-at-risk (CVaR) of the cumulative cost. We collectively refer to such problems as percentile risk-constrained MDPs. Specifically, we first derive a formula for computing the gradient of the Lagrangian function for percentile risk-constrained MDPs. Then, we devise policy gradient and actor-critic algorithms that (1) estimate such gradient, (2) update the policy parameters in the descent direction, and (3) update the Lagrange multiplier in the ascent direction. For these algorithms we prove convergence to locally-optimal policies. Finally, we demonstrate the effectiveness of our algorithms in an optimal stopping problem and an online marketing application.

    @article{ChowGhavamzadehEtAl2016,
      author = {Chow, Y. and Ghavamzadeh, M. and Janson, L. and Pavone, M.},
      title = {Risk-Constrained Reinforcement Learning with Percentile Risk Criteria},
      journal = {{Journal of Machine Learning Research}},
      year = {2018},
      url = {../wp-content/papercite-data/pdf/Chow.Ghavamzadeh.Janson.Pavone.JMLR18.pdf},
      owner = {bylard},
      timestamp = {2018-06-03}
    }
    
  13. J. A. Starek, E. Schmerling, G. D. Maher, B. W. Barbee, and M. Pavone, “Fast, Safe, Propellant-Efficient Spacecraft Motion Planning Under Clohessy-Wiltshire-Hill Dynamics,” AIAA Journal of Guidance, Control, and Dynamics, vol. 40, no. 2, pp. 418–438, 2017.

    Abstract: This paper presents a sampling-based motion planning algorithm for real-time and propellant-optimized autonomous spacecraft trajectory generation in near-circular orbits. Specifically, this paper leverages recent algorithmic advances in the field of robot motion planning to the problem of impulsively-actuated, propellant-optimized rendezvous and proximity operations under the Clohessy-Wiltshire-Hill (CWH) dynamics model. The approach calls upon a modified version of the Fast Marching Tree (FMT*) algorithm to grow a set of feasible trajectories over a deterministic, low-dispersion set of sample points covering the free state space. To enforce safety, the tree is only grown over the subset of actively-safe samples, from which there exists a feasible one-burn collision avoidance maneuver that can safely circularize the spacecraft orbit along its coasting arc under a given set of potential thruster failures. Key features of the proposed algorithm include: (i) theoretical guarantees in terms of trajectory safety and performance, (ii) amenability to real-time implementation, and (iii) generality, in the sense that a large class of constraints can be handled directly. As a result, the proposed algorithm offers the potential for widespread application, ranging from on-orbit satellite servicing to orbital debris removal and autonomous inspection missions.

    @article{StarekSchmerlingEtAl2016,
      author = {Starek, J. A. and Schmerling, E. and Maher, G. D. and Barbee, B. W. and Pavone, M.},
      title = {Fast, Safe, Propellant-Efficient Spacecraft Motion Planning Under {Clohessy}-{Wiltshire}-{Hill} Dynamics},
      journal = {{AIAA Journal of Guidance, Control, and Dynamics}},
      volume = {40},
      number = {2},
      pages = {418--438},
      year = {2017},
      doi = {10.2514/1.g001913},
      url = {../wp-content/papercite-data/pdf/Starek.Schmerling.ea.JGCD16.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  14. B. Hockman, A. Frick, I. A. D. Nesnas, and M. Pavone, “Design, Control, and Experimentation of Internally-Actuated Rovers for the Exploration of Low-Gravity Planetary Bodies,” Journal of Field Robotics, vol. 34, no. 1, pp. 5–24, 2016.

    Abstract: In this paper we discuss the design, control, and experimentation of internally-actuated rovers for the exploration of low-gravity (micro-g to milli-g) planetary bodies, such as asteroids, comets, or small moons. The actuation of the rover relies on spinning three internal flywheels, which allows all subsystems to be packaged in one sealed enclosure and enables the platform to be minimalistic, thereby reducing its cost. By controlling flywheels’ spin rate, the rover is capable of achieving large surface coverage by attitude-controlled hops, fine mobility by tumbling, and coarse instrument pointing by changing orientation relative to the ground. We discuss the dynamics of such rovers, their control, and key design features (e.g., flywheel design and orientation, geometry of external spikes, and system engineering aspects). We then discuss the design and control of a first-of-a-kind test bed, which allows the accurate emulation of a microgravity environment for mobility experiments and consists of a 3 DoF gimbal attached to an actively controlled gantry crane. Finally, we present experimental results on the test bed that provide key insights for control and validate the theoretical analysis.

    @article{HockmanFrickEtAl2016,
      author = {Hockman, B. and Frick, A. and Nesnas, I. A. D. and Pavone, M.},
      title = {Design, Control, and Experimentation of Internally-Actuated Rovers for the Exploration of Low-Gravity Planetary Bodies},
      journal = {{Journal of Field Robotics}},
      volume = {34},
      number = {1},
      pages = {5--24},
      year = {2016},
      doi = {10.1002/rob.21656},
      url = {../wp-content/papercite-data/pdf/Hockman.Pavone.ea.JFR15.pdf},
      owner = {bylard},
      timestamp = {2017-08-11}
    }
    
  15. R. Zhang and M. Pavone, “Control of Robotic Mobility-on-Demand Systems: A Queueing-Theoretical Perspective,” Int. Journal of Robotics Research, vol. 35, no. 1–3, pp. 186–203, 2016.

    Abstract: In this paper we present and analyze a queueing-theoretical model for autonomous mobility-on-demand (MOD) systems where robotic, self-driving vehicles transport customers within an urban environment and rebalance themselves to ensure acceptable quality of service throughout the entire network. We cast an autonomous MOD system within a closed Jackson network model with passenger loss. It is shown that an optimal rebalancing algorithm minimizing the number of (autonomously) rebalancing vehicles and keeping vehicles availabilities balanced throughout the network can be found by solving a linear program. The theoretical insights are used to design a robust, real-time rebalancing algorithm, which is applied to a case study of New York City. The case study shows that the current taxi demand in Manhattan can be met with about 8,000 robotic vehicles (roughly 60% of the size of the current taxi fleet). Finally, we extend our queueing-theoretical setup to include congestion effects, and we study the impact of autonomously rebalancing vehicles on overall congestion. Collectively, this paper provides a rigorous approach to the problem of system-wide coordination of autonomously driving vehicles, and provides one of the first characterizations of the sustainability benefits of robotic transportation networks.

    @article{ZhangPavone2016,
      author = {Zhang, R. and Pavone, M.},
      title = {Control of Robotic {Mobility-on-Demand} Systems: A Queueing-Theoretical Perspective},
      journal = {{Int. Journal of Robotics Research}},
      volume = {35},
      number = {1--3},
      pages = {186--203},
      year = {2016},
      doi = {10.1177/0278364915581863},
      url = {http://web.stanford.edu/~pavone/IJRR_Submission/Zhang.Pavone.IJRR15.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  16. R. Allen, M. Pavone, and M. Schwager, “Flying Smartphones: When Portable Computing Sprouts Wings,” IEEE Pervasive Computing, vol. 15, no. 3, pp. 83–88, 2016.

    Abstract: Lightweight, highly autonomous drones that can actively interact with the world are emerging as the next step-change in consumer electronic technology, much in the same way that smart phones revolutionized personal computing..

    @article{AllenPavoneEtAl2016,
      author = {Allen, R. and Pavone, M. and Schwager, M.},
      title = {Flying Smartphones: When Portable Computing Sprouts Wings},
      journal = {{IEEE Pervasive Computing}},
      volume = {15},
      number = {3},
      pages = {83--88},
      year = {2016},
      doi = {10.1109/MPRV.2016.43},
      url = {../wp-content/papercite-data/pdf/Allen.Pavone.Schwager.PC16.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  17. L. Janson, E. Schmerling, A. Clark, and M. Pavone, “Fast Marching Tree: A Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions,” Int. Journal of Robotics Research, vol. 34, no. 7, pp. 883–921, 2015.

    Abstract: In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a "lazy" dynamic programming recursion on a predetermined number of probabilistically-drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds–the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O(n-1/d+rho), where n is the number of sampled points, d is the dimension of the configuration space, and rho is an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our theoretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.

    @article{JansonSchmerlingEtAl2015,
      author = {Janson, L. and Schmerling, E. and Clark, A. and Pavone, M.},
      title = {{Fast} {Marching} {Tree:} A Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions},
      journal = {{Int. Journal of Robotics Research}},
      volume = {34},
      number = {7},
      pages = {883--921},
      year = {2015},
      doi = {10.1177/0278364915577958},
      url = {http://arxiv.org/pdf/1306.3532.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  18. M. Ono, M. Pavone, Y. Kuwata, and J. Balaram, “Chance-Constrained Dynamic Programming with Application to Risk-Aware Robotic Space Exploration,” Autonomous Robots, vol. 39, no. 4, pp. 555–571, 2015.

    Abstract: Existing approaches to constrained dynamic programming are limited to formulations where the constraints share the same additive structure of the objective function (that is, they can be represented as an expectation of the summation of one-stage costs). As such, these formulations cannot handle joint probabilistic (chance) constraints, whose structure is not additive. To bridge this gap, this paper presents a novel algorithmic approach for joint chance-constrained dynamic programming problems, where the probability of failure to satisfy given state constraints is explicitly bounded. Our approach is to (conservatively) reformulate a joint chance constraint as a constraint on the expectation of a summation of indicator random variables, which can be incorporated into the cost function by considering a dual formulation of the optimization problem. As a result, the primal variables can be optimized by standard dynamic programming, while the dual variable is optimized by a root-finding algorithm that converges exponentially. Error bounds on the primal and dual objective values are rigorously derived. We demonstrate algorithm effectiveness on three optimal control problems, namely a path planning problem, a Mars entry, descent and landing problem, and a Lunar landing problem. All Mars simulations are conducted using real terrain data of Mars, with four million discrete states at each time step. The numerical experiments are used to validate our theoretical and heuristic arguments that the proposed algorithm is both (i) computationally efficient, i.e., capable of handling real-world problems, and (ii) near-optimal, i.e., its degree of conservatism is very low.

    @article{OnoPavoneEtAl2015,
      author = {Ono, M. and Pavone, M. and Kuwata, Y. and Balaram, J.},
      title = {Chance-Constrained Dynamic Programming with Application to Risk-Aware Robotic Space Exploration},
      journal = {{Autonomous Robots}},
      volume = {39},
      number = {4},
      pages = {555--571},
      year = {2015},
      doi = {10.1007/s10514-015-9467-7},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://web.stanford.edu/~pavone/papers/Ono.Pavone.ea.AURO14.pdf}
    }
    
  19. Y. Chow, M. Pavone, B. M. Sadler, and S. Carpin, “Trading Safety Versus Performance: Rapid Deployment of Robotic Swarms with Robust Performance Constraints,” ASME Journal of Dynamic Systems, Measurement, and Control, vol. 137, no. 3, pp. 031005.1–031005.11, 2014.

    Abstract: In this paper we consider a stochastic deployment problem, where a robotic swarm is tasked with the objective of positioning at least one robot at each of a set of pre-assigned targets while meeting a temporal deadline. Travel times and failure rates are stochastic but related, inasmuch as failure rates increase with speed. To maximize chances of success while meeting the deadline, a control strategy has therefore to balance safety and performance. Our approach is to cast the problem within the theory of constrained Markov Decision Processes, whereby we seek to compute policies that maximize the probability of successful deployment while ensuring that the expected duration of the task is bounded by a given deadline. To account for uncertainties in the problem parameters, we consider a robust formulation and we propose efficient solution algorithms, which are of independent interest. Numerical experiments confirming our theoretical results are presented and discussed.

    @article{ChowPavoneEtAl2014,
      author = {Chow, Y. and Pavone, M. and Sadler, B. M. and Carpin, S.},
      title = {Trading Safety Versus Performance: Rapid Deployment of Robotic Swarms with Robust Performance Constraints},
      journal = {{ASME Journal of Dynamic Systems, Measurement, and Control}},
      volume = {137},
      number = {3},
      pages = {031005.1--031005.11},
      year = {2014},
      doi = {10.1115/1.4028117},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://web.stanford.edu/~pavone/papers/Chow.Pavone.ea.ASME14.pdf}
    }
    
  20. K. Treleaven, M. Pavone, and E. Frazzoli, “Asymptotically Optimal Algorithms for One-to-One Pickup and Delivery Problems with Applications to Transportation Systems,” IEEE Transactions on Automatic Control, vol. 58, no. 9, pp. 2261–2276, 2013.

    Abstract: Pickup and delivery problems (PDPs), in which objects or people have to be transported between specific locations, are among the most common combinatorial problems in real-world logistical operations. A widely-encountered type of PDP is the Stacker Crane Problem (SCP), where each commodity/customer is associated with a pickup location and a delivery location, and the objective is to find a minimum-length tour visiting all locations with the constraint that each pickup location and its associated delivery location are visited in immediate, consecutive order. The SCP is NP-Hard and the best known approximation algorithm only provides a 9/5 approximation ratio. In this paper, we examine an embedding of the SCP within a stochastic framework, and our objective is three-fold: First, we describe a large class of algorithms for the SCP, where every member is asymptotically optimal, i.e., it produces, almost surely, a solution approaching the optimal one as the number of pickups/deliveries goes to infinity; moreover, one can achieve computational complexity O(n^2+ε) within the class, where n is the number of pickup/delivery pairs and εis an arbitrarily small positive constant. Second, we characterize the length of the optimal SCP tour asymptotically. Finally, we study a dynamic version of the SCP, whereby pickup and delivery requests arrive according to a Poisson process, and which serves as a model for large-scale demand-responsive transport (DRT) systems. For such a dynamic counterpart of the SCP, we derive a necessary and sufficient condition for the existence of stable vehicle routing policies, which depends only on the workspace geometry, the distributions of pickup and delivery points, the arrival rate of requests, and the number of vehicles. Our results leverage a novel connection between the Euclidean Bipartite Matching Problem and the theory of random permutations, and, for the dynamic setting, exhibit novel features that are absent in traditional spatially-distributed queueing systems.

    @article{TreleavenPavoneEtAl2013,
      author = {Treleaven, K. and Pavone, M. and Frazzoli, E.},
      title = {Asymptotically Optimal Algorithms for One-to-One Pickup and Delivery Problems with Applications to Transportation Systems},
      journal = {{IEEE Transactions on Automatic Control}},
      volume = {58},
      number = {9},
      pages = {2261--2276},
      year = {2013},
      doi = {10.1109/TAC.2013.2259993},
      url = {../wp-content/papercite-data/pdf/Treleaven.Pavone.ea.TAC13.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  21. M. Pavone, S. L. Smith, E. Frazzoli, and D. Rus, “Robotic Load Balancing for Mobility-on-Demand Systems,” Int. Journal of Robotics Research, vol. 31, no. 7, pp. 839–854, 2012.

    Abstract: In this paper we develop methods for maximizing the throughput of a mobility-on-demand urban transportation system. We consider a finite group of shared vehicles, located at a set of stations. Users arrive at the stations, pick-up vehicles, and drive (or are driven) to their destination station where they drop-off the vehicle. When some origins and destinations are more popular than others, the system will inevitably become out of balance: Vehicles will build up at some stations, and become depleted at others. We propose a robotic solution to this rebalancing problem that involves empty robotic vehicles autonomously driving between stations. Specifically, we develop a rebalancing policy that lets every station reach an equilibrium in which there are excess vehicles and no waiting customers and that minimizes the number of robotic vehicles performing rebalancing trips. To do this, we utilize a fluid model for the customers and vehicles in the system. We then show that the optimal rebalancing policy can be found as the solution to a linear program. We use this solution to develop a real-time rebalancing policy which can operate in highly variable environments. We verify policy performance in a simulated mobility-on-demand environment and in hardware experiments.

    @article{PavoneSmithEtAl2012,
      author = {Pavone, M. and Smith, S. L. and Frazzoli, E. and Rus, D.},
      title = {Robotic Load Balancing for {Mobility-on-Demand} Systems},
      journal = {{Int. Journal of Robotics Research}},
      volume = {31},
      number = {7},
      pages = {839--854},
      year = {2012},
      doi = {10.1177/0278364912444766},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Smith.ea.IJRR12.pdf}
    }
    
  22. F. Bullo, E. Frazzoli, M. Pavone, K. Savla, and S. L. Smith, “Dynamic Vehicle Routing for Robotic Systems,” Proc. of the IEEE, vol. 99, no. 9, pp. 1482–1504, 2011.

    Abstract: Recent years have witnessed great advancements in the science and technology of autonomy, robotics and networking. This paper surveys recent concepts and algorithms for dynamic vehicle routing (DVR), that is, for the automatic planning of optimal multi-vehicle routes to perform tasks that are generated over time by an exogenous process. We consider a rich variety of scenarios relevant for robotic applications. We begin by reviewing the basic DVR problem: demands for service arrive at random locations at random times and a vehicle travels to provide on-site service while minimizing the expected wait time of the demands. Next, we treat different multi-vehicle scenarios based on different models for demands (e.g., demands with different priority levels and impatient demands), vehicles (e.g., motion constraints, communication and sensing capabilities), and tasks. The performance criterion used in these scenarios is either the expected wait time of the demands or the fraction of demands serviced successfully. In each specific DVR scenario, we adopt a rigorous technical approach that relies upon methods from queueing theory, combinatorial optimization and stochastic geometry. First, we establish fundamental limits on the achievable performance, including limits on stability and quality of service. Second, we design algorithms, and provide provable guarantees on their performance with respect to the fundamental limits.

    @article{BulloFrazzoliEtAl2011,
      author = {Bullo, F. and Frazzoli, E. and Pavone, M. and Savla, K. and Smith, S. L.},
      title = {Dynamic Vehicle Routing for Robotic Systems},
      journal = {{Proc. of the IEEE}},
      volume = {99},
      number = {9},
      pages = {1482--1504},
      year = {2011},
      doi = {10.1109/JPROC.2011.2158181},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Bullo.Frazzoli.ea.IEEEProc11.pdf}
    }
    
  23. M. Pavone, A. Arsie, E. Frazzoli, and F. Bullo, “Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks,” IEEE Transactions on Automatic Control, vol. 56, no. 8, pp. 1834–1848, 2011.

    Abstract: A widely applied strategy for workload sharing is to equalize the workload assigned to each resource. In mobile multiagent systems, this principle directly leads to equitable partitioning policies whereby: 1) the environment is equitably divided into subregions of equal measure; 2) one agent is assigned to each subregion; and 3) each agent is responsible for service requests originating within its own subregion. The current lack of distributed algorithms for the computation of equitable partitions limits the applicability of equitable partitioning policies to limited-size multiagent systems operating in known, static environments. In this paper, first we design provably correct and spatially distributed algorithms that allow a team of agents to compute a convex and equitable partition of a convex environment. Second, we discuss how these algorithms can be extended so that a team of agents can compute, in a spatially distributed fashion, convex and equitable partitions with additional features, e.g., equitable and median Voronoi diagrams. Finally, we discuss two application domains for our algorithms, namely dynamic vehicle routing for mobile robotic networks and wireless ad hoc networks. Through these examples, we show how one can couple the algorithms presented in this paper with equitable partitioning policies to make these amenable to distributed implementation. More in general, we illustrate a systematic approach to devise spatially distributed control policies for a large variety of multiagent coordination problems. Our approach is related to the classic Lloyd algorithm and exploits the unique features of power diagrams.

    @article{PavoneArsieEtAl2011,
      author = {Pavone, M. and Arsie, A. and Frazzoli, E. and Bullo, F.},
      title = {Distributed Algorithms for Environment Partitioning in Mobile Robotic Networks},
      journal = {{IEEE Transactions on Automatic Control}},
      volume = {56},
      number = {8},
      pages = {1834--1848},
      year = {2011},
      doi = {10.1109/TAC.2011.2112410},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Arsie.ea.TAC11.pdf}
    }
    
  24. M. Pavone, E. Frazzoli, and F. Bullo, “Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment,” IEEE Transactions on Automatic Control, vol. 56, no. 6, pp. 1259–1274, 2011.

    Abstract: In this paper, we present adaptive and distributed algorithms for motion coordination of a group of m vehicles. The vehicles must service demands whose time of arrival, spatial location, and service requirement are stochastic; the objective is to minimize the average time demands spend in the system. The general problem is known as the m-vehicle Dynamic Traveling Repairman Problem (m-DTRP). The best previously known control algorithms rely on centralized task assignment and are not robust against changes in the environment. In this paper, we first devise new control policies for the 1-DTRP that: i) are provably optimal both in light-load conditions (i.e., when the arrival rate for the demands is small) and in heavy-load conditions (i.e., when the arrival rate for the demands is large), and ii) are adaptive, in particular, they are robust against changes in load conditions. Then, we show that specific partitioning policies, whereby the environment is partitioned among the vehicles and each vehicle follows a certain set of rules within its own region, are optimal in heavy-load conditions. Building upon the previous results, we finally design control policies for the m-DTRP that i) are adaptive and distributed, and ii) have strong performance guarantees in heavy-load conditions and stabilize the system in any load condition.

    @article{PavoneFrazzoliEtAl2011,
      author = {Pavone, M. and Frazzoli, E. and Bullo, F.},
      title = {Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment},
      journal = {{IEEE Transactions on Automatic Control}},
      volume = {56},
      number = {6},
      pages = {1259--1274},
      year = {2011},
      doi = {10.1109/TAC.2010.2092850},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Frazzoli.ea.TAC11.pdf}
    }
    
  25. J. L. Ramirez, M. Pavone, E. Frazzoli, and D. W. Miller, “Distributed Control of Spacecraft Formations via Cyclic Pursuit: Theory and Experiments,” AIAA Journal of Guidance, Control, and Dynamics, vol. 33, no. 5, pp. 1655–1669, 2010.

    Abstract: In this paper, distributed control policies for spacecraft formations that draw inspiration from the simple idea of cyclic pursuit are studied. First studied are cyclic-pursuit control laws for both single- and double-integrator models in three dimensions. In particular, control laws are developed that only require relative measurements of position and velocity with respect to the two leading neighbors in the ring topology of cyclic pursuit and that allow convergence to a variety of symmetric formations, including evenly spaced circular and elliptic formations and evenly spaced Archimedes spirals. Second, potential applications are discussed, including spacecraft formation for interferometric imaging. Finally, experimental results obtained by implementing the aforementioned control laws on the Synchronized Position Hold Engage Reorient Experimental Satellite testbed onboard the International Space Station are presented and discussed.

    @article{RamirezPavoneEtAl2010,
      author = {Ramirez, J. L. and Pavone, M. and Frazzoli, E. and Miller, D. W.},
      title = {Distributed Control of Spacecraft Formations via Cyclic Pursuit: Theory and Experiments},
      journal = {{AIAA Journal of Guidance, Control, and Dynamics}},
      volume = {33},
      number = {5},
      pages = {1655--1669},
      year = {2010},
      doi = {10.2514/1.46511},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Ramirez.Pavone.ea.JGCD10.pdf}
    }
    
  26. S. L. Smith, M. Pavone, F. Bullo, and E. Frazzoli, “Dynamic Vehicle Routing with Priority Classes of Stochastic Demands,” SIAM Journal on Control and Optimization, vol. 48, no. 5, pp. 3224–3245, 2010.

    Abstract: In this paper we introduce a dynamic vehicle routing problem in which there are multiple vehicles and multiple priority classes of service demands. Service demands of each priority class arrive in the environment randomly over time and require a random amount of on-site service that is characteristic of the class. To service a demand, one of the vehicles must travel to the demand location and remain there for the required on-site service time. The quality of service provided to each class is given by the expected delay between the arrival of a demand in the class and that demand’s service completion. The goal is to design a routing policy for the service vehicles which minimizes a convex combination of the delays for each class. First, we provide a lower bound on the achievable values of the convex combination of delays. Then, we propose a novel routing policy and analyze its performance under heavy-load conditions (i.e., when the fraction of time the service vehicles spend performing on-site service approaches one). The policy performs within a constant factor of the lower bound, where the constant depends only on the number of classes, and is independent of the number of vehicles, the arrival rates of demands, the on-site service times, and the convex combination coefficients.

    @article{SmithPavoneEtAl2010,
      author = {Smith, S. L. and Pavone, M. and Bullo, F. and Frazzoli, E.},
      title = {Dynamic Vehicle Routing with Priority Classes of Stochastic Demands},
      journal = {{SIAM Journal on Control and Optimization}},
      volume = {48},
      number = {5},
      pages = {3224--3245},
      year = {2010},
      doi = {10.1137/090749347},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Smith.Pavone.ea.SIAM10.pdf}
    }
    
  27. M. Pavone, N. Bisnik, E. Frazzoli, and V. Isler, “A Stochastic and Dynamic Vehicle Routing Problem with Time Windows and Customer Impatience,” Journal of Mobile Networks and Applications, vol. 14, no. 3, pp. 350–364, 2009.

    Abstract: In this paper, we study the problem of designing motion strategies for a team of mobile agents, required to fulfill request for on-site service in a given planar region. In our model, each service request is generated by a spatio-temporal stochastic process; once a service request has been generated, it remains active for a certain deterministic amount of time, and then expires. An active service request is fulfilled when one of the mobile agents visits the location of the request. Specific problems we investigate are the following: what is the minimum number of mobile agents needed to ensure that a certain fraction of service requests is fulfilled before expiration? What strategy should they use to ensure that this objective is attained? This problem can be viewed as the stochastic and dynamic version of the well-known vehicle routing problem with time windows. We also extend our analysis to the case in which the time service requests remain active is itself a random variable, describing customer impatience. The customers’ impatience is only known to the mobile agents via prior statistics. In this case, it is desired to minimize the fraction of service requests missed because of impatience. Finally, we show how the routing strategies presented in the paper can be executed in a distributed fashion.

    @article{PavoneBisnikEtAl2009,
      author = {Pavone, M. and Bisnik, N. and Frazzoli, E. and Isler, V.},
      title = {A Stochastic and Dynamic Vehicle Routing Problem with Time Windows and Customer Impatience},
      journal = {{Journal of Mobile Networks and Applications}},
      volume = {14},
      number = {3},
      pages = {350--364},
      year = {2009},
      doi = {10.1007/s11036-008-0101-1},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Bisnik.ea.MONE09.pdf}
    }
    
  28. M. Pavone, K. Savla, and E. Frazzoli, “Sharing the Load,” IEEE Robotics and Automation Magazine, vol. 16, no. 2, pp. 52–61, 2009.

    Abstract: In this article, we discussed the use of various spatial tessellations to determine, in the framework of partitioning policies, optimal workload share in a mobile robotic network. We also proposed efficient and spatially distributed algorithms for achieving some of these tessellations with minimum or no communication between the agents. Because of space limitations, we have not reported results of numerical experiments in this article but provided bibliographic references to publications containing such results and further details. It is interesting to note that these tessellations appear while considering different variations of the same basic problem (DTRP). It is then natural to investigate the existence of a single objective function, whose optima correspond to the various tessellations under these different variations. The game theory approach seems to be a promising one.

    @article{PavoneSavlaEtAl2009,
      author = {Pavone, M. and Savla, K. and Frazzoli, E.},
      title = {Sharing the Load},
      journal = {{IEEE Robotics and Automation Magazine}},
      volume = {16},
      number = {2},
      pages = {52--61},
      year = {2009},
      doi = {10.1109/MRA.2009.932528},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Savla.ea.RAM09.pdf}
    }
    
  29. M. Pavone and E. Frazzoli, “Decentralized Policies for Geometric Pattern Formation and Path Coverage,” ASME Journal of Dynamic Systems, Measurement, and Control, vol. 129, no. 5, pp. 633–643, 2007.

    Abstract: This paper presents a decentralized control policy for symmetric formations in multiagent systems. It is shown that n agents, each one pursuing its leading neighbor along the line of sight rotated by a common offset angle α, eventually converge to a single point, a circle or a logarithmic spiral pattern, depending on the value of α. In the final part of the paper, we present a strategy to make the agents totally anonymous, and we discuss a potential application to coverage path planning.

    @article{PavoneFrazzoli2007,
      author = {Pavone, M. and Frazzoli, E.},
      title = {Decentralized Policies for Geometric Pattern Formation and Path Coverage},
      journal = {{ASME Journal of Dynamic Systems, Measurement, and Control}},
      volume = {129},
      number = {5},
      pages = {633--643},
      year = {2007},
      doi = {10.1115/1.2767658},
      url = {../wp-content/papercite-data/pdf/Pavone.Frazzoli.JDSMC07.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  30. M. Pavone, P. Arena, and L. Patanè, “An Innovative Mechanical and Control Architecture for a Biomimetic Hexapod for Planetary Exploration,” Space Technology, vol. 26, no. 1-2, pp. 13–24, 2006.

    Abstract: This paper addresses the design of a six legged robot for planetary exploration. The robot is specifically designed for uneven terrains and is biologically inspired on different levels: mechanically as well as in control. A novel structure is developed basing on a (careful) emulation of the cockroach, whose extraordinary agility and speed are principally due to its self-stabilizing posture and specializing legged function. Structure design enhances these properties, in particular with an innovative piston-like scheme for rear legs, while avoiding an excessive and useless complexity. Locomotion control is designed following an analog electronics approach, that in space applications could hold many benefits. In particular, the locomotion control is based on a Cellular Neural Network playing the role of an artificial Central Pattern Generator. Several dynamical simulations were carried out to test the structure and the locomotion control. Simulation results led to the implementation of the first prototype: Gregor I. Experimental tests showed that Gregor I is able to walk at the travel speed of 0.1 body length per second and to successfully negotiate obstacles more than 170% of the height of its center of mass.

    @article{PavoneArenaEtAl2006b,
      author = {Pavone, M. and Arena, P. and Patan\`e, L.},
      title = {An Innovative Mechanical and Control Architecture for a Biomimetic Hexapod for Planetary Exploration},
      journal = {{Space Technology}},
      volume = {26},
      number = {1-2},
      pages = {13--24},
      year = {2006},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Arena.ea.ST06.pdf}
    }
    
  31. M. Pavone, P. Arena, L. Fortuna, M. Frasca, and L. Patanè, “Climbing Obstacle in Bio-robots via CNN and Adaptive Attitude Control,” Int. Journal of Circuit Theory and Applications, vol. 34, no. 1, pp. 109–125, 2006.

    Abstract: A control system based on the principles used by cockroaches to climb obstacles is introduced and applied to a bio-inspired hexapod robot. Cockroaches adaptively use different strategies as functions of the ground morphology and obstacle characteristics. The control system introduced in this paper consists of two parts working in parallel. Locomotion control is performed by a cellular neural network (CNN) playing the role of an artificial central pattern generator (CPG) for the robot, while a new attitude control system has been designed. In order to reproduce the adaptative capabilities of the biological model, the attitude control system is based on a motor map and is aimed at regulating the posture of the robot to allow it to overcome obstacles. In fact, high obstacles require the locomotion gait to be reorganized by changing the posture of the robot to be more effective during the overcoming of the obstacle. Both proprioceptive and exteroceptive information are needed to solve this problem, they constitute the input of the adaptive attitude control. Simulation results illustrating the suitability of the control system are also shown.

    @article{PavoneArenaEtAl2006,
      author = {Pavone, M. and Arena, P. and Fortuna, L. and Frasca, M. and Patan\`e, L.},
      title = {Climbing Obstacle in Bio-robots via {CNN} and Adaptive Attitude Control},
      journal = {{Int. Journal of Circuit Theory and Applications}},
      volume = {34},
      number = {1},
      pages = {109--125},
      year = {2006},
      doi = {10.1109/ISCAS.2005.1465810},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Arena.ea.IJCTA06.pdf}
    }
    

Conference Articles

  1. R. Bonalli, A. Cauligi, A. Bylard, and M. Pavone, “GuSTO: Guaranteed Sequential Trajectory Optimization via Sequential Convex Programming,” in Proc. IEEE Conf. on Robotics and Automation, Montreal, Canada, 2019. (Submitted)

    Abstract: Sequential Convex Programming (SCP) has recently seen a surge of interest as a tool for trajectory optimization. Yet, most available methods lack rigorous performance guarantees and are often tailored to specific optimal control setups. In this paper, we present GuSTO (Guaranteed Sequential Trajectory Optimization), an algorithmic framework to solve trajectory optimization problems for control-affine systems with drift. GuSTO generalizes earlier SCP-based methods for trajectory optimization (by addressing, for example, goal region constraints and problems with either fixed or free final time), and enjoys theoretical convergence guarantees in terms of convergence to, at least, a stationary point. The theoretical analysis is further leveraged to devise an accelerated implementation of GuSTO, which originally infuses ideas from indirect optimal control into an SCP context. Numerical experiments on a variety of trajectory optimization setups show that GuSTO generally outperforms current state-of-the-art approaches in terms of success rates, solution quality, and computation times.

    @inproceedings{BonalliCauligiEtAl2019,
      author = {Bonalli, R. and Cauligi, A. and Bylard, A. and Pavone, M.},
      title = {{GuSTO:} Guaranteed Sequential Trajectory Optimization via Sequential Convex Programming},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2019},
      note = {Submitted},
      address = {Montreal, Canada},
      month = may,
      url = {../wp-content/papercite-data/pdf/Bonalli.Cauligi.Bylard.Pavone.ICRA19.pdf},
      keywords = {sub},
      owner = {bylard},
      timestamp = {2018-10-04}
    }
    
  2. J. Lorenzetti, B. Landry, S. Singh, and M. Pavone, “Reduced Order Model Predictive Control For Setpoint Tracking,” in European Control Conference, Naples, Italy, 2019. (Submitted)

    Abstract: Despite the success of model predictive control (MPC), its application to high-dimensional systems, such as flexible structures and coupled fluid/rigid-body systems, remains a largely open challenge due to excessive computational complexity. A promising solution approach is to leverage reduced order models for designing the model predictive controller. In this paper we present a reduced order MPC scheme that enables setpoint tracking while robustly guaranteeing constraint satisfaction for linear, discrete, time-invariant systems. Setpoint tracking is enabled by designing the MPC cost function to account for the steady-state error between the full and reduced order models. Robust constraint satisfaction is accomplished by solving (offline) a set of linear programs to provide bounds on the errors due to bounded disturbances, state estimation, and model approximation. The approach is validated on a synthetic system as well as a high-dimensional linear model of a flexible rod, obtained using finite element methods.

    @inproceedings{LorenzettiLandryEtAl2019,
      author = {Lorenzetti, J. and Landry, B. and Singh, S. and Pavone, M.},
      title = {Reduced Order Model Predictive Control For Setpoint Tracking},
      booktitle = {{European Control Conference}},
      year = {2019},
      note = {Submitted},
      address = {Naples, Italy},
      month = jun,
      url = {https://arxiv.org/pdf/1811.06590.pdf},
      keywords = {sub},
      owner = {jlorenze},
      timestamp = {2018-11-15}
    }
    
  3. M. Salazar, M. Tsao, I. Aguiar, M. Schiffer, and M. Pavone, “A Congestion-aware Routing Scheme for Autonomous Mobility-on-Demand Systems,” in European Control Conference, Naples, Italy, 2019. (Submitted)

    Abstract: We study route-planning for Autonomous Mobility-on-Demand (AMoD) systems that accounts for the impact of road traffic on travel time. Specifically, we develop a congestion-aware routing scheme (CARS) that captures road-utilization-dependent travel times at a mesoscopic level via a piecewise affine approximation of the Bureau of Public Roads (BPR) model. This approximation largely retains the key features of the BPR model, while allowing the design of a real-time, convex quadratic optimization algorithm to determine congestion-aware routes for an AMoD fleet. Through a real-world case study of Manhattan, we compare CARS to existing routing approaches, namely a congestion-unaware and a threshold congestion model. Numerical results show that CARS significantly outperforms the other two approaches, with improvements in terms of travel time and global cost in the order of 20%.

    @inproceedings{SalazarTsaoEtAl2019,
      author = {Salazar, M. and Tsao, M. and Aguiar, I. and Schiffer, M. and Pavone, M.},
      title = {A Congestion-aware Routing Scheme for Autonomous Mobility-on-Demand Systems},
      booktitle = {{European Control Conference}},
      year = {2019},
      note = {Submitted},
      address = {Naples, Italy},
      month = nov,
      url = {../wp-content/papercite-data/pdf/Salazar.Tsao.ea.ECC19.pdf},
      keywords = {sub},
      owner = {samauro},
      timestamp = {2018-11-17}
    }
    
  4. K. Leung, N. Arechiga, and M. Pavone, “Backpropagation for Signal Temporal Logic,” in Hybrid Systems: Computation and Control, Montreal, Canada, 2019. (Submitted)

    Abstract: Signal Temporal Logic (STL) is an expressive language used to describe logical and temporal properties of signals, both continuous and discrete. Inferring STL formulas from behavior traces can provide powerful insights into complex systems. These insights can help system designers better understand and improve the systems they develop (e.g., long-term behaviors of time series data), yet this is a very challenging and often intractable problem. This work presents a method for evaluating STL formulas using computation graphs, hence bridging a connection between STL and many modern machine learning frameworks that depend on computation graphs, such as deep learning. We show that this approach is particularly effective for solving parameteric STL (pSTL) problems, the problem of parameter fitting for a given signal. We provide a relaxation technique that makes this method more tractable when solving general pSTL formulas. By using computation graphs, we can leverage the benefits and the computational prowess of modern day machine learning tools. Motivated by the problem of learning explanatory factors and safety assurance for complex cyber-physical systems, we demonstrate our proposed method on an autonomous driving case study.

    @inproceedings{LeungArechigaEtAl2019,
      author = {Leung, K. and Arechiga, N. and Pavone, M.},
      title = {Backpropagation for Signal Temporal Logic},
      booktitle = {{Hybrid Systems: Computation and Control}},
      year = {2019},
      note = {Submitted},
      address = {Montreal, Canada},
      month = apr,
      keywords = {sub},
      owner = {karenl7},
      timestamp = {2018-10-24}
    }
    
  5. B. Ivanovic and M. Pavone, “Modeling Multimodal Dynamic Spatiotemporal Graphs,” in Proc. IEEE Conf. on Robotics and Automation, Montreal, Canada, 2019. (Submitted)

    Abstract: Spatiotemporal graphs (STGs) are a powerful tool for modeling multi-agent interaction scenarios, used commonly in human trajectory prediction and proactive planning and decision making for safe human-robot interaction. However, many current STG-backed methods rely on a static graph assumption, i.e. that the underlying graphical structure maintains the same nodes and edges throughout the scenario. This assumption is frequently broken in real-world applications, especially in highly-dynamic problems such as human trajectory prediction in crowds. To remove the reliance on this assumption, we present a methodology for modeling and predicting agent behavior in both highly dynamic and multimodal scenarios (i.e. where the scene’s graphical structure is time-varying and there are many possible highly-distinct futures for each agent). Our approach to model dynamic STGs augments prior multimodal, multi-agent modeling methods with a gating function on edge models that smoothly adds and removes edge influence from a node. We demonstrate the performance of our approach on the ETH multi-human trajectory dataset and on NBA basketball player trajectories. Both are highly-dynamic, multimodal, and multi-agent interaction scenarios which serve as proxies for many robotic applications.

    @inproceedings{IvanovicPavone2019,
      author = {Ivanovic, B. and Pavone, M.},
      title = {Modeling Multimodal Dynamic Spatiotemporal Graphs},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2019},
      note = {Submitted},
      address = {Montreal, Canada},
      month = may,
      url = {https://arxiv.org/pdf/1810.05993.pdf},
      keywords = {sub},
      owner = {borisi},
      timestamp = {2018-09-16}
    }
    
  6. B. Ivanovic, J. Harrison, A. Sharma, M. Chen, and M. Pavone, “BaRC: Backward Reachability Curriculum for Robotic Reinforcement Learning,” in Proc. IEEE Conf. on Robotics and Automation, Montreal, Canada, 2019. (Submitted)

    Abstract: Model-free Reinforcement Learning (RL) offers an attractive approach to learn control policies for high-dimensional systems, but its relatively poor sample complexity often forces training in simulated environments. Even in simulation, goal-directed tasks whose natural reward function is sparse remain intractable for state-of-the-art model-free algorithms for continuous control. The bottleneck in these tasks is the prohibitive amount of exploration required to obtain a learning signal from the initial state of the system. In this work, we leverage physical priors in the form of an approximate system dynamics model to design a curriculum scheme for a model-free policy optimization algorithm. Our Backward Reachability Curriculum (BaRC) begins policy training from states that require a small number of actions to accomplish the task, and expands the initial state distribution backwards in a dynamically-consistent manner once the policy optimization algorithm demonstrates sufficient performance. BaRC is general, in that it can accelerate training of any model-free RL algorithm on a broad class of goal-directed continuous control MDPs. Its curriculum strategy is physically intuitive, easy-to-tune, and allows incorporating physical priors to accelerate training without hindering the performance, flexibility, and applicability of the model-free RL algorithm. We evaluate our approach on two representative dynamic robotic learning problems and find substantial performance improvement relative to previous curriculum generation techniques and naïve exploration strategies

    @inproceedings{IvanovicHarrisonEtAl2019,
      author = {Ivanovic, B. and Harrison, J. and Sharma, A. and Chen, M. and Pavone, M.},
      title = {{BaRC:} Backward Reachability Curriculum for Robotic Reinforcement Learning},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2019},
      note = {Submitted},
      address = {Montreal, Canada},
      month = may,
      url = {https://arxiv.org/pdf/1806.06161.pdf},
      keywords = {sub},
      owner = {apoorva},
      timestamp = {2018-09-05}
    }
    
  7. B. Ichter and M. Pavone, “Robot Motion Planning in Learned Latent Spaces,” in IEEE Robotics and Automation Letters, Merida, Mexico, 2019. (Submitted)

    Abstract: This paper presents Latent Sampling-based Motion Planning (L-SBMP), a methodology towards computing motion plans for complex robotic systems by learning a plannable latent representation. Recent works in control of robotic systems have effectively leveraged local, low-dimensional embeddings of high-dimensional dynamics. In this paper we combine these recent advances with techniques from sampling-based motion planning (SBMP) in order to design a methodology capable of planning for high-dimensional robotic systems beyond the reach of traditional approaches (e.g., humanoids, or even systems where planning occurs in the visual space). Specifically, the learned latent space is constructed through an autoencoding network, a dynamics network, and a collision checking network, which mirror the three main algorithmic primitives of SBMP, namely state sampling, local steering, and collision checking. Notably, these networks can be trained through only raw data of the system’s states and actions along with a supervising collision checker. Building upon these networks, an RRT-based algorithm is used to plan motions directly in the latent space - we refer to this exploration algorithm as Learned Latent RRT (L2RRT). This algorithm globally explores the latent space and is capable of generalizing to new environments. The overall methodology is demonstrated on two planning problems, namely a visual planning problem, whereby planning happens in the visual (pixel) space, and a humanoid robot planning problem.

    @inproceedings{IchterPavone2019,
      author = {Ichter, B. and Pavone, M.},
      title = {Robot Motion Planning in Learned Latent Spaces},
      booktitle = {{IEEE Robotics and Automation Letters}},
      year = {2019},
      note = {Submitted},
      address = {Merida, Mexico},
      month = oct,
      url = {https://arxiv.org/abs/1807.10366},
      keywords = {sub},
      owner = {ichter},
      timestamp = {2018-11-06}
    }
    
  8. J. Harrison, A. Sharma, R. Calandra, and M. Pavone, “Control Adaptation via Meta-Learning Dynamics,” in Proc. IEEE Conf. on Robotics and Automation, Montreal, Canada, 2019. (Submitted)

    Abstract: Model-based control relies on having an accurate dynamics model. In situations where the dynamics of the robot is not static (e.g., after a delivery quadcopter pick or drop a package), it is paramount to accurately estimate how the dynamics is influenced – and thus account for these changes at the control level. One way of doing so is to condition the dynamics model on some latent variable which represents the context. In this paper, we present CAMeLiD, a data-driven approach to learn controllers that can quickly adapt to previously unseen dynamics. This is done through a high-capacity neural network trained in a meta-learning manner to infer the context of the dynamics, and a subsequent model-based control framework based on iLQG. We demonstrate CAMeLiD on a quadrotor delivery experiment, and show it results in substantial performance improvement over baselines.

    @inproceedings{HarrisonSharmaEtAl2019,
      author = {Harrison, J. and Sharma, A. and Calandra, R. and Pavone, M.},
      title = {Control Adaptation via Meta-Learning Dynamics},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2019},
      note = {Submitted},
      address = {Montreal, Canada},
      month = may,
      keywords = {sub},
      owner = {jh2},
      timestamp = {2018-09-16}
    }
    
  9. M. Tsao, D. Milojevic, C. Ruch, M. Salazar, E. Frazzoli, and M. Pavone, “Model Predictive Control of Ride-sharing Autonomous Mobility on Demand Systems,” in Proc. IEEE Conf. on Robotics and Automation, Montreal, Canada, 2019. (Submitted)

    Abstract: This paper presents a model predictive control (MPC) approach to optimize routes for Ride-sharing Autonomous Mobility-on-Demand (RAMoD) systems, whereby self-driving vehicles provide coordinated on-demand mobility, possibly allowing multiple customers to share a ride. Specifically, we first devise a time-expanded network flow model for RAMoD. Second, leveraging this model, we design a real-time MPC algorithm to optimize the routes of both empty and customer-carrying vehicles, with the goal of optimizing social welfare, namely, a weighted combination of customers’ travel time and vehicles’ mileage. Finally, we present a real-world case study for the city of San Francisco, CA, by using the microscopic traffic simulator MATSim. The simulation results show that a RAMoD system can significantly improve social welfare with respect to a single-occupancy AMoD system, and that the predictive structure of the proposed MPC controller allows it to outperform existing reactive ride-sharing coordination algorithms for RAMoD.

    @inproceedings{TsaoMilojevicEtAl2019,
      author = {Tsao, M. and Milojevic, D. and Ruch, C. and Salazar, M. and Frazzoli, E. and Pavone, M.},
      title = {Model Predictive Control of Ride-sharing Autonomous Mobility on Demand Systems},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2019},
      note = {Submitted},
      address = {Montreal, Canada},
      month = may,
      url = {../wp-content/papercite-data/pdf/Tsao.ea.ICRA19.pdf},
      keywords = {sub},
      owner = {samauro},
      timestamp = {2018-09-16}
    }
    
  10. M. Salazar, M. Tsao, I. Aguiar, M. Schiffer, and M. Pavone, “CARA: A Congestion-Aware Routing Algorithm for Autonomous Mobility-on-Demand Systems,” in Annual Meeting of the Transportation Research Board, Washington, D.C., 2019. (Submitted)

    Abstract: We present a congestion-aware routing policy for Autonomous Mobility-on-Demand (AMoD) systems that accounts for the impact of road traffic on travel time. Specifically, we develop a congestion-aware routing algorithm (CARA) that captures road utilization dependent travel times via a piecewise affine approximation of the Bureau of Public Roads (BPR) model. Such an approximation largely retains the key features of the BPR model, while enabling the design of a real-time, convex quadratic optimization algorithm to compute congestion-aware routes for an AMoD fleet. Through a real-world case study of Manhattan, we compare CARA to existing routing approaches, the first one congestion-unaware and the second one based on a threshold congestion model. Numerical results show that CARA significantly outperforms the state of the art, with improvements in terms of travel time and global cost in the order of 20%, and computation times compatible with a real-time implementation.

    @inproceedings{Salazar2019,
      author = {Salazar, M. and Tsao, M. and Aguiar, I. and Schiffer, M. and Pavone, M.},
      title = {{CARA:} A Congestion-Aware Routing Algorithm for Autonomous Mobility-on-Demand Systems},
      booktitle = {{Annual Meeting of the Transportation Research Board}},
      year = {2019},
      note = {Submitted},
      address = {Washington, D.C.},
      month = jan,
      url = {../wp-content/papercite-data/pdf/Salazar.Tsao.ea.TRB19.pdf},
      keywords = {sub},
      owner = {mwtsao},
      timestamp = {2018-08-01}
    }
    
  11. S. Chiodini, R. G. Reid, B. Hockman, I. A. D. Nesnas, S. Debei, and M. Pavone, “Robust Visual Localization for Hopping Rovers on Small Bodies,” in Proc. IEEE Conf. on Robotics and Automation, Brisbane, Australia, 2018.

    Abstract: We present a collaborative visual localization method for rovers designed to hop and tumble over the surface of small Solar System bodies, such as comets and asteroids. In a two-phase approach, an orbiting primary spacecraft first maps the surface of a body by capturing images from various poses and illumination angles; these images are processed to create a prior map of 3D landmarks. In the second phase, a hopping rover is deployed to the surface where it uses the prior map and a camera to perform on-board visual simultaneous localization and mapping (SLAM). Small bodies present new challenges to existing visual SLAM algorithms. Rotation periods as short as 1-12 hours, in the absence of atmospheric scattering, create high-contrast shadows that move over the surface. The constantly changing illumination angles cause landmark outliers and increase pose uncertainty. Furthermore, in this collaborative visual SLAM problem, the scene scale between spacecraft and hopping rover varies by several orders of magnitude (kilometers to centimeters). In this work, we describe how to augment ORB-SLAM2 - a state of the art visual SLAM implementation - so that it combines prior images with multiple illumination angles to handle large illumination variations. We also demonstrate how a wide field of view (FOV) camera (e.g. on a hopping rover) can relocalize to prior maps captured by a narrow FOV camera (e.g. a spacecraft navcam) to handle large scale variations. To reduce pose and scale errors accumulated while exploring the surface, we show how the rover can perform large hops to capture views of the surface that it can match to the prior map. After relocalizing, the rover’s on-board estimates are updated with a pose graph optimization and bundle adjustment. We evaluate the proposed method with sequences of images captured around a mock asteroid; illumination angles are varied while narrow and wide FOV cameras are steered along trajectories representative of orbital and hopping motions. Trajectory estimates are compared and found to be consistent with ground truth data. Evaluations suggest this method is robust to large illumination variations, scene scale changes and off-nadir camera pointing angles.

    @inproceedings{ChiodiniReidEtAl2018,
      author = {Chiodini, S. and Reid, R. G. and Hockman, B. and Nesnas, I. A. D. and Debei, S. and Pavone, M.},
      title = {Robust Visual Localization for Hopping Rovers on Small Bodies},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2018},
      address = {Brisbane, Australia},
      month = may,
      url = {../wp-content/papercite-data/pdf/Chiodini.Reid.Hockman.ea.ICRA18.pdf},
      owner = {bhockman},
      timestamp = {2018-01-16}
    }
    
  12. K. Leung, E. Schmerling, M. Chen, J. Talbot, J. C. Gerdes, and M. Pavone, “On Infusing Reachability-Based Safety Assurance within Probabilistic Planning Frameworks for Human-Robot Vehicle Interactions,” in Int. Symp. on Experimental Robotics, 2018.

    Abstract:

    @inproceedings{LeungSchmerlingEtAl2018,
      author = {Leung, K. and Schmerling, E. and Chen, M. and Talbot, J. and Gerdes, J. C. and Pavone, M.},
      title = {On Infusing Reachability-Based Safety Assurance within Probabilistic Planning Frameworks for Human-Robot Vehicle Interactions},
      booktitle = {{Int. Symp. on Experimental Robotics}},
      year = {2018},
      url = {../wp-content/papercite-data/pdf/Leung.Schmerling.Chen.ea.ISER18.pdf},
      owner = {mochen72},
      timestamp = {2018-10-13}
    }
    
  13. S. Singh, M. Chen, S. L. Herbert, C. J. Tomlin, and M. Pavone, “Robust Tracking with Model Mismatch for Fast and Safe Planning: an SOS Optimization Approach,” in Workshop on Algorithmic Foundations of Robotics, Merida, Mexico, 2018. (In Press)

    Abstract: In the pursuit of real-time motion planning, a commonly adopted practice is to compute a trajectory by running a planning algorithm on a simplified, low-dimensional dynamical model, and then employ a feedback tracking controller that tracks such a trajectory by accounting for the full, high-dimensional system dynamics. While this strategy of planning with model mismatch generally yields fast computation times, there are no guarantees of dynamic feasibility, which hampers application to safety-critical systems. Building upon recent work that addressed this problem through the lens of Hamilton-Jacobi (HJ) reachability, we devise an algorithmic framework whereby one computes, offline, for a pair of "planner" (i.e., low-dimensional) and "tracking" (i.e., high-dimensional) models, a feedback tracking controller and associated tracking bound. This bound is then used as a safety margin when generating motion plans via the low-dimensional model. Specifically, we harness the computational tool of sum-of-squares (SOS) programming to design a bilinear optimization algorithm for the computation of the feedback tracking controller and associated tracking bound. The algorithm is demonstrated via numerical experiments, with an emphasis on investigating the trade-off between the increased computational scalability afforded by SOS and its intrinsic conservativeness. Collectively, our results enable scaling the appealing strategy of planning with model mismatch to systems that are beyond the reach of HJ analysis, while maintaining safety guarantees.

    @inproceedings{SinghChenEtAl2018,
      author = {Singh, S. and Chen, M. and Herbert, S. L. and Tomlin, C. J. and Pavone, M.},
      title = {Robust Tracking with Model Mismatch for Fast and Safe Planning: an {SOS} Optimization Approach},
      booktitle = {{Workshop on Algorithmic Foundations of Robotics}},
      year = {2018},
      note = {In Press},
      address = {Merida, Mexico},
      month = oct,
      url = {https://arxiv.org/abs/1808.00649},
      keywords = {press},
      owner = {ssingh19},
      timestamp = {2018-09-21}
    }
    
  14. S. Singh, V. Sindhwani, J.-J. E. Slotine, and M. Pavone, “Learning Stabilizable Dynamical Systems via Control Contraction Metrics,” in Workshop on Algorithmic Foundations of Robotics, Merida, Mexico, 2018. (In Press)

    Abstract: We propose a novel framework for learning stabilizable nonlinear dynamical systems for continuous control tasks in robotics. The key idea is to develop a new control-theoretic regularizer for dynamics fitting rooted in the notion of stabilizability, which guarantees that the learnt system can be accompanied by a robust controller capable of stabilizing any trajectory that the system can generate. By leveraging tools from contraction theory, statistical learning, and convex optimization, we provide a general and tractable algorithm to learn stabilizable dynamics, which can be applied to complex underactuated systems. We validate the proposed algorithm on a simulated planar quadrotor system and observe that the control-theoretic regularized dynamics model is able to consistently generate and accurately track reference trajectories whereas the model learnt using standard regression techniques, e.g., ridge-regression (RR) does extremely poorly on both tasks. Furthermore, in aggressive flight regimes with high velocity and bank angle, the tracking controller fails to stabilize the trajectory generated by the ridge-regularized model whereas no instabilities were observed using the control-theoretic learned model, even with a small number of demonstration examples. The results presented illustrate the need to infuse standard model-based reinforcement learning algorithms with concepts drawn from nonlinear control theory for improved reliability.

    @inproceedings{SinghSindhwaniEtAl2018,
      author = {Singh, S. and Sindhwani, V. and Slotine, J.-J. E. and Pavone, M.},
      title = {Learning Stabilizable Dynamical Systems via Control Contraction Metrics},
      booktitle = {{Workshop on Algorithmic Foundations of Robotics}},
      year = {2018},
      note = {In Press},
      address = {Merida, Mexico},
      month = oct,
      url = {https://arxiv.org/abs/1808.00113},
      keywords = {press},
      owner = {ssingh19},
      timestamp = {2018-09-21}
    }
    
  15. J. Harrison, A. Sharma, and M. Pavone, “Meta-Learning Priors for Efficient Online Bayesian Regression,” in Workshop on Algorithmic Foundations of Robotics, Merida, Mexico, 2018. (In Press)

    Abstract: Gaussian Process (GP) regression has seen widespread use in robotics due to its generality, simplicity of use, and the utility of Bayesian predictions. In particular, the predominant implementation of GP regression is kernel-based, as it enables fitting of arbitrary nonlinear functions by leveraging kernel functions as infinite-dimensional features. While incorporating prior information has the potential to drastically improve data efficiency of kernel-based GP regression, expressing complex priors through the choice of kernel function and associated hyperparameters is often challenging and unintuitive. Furthermore, the computational complexity of kernel-based GP regression scales poorly with the number of samples, limiting its application in regimes where a large amount of data is available. In this work, we propose ALPaCA, an algorithm for efficient Bayesian regression which addresses these issues. ALPaCA uses a dataset of sample functions to learn a domain-specific, finite-dimensional feature encoding, as well as a prior over the associated weights, such that Bayesian linear regression in this feature space yields accurate online predictions of the posterior density. These features are neural networks, which are trained via a meta-learning approach. ALPaCA extracts all prior information from the dataset, rather than relying on the choice of arbitrary, restrictive kernel hyperparameters. Furthermore, it substantially reduces sample complexity, and allows scaling to large systems. We investigate the performance of ALPaCA on two simple regression problems, two simulated robotic systems, and on a lane-change driving task performed by humans. We find our approach outperforms kernel-based GP regression, as well as state of the art meta-learning approaches, thereby providing a promising plug-in tool for many regression tasks in robotics where scalability and data-efficiency are important.

    @inproceedings{HarrisonSharmaEtAl2018,
      author = {Harrison, J. and Sharma, A. and Pavone, M.},
      title = {Meta-Learning Priors for Efficient Online Bayesian Regression},
      booktitle = {{Workshop on Algorithmic Foundations of Robotics}},
      year = {2018},
      note = {In press},
      address = {Merida, Mexico},
      month = oct,
      url = {https://arxiv.org/pdf/1807.08912.pdf},
      keywords = {press},
      owner = {apoorva},
      timestamp = {2018-10-07}
    }
    
  16. B. Hockman and M. Pavone, “Traversability of Hopping Rovers on Small Solar System Bodies,” in Int. Symp. on Artificial Intelligence, Robotics and Automation in Space, Madrid, Spain, 2018.

    Abstract: In this paper we explore notions of traversability for hopping rovers on small solar system bodies, such as asteroids and comets, with a focus on developing actionable tools for mission planning. We start with a discussion of hopping dynamics and the inherent differences between notions of “traversability” for hopping and traditional wheeled rovers. We then discuss various map-based tools for understanding the surface gravity environment and propose an algorithm that partitions the surface into locally traversable regions. Finally, we leverage dynamic simulations to estimate k-hop backwards reachable sets—that is the surface regions from which a particular point can be reached within k hops. A case study of comet 67P demonstrates that even extremely irregular bodies may be largely traversable with an appropriate hopper design.

    @inproceedings{Hockman2018,
      author = {Hockman, B. and Pavone, M.},
      title = {Traversability of Hopping Rovers on Small Solar System Bodies},
      booktitle = {{Int. Symp. on Artificial Intelligence, Robotics and Automation in Space}},
      year = {2018},
      address = {Madrid, Spain},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Hockman.Pavone.ISAIRAS18.pdf},
      owner = {bhockman},
      timestamp = {2018-05-25}
    }
    
  17. M. Tsao, R. Iglesias, and M. Pavone, “Stochastic Model Predictive Control for Autonomous Mobility on Demand,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, Maui, Hawaii, 2018. (In Press)

    Abstract: This paper presents a stochastic, model predictive control (MPC) algorithm that leverages short-term proba- bilistic forecasts for dispatching and rebalancing Autonomous Mobility-on-Demand systems (AMoD), i.e. fleets of self-driving vehicles. We first present the core stochastic optimization problem in terms of a time-expanded network flow model. Then, to ameliorate its tractability, we present two key relaxations. First, we replace the original stochastic problem with a Sample Average Approximation, and provide its performance guaran- tees. Second, we divide the controller into two submodules. The first submodule assigns vehicles to existing customers and the second redistributes vacant vehicles throughout the city. This enables the problem to be solved as two totally unimodular linear programs, allowing the controller to scale to large problem sizes. Finally, we test the proposed algorithm in two scenarios based on real data and show that it outperforms prior state-of-the-art algorithms. In particular, in a simulation using customer data from the ridesharing company DiDi Chuxing, the algorithm presented here exhibits a 62.3 percent reduction in customer waiting time compared to state of the art non- stochastic algorithms.

    @inproceedings{TsaoIglesiasEtAl2018,
      author = {Tsao, M. and Iglesias, R. and Pavone, M.},
      title = {Stochastic Model Predictive Control for Autonomous Mobility on Demand},
      booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}},
      year = {2018},
      note = {In Press. {Extended Version, Available} at \url{https://arxiv.org/pdf/1804.11074}},
      address = {Maui, Hawaii},
      month = nov,
      url = {https://arxiv.org/pdf/1804.11074.pdf},
      keywords = {press},
      owner = {rdit},
      timestamp = {2018-07-12}
    }
    
  18. L. Janson, T. Hu, and M. Pavone, “Safe Motion Planning in Unknown Environments: Optimality Benchmarks and Tractable Policies,” in Robotics: Science and Systems, Pittsburgh, Pennsylvania, 2018. (In Press)

    Abstract: This paper addresses the problem of planning a safe (i.e., collisionfree) trajectory from an initial state to a goal region when the obstacle space is apriori unknown and is incrementally revealed online, e.g., through lineofsight perception. Despite its ubiquitous nature, this formulation of motion planning has received relatively little theoretical investigation, as opposed to the setup where the environment is assumed known. A fundamental challenge is that, unlike motion planning with known obstacles, it is not even clear what an optimal policy to strive for is. Our contribution is threefold. First, we present a notion of optimality for safe planning in unknown environments in the spirit of comparative (as opposed to competitive) analysis, with the goal of obtaining a benchmark that is, at least conceptually, attainable. Second, by leveraging this theoretical benchmark, we derive a pseudooptimal class of policies that can seamlessly incorporate any amount of prior or learned information while still guaranteeing the robot never collides. Finally, we demonstrate the practicality of our algorithmic approach in numerical experiments using a range of environment types and dynamics, including a comparison with a state of the art method. A key aspect of our framework is that it automatically and implicitly weighs exploration versus exploitation in a way that is optimal with respect to the information available.

    @inproceedings{JansonHuEtAl2018,
      author = {Janson, L. and Hu, T. and Pavone, M.},
      title = {Safe Motion Planning in Unknown Environments: Optimality Benchmarks and Tractable Policies},
      booktitle = {{Robotics: Science and Systems}},
      year = {2018},
      note = {In Press},
      address = {Pittsburgh, Pennsylvania},
      month = jun,
      url = {https://arxiv.org/pdf/1804.05804.pdf},
      keywords = {press},
      owner = {bylard},
      timestamp = {20180412}
    }
    
  19. F. Rossi, R. Iglesias, M. Alizadeh, and M. Pavone, “On the Interaction Between Autonomous Mobility-on-Demand Systems and the Power Network: Models and Coordination Algorithms,” in Robotics: Science and Systems, Pittsburgh, Pennsylvania, 2018.

    Abstract: We study the interaction between a fleet of electric, self-driving vehicles servicing on-demand transportation requests (referred to as Autonomous Mobility-on-Demand, or AMoD, system) and the electric power network. We propose a joint linear model that captures the coupling between the two systems stemming from the vehicles’ charging requirements. The model subsumes existing network flow models for AMoD systems and linear models for the power network, and it captures time-varying customer demand and power generation costs, road congestion, and power transmission and distribution constraints. We then leverage the linear model to jointly optimize the operation of both systems. We propose an algorithmic procedure to losslessly reduce the problem size by bundling customer requests, allowing it to be efficiently solved by state-of-the-art linear programming solvers. Finally, we study the implementation of a hypothetical electric-powered AMoD system in Dallas-Fort Worth, and its impact on the Texas power network. We show that coordination between the AMoD system and the power network can reduce the overall energy expenditure compared to the case where no cars are present (despite the increased demand for electricity) and yield savings of $78M per year compared to an uncoordinated scenario. Collectively, the results of this paper provide a first-of-a-kind characterization of the interaction between electric-powered AMoD systems and the electric power network, and shed additional light on the economic and societal value of AMoD.

    @inproceedings{RossiIglesiasEtAl2018,
      author = {Rossi, F. and Iglesias, R. and Alizadeh, M. and Pavone, M.},
      title = {On the Interaction Between {Autonomous Mobility-on-Demand} Systems and the Power Network: Models and Coordination Algorithms},
      booktitle = {{Robotics: Science and Systems}},
      year = {2018},
      note = {{Extended version available at }\url{https://arxiv.org/abs/1709.04906}},
      address = {Pittsburgh, Pennsylvania},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Rossi.Iglesias.Alizadeh.Pavone.RSS18.pdf},
      owner = {frossi2},
      timestamp = {2018-06-30}
    }
    
  20. M. Salazar, F. Rossi, M. Schiffer, C. H. Onder, and M. Pavone, “On the Interaction between Autonomous Mobility-on-Demand and the Public Transportation Systems,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, Maui, Hawaii, 2018. (In Press)

    Abstract: In this paper we study models and coordination policies for intermodal Autonomous Mobility-on-Demand (AMoD), wherein a fleet of self-driving vehicles provides on-demand mobility jointly with public transit. Specifically, we first present a network flow model for intermodal AMoD, where we capture the coupling between AMoD and public transit and the goal is to maximize social welfare. Second, leveraging such a model, we design a pricing and tolling scheme that allows to achieve the social optimum under the assumption of a perfect market with selfish agents. Finally, we present a real-world case study for New York City. Our results show that the coordination between AMoD fleets and public transit can yield significant benefits compared to an AMoD system operating in isolation.

    @inproceedings{SalazarRossiEtAl2018,
      author = {Salazar, M. and Rossi, F. and Schiffer, M. and Onder, C. H. and Pavone, M.},
      title = {On the Interaction between Autonomous Mobility-on-Demand and the Public Transportation Systems},
      booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}},
      year = {2018},
      note = {In Press. {Extended Version, Available} at \url{https://arxiv.org/abs/1804.11278}},
      address = {Maui, Hawaii},
      month = {#nov#},
      url = {https://arxiv.org/pdf/1804.11278.pdf},
      keywords = {press},
      owner = {frossi2},
      timestamp = {2018-07-12}
    }
    
  21. J. Lorenzetti, M. Chen, B. Landry, and M. Pavone, “Reach-Avoid Games Via Mixed-Integer Second-Order Cone Programming,” in Proc. IEEE Conf. on Decision and Control, Miami Beach, Florida, 2018. (In Press)

    Abstract: Reach-avoid games are excellent proxies for studying many problems in robotics and related fields, with applications including multi-robot systems, human-robot interactions, and safety-critical systems. Solving reach-avoid games is however difficult due to the conflicting and asymmetric goals of agents, and trade-offs between optimality, computational complexity, and solution generality are commonly required. This paper seeks to find attacker strategies in reach-avoid games that reduce computational complexity while retaining solution quality by using a receding horizon strategy. To solve for the open-loop strategy fast enough to enable an receding horizon approach, the problem is formulated as a mixed-integer second-order cone program. This formulation leverages the use of sums-of-squares optimization to provide guarantees that the strategy is robust to all possible defender policies. The method is demonstrated through numerical and hardware experiments.

    @inproceedings{LorenzettiChenEtAl2018,
      author = {Lorenzetti, J. and Chen, M. and Landry, B. and Pavone, M.},
      title = {Reach-Avoid Games Via Mixed-Integer Second-Order Cone Programming},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2018},
      note = {In Press},
      address = {Miami Beach, Florida},
      month = dec,
      url = {../wp-content/papercite-data/pdf/Lorenzetti.Chen.Landry.Pavone.CDC18.pdf},
      keywords = {press},
      owner = {mochen72},
      timestamp = {2018-11-15}
    }
    
  22. B. Landry, M. Chen, S. Hemley, and M. Pavone, “Reach-Avoid Problems via Sum-of-Squares Optimization and Dynamic Programming,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Madrid, Spain, 2018.

    Abstract: Reach-avoid problems involve driving a system to a set of desirable configurations while keeping it away from undesirable ones. Providing mathematical guarantees for such scenarios is challenging but have numerous potential practical applications. Due to the challenges, analysis of reach-avoid problems involves making trade-offs between generality of system dynamics, generality of problem setups, optimality of solutions, and computational complexity. In this paper, we combine sum-of-squares optimization and dynamic programming to address the reach-avoid problem, and provide a conservative solution that maintains reaching and avoidance guarantees. Our method is applicable to polynomial system dynamics and to general problem setups, and is more computationally scalable than previous related methods. Through a numerical example involving two single integrators, we validate our proposed theory and compare our method to Hamilton-Jacobi reachability. Having validated our theory, we demonstrate the computational scalability of our method by computing the reach-avoid set of a system with two kinematic cars.

    @inproceedings{LandryChenEtAl2018,
      author = {Landry, B. and Chen, M. and Hemley, S. and Pavone, M.},
      title = {Reach-Avoid Problems via Sum-of-Squares Optimization and Dynamic Programming},
      booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}},
      year = {2018},
      note = {Submitted},
      address = {Madrid, Spain},
      month = oct,
      url = {https://arxiv.org/pdf/1807.11553.pdf},
      owner = {blandry},
      timestamp = {2018-03-03}
    }
    
  23. B. Ivanovic, E. Schmerling, K. Leung, and M. Pavone, “Generative Modeling of Multimodal Multi-Human Behavior,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Madrid, Spain, 2018.

    Abstract: This work presents a methodology for modeling and predicting human behavior in settings with N humans interacting in highly multimodal scenarios (i.e. where there are many possible highly-distinct futures). A motivating example includes robots interacting with humans in crowded environments, such as self-driving cars operating alongside human-driven vehicles or human-robot collaborative bin packing in a warehouse. Our approach to model human behavior in such uncertain environments is to model humans in the scene as nodes in a graphical model, with edges encoding relationships between them. For each human, we learn a multimodal probability distribution over future actions from a dataset of multi-human interactions. Learning such distributions is made possible by recent advances in the theory of conditional variational autoencoders and deep learning approximations of probabilistic graphical models. Specifically, we learn action distributions conditioned on interaction history, neighboring human behavior, and candidate future agent behavior in order to take into account response dynamics. We demonstrate the performance of such a modeling approach in modeling basketball player trajectories, a highly multimodal, multi-human scenario which serves as a proxy for many robotic applications.

    @inproceedings{IvanovicSchmerlingEtAl2018,
      author = {Ivanovic, B. and Schmerling, E. and Leung, K. and Pavone, M.},
      title = {Generative Modeling of Multimodal Multi-Human Behavior},
      booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}},
      year = {2018},
      address = {Madrid, Spain},
      month = oct,
      url = {https://arxiv.org/pdf/1803.02015.pdf},
      owner = {borisi},
      timestamp = {2018-10-14}
    }
    
  24. F. Rossi, S. Bandyopadhyay, M. Wolf, and M. Pavone, “Review of Multi-Agent Algorithms for Collective Behavior: a Structural Taxonomy,” in IFAC Workshop on Networked & Autonomous Air & Space Systems, Santa Fe, New Mexico, 2018. (In Press)

    Abstract: In this paper, we review multi-agent collective behavior algorithms in the literature and classify them according to their underlying mathematical structure. For each mathematical technique, we identify the multi-agent coordination tasks it can be applied to, and we analyze its scalability, bandwidth use, and demonstrated maturity. We highlight how versatile techniques such as artificial potential functions can be used for applications ranging from low-level position control to high-level coordination and task allocation, we discuss possible reasons for the slow adoption of complex distributed coordination algorithms in the field, and we highlight areas for further research and development.

    @inproceedings{RossiBandyopadhyayEtAl2018,
      author = {Rossi, F. and Bandyopadhyay, S. and Wolf, M. and Pavone, M.},
      title = {Review of Multi-Agent Algorithms for Collective Behavior: a Structural Taxonomy},
      booktitle = {{IFAC Workshop on Networked \& Autonomous Air \& Space Systems}},
      year = {2018},
      note = {In Press},
      address = {Santa Fe, New Mexico},
      month = jun,
      keywords = {press},
      owner = {frossi2},
      timestamp = {2018-02-01}
    }
    
  25. R. A. Bunge, M. Pavone, and I. Kroo, “Minimal Altitude Loss Pullout Maneuvers,” in AIAA Conf. on Guidance, Navigation and Control, Kissimmee, Florida, 2018.

    Abstract: In a pullout maneuver an initially diving aircraft is returned to level flight. Depending on the initial condition, aircraft characteristics and control inputs, altitude loss may be significant and minimizing it can be important to avoid collision with the ground. A motivating example is that of stall/spin recoveries, where the pullout represents a majority of the total altitude lost. This paper presents a solution of the minimal altitude loss pullout maneuver by posing it as an infinite horizon optimal control problem and solving it using dynamic programming techniques on a reduced-order point mass model for a low-wing general aviation aircraft. The computed optimal policy results in a ?bang-bang? type controller, typical of shortest path problems, with maximum lift coefficient and bank rate applied at each point in time. The effect of maximum lift coefficient on the minimum altitude loss is analyzed, showing that attaining the highest lift coefficient possible throughout the pullout is critical. Based on these results a pullout flight control system is designed, with the optimal policy acting as an outer loop issuing commands to two inner loops that track lift coefficient and roll rate, respectively. The proposed pullout controller is tested on 6 DOF simulations, and shown to be effective at recovering the aircraft with close to optimal altitude loss.

    @inproceedings{BungePavoneEtAl2018,
      author = {Bunge, R.A. and Pavone, M. and Kroo, I.},
      title = {Minimal Altitude Loss Pullout Maneuvers},
      booktitle = {{AIAA Conf. on Guidance, Navigation and Control}},
      year = {2018},
      address = {Kissimmee, Florida},
      doi = {10.2514/6.2018-1339},
      month = jan,
      url = {../wp-content/papercite-data/pdf/Bunge.Pavone.Kroo.AIAAGNC18.pdf},
      owner = {frossi2},
      timestamp = {2018-01-21}
    }
    
  26. S. Chinchali et al., “Cellular Network Traffic Scheduling with Deep Reinforcement Learning,” in Proc. AAAI Conf. on Artificial Intelligence, New Orleans, Louisiana, 2018.

    Abstract: Modern mobile networks are facing unprecedented growth in demand due to a new class of traffic from Internet of Things (IoT) devices such as smart wearables and autonomous cars. Future networks must schedule delay-tolerant software updates, data backup, and other transfers from IoT devices while maintaining strict service guarantees for conventional real-time applications such as voice-calling and video. This problem is extremely challenging because conventional traffic is highly dynamic across space and time, so its performance is significantly impacted if all IoT traffic is scheduled immediately when it originates. In this paper, we present a reinforcement learning (RL) based scheduler that can dynamically adapt to traffic variation, and to various reward functions set by network operators, to optimally schedule IoT traffic. Using 4 weeks of real network data from downtown Melbourne, Australia spanning diverse traffic patterns, we demonstrate that our RL scheduler can enable mobile networks to carry 14.7% more data with minimal impact on existing traffic, and outperforms heuristic schedulers by more than 2x. Our work is a valuable step towards designing autonomous, "self- driving" networks that learn to manage themselves from past data.

    @inproceedings{ChinchaliHuEtAl2018,
      author = {Chinchali, S. and Hu, P. and Chu, T. and Sharma, M. and Bansal, M. and Misra, R. and Pavone, M. and Katti, S},
      title = {Cellular Network Traffic Scheduling with Deep Reinforcement Learning},
      booktitle = {{Proc. AAAI Conf. on Artificial Intelligence}},
      year = {2018},
      address = {New Orleans, Louisiana},
      month = feb,
      url = {../wp-content/papercite-data/pdf/Chinchali.ea.AAAI18.pdf},
      owner = {frossi2},
      timestamp = {2018-04-10}
    }
    
  27. B. Hockman, R. G. Reid, I. A. D. Nesnas, and M. Pavone, “Gravimetric Localization on the Surface of Small Bodies,” in IEEE Aerospace Conference, Big Sky, Montana, 2018.

    Abstract: The localization of landers on the surface of small bodies has traditionally relied on observations from a mothership (e.g. Rosetta’s Philae lander and Hayabusa 2’s MASCOT and MINERVA landers). However, when line-of-sight with the mothership is not always available, or for surface rovers that travel large distances, alternative mothership-independent localization techniques may be required. On-board vision-based techniques have demonstrated effective localization in terrestrial applications as well as for Mars rovers, but may be unreliable on small bodies where rovers must contend with fast-moving shadows, difficulties observing absolute scale, and issues acquiring images such as dust, sun blinding, tumbling and low albedo. We investigate the feasibility of an entirely new localization approach based on surface gravimetry, where a rover can constrain its location on the surface by precisely measuring the local gravity vector. This mothership-independent localization technique is well-suited to a class of hybrid rovers that can bounce and tumble over the surface of small bodies; it is insensitive to surface illumination, and even works at night. We develop a Bayesian framework for computing localization “likelihood maps” from gravimetry (and gradiometry) data, accounting for all sensor and model uncertainties. We then propose a method for deriving landing distributions of a bouncing rover from simulation data to serve as a prior for the localization estimate. Finally, we conduct a case study on the Philae lander, where we show how this approach could have helped reject localization hypotheses and significantly narrow the areas searched for the Philae lander.

    @inproceedings{HockmanReidEtAl2018,
      author = {Hockman, B. and Reid, R. G. and Nesnas, I. A. D. and Pavone, M.},
      title = {Gravimetric Localization on the Surface of Small Bodies},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2018},
      address = {Big Sky, Montana},
      month = mar,
      url = {../wp-content/papercite-data/pdf/Hockman.Reid.Nesnas.Pavone.AeroConf18.pdf},
      owner = {bhockman},
      timestamp = {2018-01-16}
    }
    
  28. B. Ichter, J. Harrison, and M. Pavone, “Learning Sampling Distributions for Robot Motion Planning,” in Proc. IEEE Conf. on Robotics and Automation, Brisbane, Australia, 2018.

    Abstract: A defining feature of sampling-based motion planning is the reliance on an implicit representation of the state space, which is enabled by a set of probing samples.Traditionally, these samples are drawn either probabilistically or deterministically to uniformly cover the state space. Yet, the motion of many robotic systems is often restricted to "small" regions of the state space, due to e.g. differential constraints or collision-avoidance constraints. To accelerate the planning process, it is thus desirable to devise non-uniform sampling strategies that favor sampling in those regions where an optimal solution might lie. This paper proposes a methodology for non-uniform sampling, whereby a sampling distribution is learnt from demonstrations, and then used to bias sampling. The sampling distribution is computed through a conditional variational autoencoder, allowing sample generation from the latent space conditioned on the specific planning problem. This methodology is general, can be used in combination with any sampling-based planner, and can effectively exploit the underlying structure of a planning problem while maintaining the theoretical guarantees of sampling-based approaches. Specifically, on several planning problems, the proposed methodology is shown to effectively learn representations for the relevant regions of the state space, resulting in an order of magnitude improvement in terms of success rate and convergence to the optimal cost

    @inproceedings{IchterHarrisonEtAl2018,
      author = {Ichter, B. and Harrison, J. and Pavone, M.},
      title = {Learning Sampling Distributions for Robot Motion Planning},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2018},
      address = {Brisbane, Australia},
      month = may,
      url = {https://arxiv.org/pdf/1709.05448.pdf},
      owner = {frossi2},
      timestamp = {2018-01-16}
    }
    
  29. E. Schmerling, K. Leung, W. Vollprecht, and M. Pavone, “Multimodal Probabilistic Model-Based Planning for Human-Robot Interaction,” in Proc. IEEE Conf. on Robotics and Automation, Brisbane, Australia, 2018.

    Abstract: This paper presents a method for constructing human-robot interaction policies in settings where multimodality, i.e., the possibility of multiple highly distinct futures, plays a critical role in decision making. We are motivated in this work by the example of traffic weaving, e.g., at highway onramps/offramps, where entering and exiting cars must swap lanes in a short distance — a challenging negotiation even for experienced drivers due to the inherent multimodal uncertainty of who will pass whom. Our approach is to learn multimodal probability distributions over future human actions from a dataset of human-human exemplars and perform real-time robot policy construction in the resulting environment model through massively parallel sampling of human responses to candidate robot action sequences. Direct learning of these distributions is made possible by recent advances in the theory of conditional variational autoencoders (CVAEs), whereby we learn action distributions simultaneously conditioned on the present interaction history, as well as candidate future robot actions in order to take into account response dynamics. We demonstrate the efficacy of this approach with a human-in-the-loop simulation of a traffic weaving scenario.

    @inproceedings{SchmerlingLeungEtAl2018,
      author = {Schmerling, E. and Leung, K. and Vollprecht, W. and Pavone, M.},
      title = {Multimodal Probabilistic Model-Based Planning for Human-Robot Interaction},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2018},
      address = {Brisbane, Australia},
      month = may,
      url = {../wp-content/papercite-data/pdf/Schmerling.Leung.Vollprecht.Pavone.ICRA18.pdf},
      owner = {schmrlng},
      timestamp = {2017-09-18}
    }
    
  30. R. Iglesias, F. Rossi, K. Wang, D. Hallac, J. Leskovec, and M. Pavone, “Data-Driven Model Predictive Control of Autonomous Mobility-on-Demand Systems,” in Proc. IEEE Conf. on Robotics and Automation, Brisbane, Australia, 2018.

    Abstract: The goal of this paper is to present an end-to-end, data-driven framework to control Autonomous Mobility-on-Demand systems (AMoD, i.e. fleets of self-driving vehicles). We first model the AMoD system using a time-expanded network, and present a formulation that computes the optimal rebalancing strategy (i.e., preemptive repositioning) and the minimum feasible fleet size for a given travel demand. Then, we adapt this formulation to devise a Model Predictive Control (MPC) algorithm that leverages short-term demand forecasts based on historical data to compute rebalancing strategies. We test the end-to-end performance of this controller with a state-of-the-art LSTM neural network to predict customer demand and real customer data from DiDi Chuxing: we show that this approach scales very well for large systems (indeed, the computational complexity of the MPC algorithm does not depend on the number of customers and of vehicles in the system) and outperforms state-of-the-art rebalancing strategies by reducing the mean customer wait time by up to to 89.6%.

    @inproceedings{IglesiasRossiEtAl2018,
      author = {Iglesias, R. and Rossi, F. and Wang, K. and Hallac, D. and Leskovec, J. and Pavone, M.},
      title = {Data-Driven Model Predictive Control of Autonomous Mobility-on-Demand Systems},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2018},
      address = {Brisbane, Australia},
      month = may,
      url = {../wp-content/papercite-data/pdf/Iglesias.Rossi.Wang.ea.ICRA18.pdf},
      owner = {frossi2},
      timestamp = {2018-01-14}
    }
    
  31. Z. Wang, S. Singh, M. Pavone, and M. Schwager, “Cooperative Object Transport in 3D with Multiple Quadrotors using No Peer Communication,” in Proc. IEEE Conf. on Robotics and Automation, Brisbane, Australia, 2018.

    Abstract: We present a framework to enable a fleet of rigidly attached quadrotor aerial robots to transport heavy objects along a known reference trajectory without inter-robot communication or centralized coordination. Leveraging a distributed wrench controller, we provide exponential stability guarantees for the entire assembly, under a mild geometric condition. This is achieved by each quadrotor independently solving a local optimization problem to counteract the biased torque effects from each robot in the assembly. We rigorously analyze the controllability of the object, design a distributed compensation scheme to address these challenges, and show that the resulting strategy collectively guarantees full group control authority. To ensure feasibility for online implementation, we derive bounds on the net desired control wrench, characterize the output wrench space of each quadrotor, and perform subsequent trajectory optimization under these input constraints. We thoroughly validate our method in simulation with eight quadrotors transporting a heavy object in a cluttered environment subject to various sources of uncertainty, and demonstrate the algorithm’s resilience.

    @inproceedings{WangSinghEtAl2018,
      author = {Wang, Z. and Singh, S. and Pavone, M. and Schwager, M.},
      title = {Cooperative Object Transport in {3D} with Multiple Quadrotors using No Peer Communication},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2018},
      address = {Brisbane, Australia},
      month = may,
      url = {../wp-content/papercite-data/pdf/Wang.Singh.Pavone.ea.ICRA18.pdf},
      owner = {ssingh19},
      timestamp = {2018-01-16}
    }
    
  32. S. P. Chinchali, A. Anemogiannis, T. Chu, R. Misra, M. Pavone, and S. Katti, “Decoupling Prediction and Control Across Data Boundaries,” in Proc. ACM Workshop on Hot Topics in Networks, Seattle, Washington, 2018. (Submitted)

    Abstract: Today’s networks have access to a wealth of real-time connectivity information that can be used to provide accurate forecasts of bandwidth or city-wide cell congestion. Network operators have an incentive to deliver such rich forecasts to external control application developers, who can leverage them to improve mobile video streaming or ride-sharing services. The two entities of a network operator and downstream control application developer must decide a concise forecast representation to share across a data boundary that is mutually beneficial. A key challenge is that an application’s control decisions, which could be proprietary, affect future network state, requiring some form of feedback across the data boundary. We propose how to decouple network prediction and control units for key benefits of modularity, increased interpretability, and re-usability across applications.

    @inproceedings{ChinchaliAnemogiannisEtAl2018,
      author = {Chinchali, S. P. and Anemogiannis, A. and Chu, T. and Misra, R. and Pavone, M. and Katti, S.},
      title = {Decoupling Prediction and Control Across Data Boundaries},
      booktitle = {{Proc. ACM Workshop on Hot Topics in Networks}},
      year = {2018},
      note = {Submitted},
      address = {Seattle, Washington},
      month = oct,
      keywords = {sub},
      owner = {chinchali},
      timestamp = {2018-07-25}
    }
    
  33. M. Chen, Q. Tam, S. C. Livingston, and M. Pavone, “Signal Temporal Logic meets Hamilton-Jacobi Reachability: Connections and Applications,” in Workshop on Algorithmic Foundations of Robotics, Merida, Mexico, 2018. (Submitted)

    Abstract: Signal temporal logic (STL) and Hamilton-Jacobi (HJ) reachability analysis are effective mathematical tools for formally analyzing the behavior of robotic systems. STL is a specification language that uses a combination of logic and temporal operators to precisely express real-valued and time-dependent requirements on system behaviors. While recursively defined STL specifications are extremely expressive and controller synthesis methods exist, so far there has not been work that quantifies the set of states from which STL formulas can be satisfied. HJ reachability, on the other hand, is a method for computing the reachable set, that is the set of states from which a system is able to reach a goal while satisfying state and control constraints. While reasoning about system requirements through sets of states is useful for predetermining whether it is possible to satisfy desired system properties as well as obtaining state feedback controllers, so far the applicability of HJ reachability has been limited to relatively simple reach-avoid specifications. In this paper, we merge STL and HJ reachability into a single framework that combines the key advantage of both methods ? expressiveness of specifications and set quantification. To do this, we establish a correspondence between temporal and reachability operators, and utilize the idea of least-restrictive feasible controller sets (LRFCSs) to break down controller synthesis for complex STL formulas into a sequence of reachability and elementary set operations. LRFCSs are crucial for avoiding controller conflicts among the different reachability operations. In addition, the synthesized state feedback controllers are guaranteed to satisfy STL specifications if determined to be possible by our framework, and violate specifications minimally if not. We demonstrate our method through numerical simulations and robotic experiments.

    @inproceedings{ChenTamEtAl2018,
      author = {Chen, M. and Tam, Q. and Livingston, S. C. and Pavone, M.},
      title = {Signal Temporal Logic meets {Hamilton-Jacobi} Reachability: Connections and Applications},
      booktitle = {{Workshop on Algorithmic Foundations of Robotics}},
      year = {2018},
      note = {Submitted},
      address = {Merida, Mexico},
      month = oct,
      url = {../wp-content/papercite-data/pdf/Chen.Tam.Livingston.Pavone.WAFR18.pdf},
      keywords = {sub},
      owner = {bylard},
      timestamp = {2018-07-24}
    }
    
  34. R. MacPherson, B. Hockman, A. Bylard, M. A. Estrada, M. R. Cutkosky, and M. Pavone, “Trajectory Optimization for Dynamic Grasping in Space using Adhesive Grippers,” in Field and Service Robotics, Zurich, Switzerland, 2017.

    Abstract: Spacecraft equipped with gecko-inspired dry adhesive grippers can dynamically grasp objects having a wide variety of featureless surfaces. In this paper we propose an optimization-based control strategy to exploit the dynamic robustness of such grippers for the task of grasping a free-floating, spinning object. First, we extend previous work characterizing the dynamic grasping capabilities of these grippers to the case where both object and spacecraft are free-floating and comparably sized. We then formulate the acquisition problem as a two-phase optimal control problem, which is amenable to real time implementation and can handle constraints on velocity, control, as well as integer timing constraints for grasping a specific target location on the surface of a spinning object. Conservative analytical bounds on the set of initial states that guarantee persistent feasibility are derived.

    @inproceedings{MacPhersonHockmanEtAl2017,
      author = {MacPherson, R. and Hockman, B. and Bylard, A. and Estrada, M. A. and Cutkosky, M. R. and Pavone, M.},
      title = {Trajectory Optimization for Dynamic Grasping in Space using Adhesive Grippers},
      booktitle = {{Field and Service Robotics}},
      year = {2017},
      address = {Zurich, Switzerland},
      month = sep,
      url = {../wp-content/papercite-data/pdf/MacPherson.Hockman.Bylard.ea.FSR17.pdf},
      owner = {bylard},
      timestamp = {2018-01-16}
    }
    
  35. A. Bylard, R. MacPherson, B. Hockman, M. R. Cutkosky, and M. Pavone, “Robust Capture and Deorbit of Rocket Body Debris Using Controllable Dry Adhesion,” in IEEE Aerospace Conference, Big Sky, Montana, 2017.

    Abstract: Removing large orbital debris in a safe, robust, and cost-effective manner is a long-standing challenge, having serious implications for LEO satellite safety and access to space. Many studies have focused on the deorbit of spent rocket bodies (R/Bs) as an achievable and high-priority first step. However, major difficulties arise from the R/Bs’ residual tumble and lack of traditional docking/grasping fixtures. Previously investigated docking strategies often require complex and risky approach maneuvers or have a high chance of producing additional debris. To address this challenge, this paper investigates the use of controllable dry adhesives (CDAs), also known as gecko-inspired adhesives, as an alternative approach to R/B docking and deorbiting. CDAs are gathering interest for in-space grasping and manipulation due to their ability to controllably attach to and detach from any smooth, clean surface, including flat and curved surfaces. Such capability significantly expands the number and types of potential docking locations on a target. CDAs are also inexpensive, are space-qualified (performing well in a vacuum, in extreme temperatures, and under radiation), and can attach and detach while applying minimal force to a target surface, all important considerations for space deployment. In this paper, we investigate a notional strategy for initial capture and stabilization of a R/B having multi-axis tumble, exploiting the unique properties of CDA grippers to reduce maneuver complexity, and we propose alternatives for rigidly attaching deorbiting kits to a R/B. Simulations based on experimentally verified models of CDA grippers show that these approaches show promise as robust alternatives to previously explored methods.

    @inproceedings{BylardMacPhersonEtAl2017,
      author = {Bylard, A. and MacPherson, R. and Hockman, B. and Cutkosky, M. R. and Pavone, M.},
      title = {Robust Capture and Deorbit of Rocket Body Debris Using Controllable Dry Adhesion},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2017},
      address = {Big Sky, Montana},
      month = mar,
      url = {../wp-content/papercite-data/pdf/Bylard.MacPherson.Hockman.ea.AeroConf17.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  36. A. Sushko, A. Tedjarati, J. Creus-Costa, S. Maldonado, K. Marshland, and M. Pavone, “Low cost, high endurance, altitude-controlled latex balloon for near-space research (ValBal),” in IEEE Aerospace Conference, Big Sky, Montana, 2017.

    Abstract: High-altitude balloons in near space offer the possibility of affordable scientific experimentation and hardware testing for outer space missions. In this paper we present a novel, low cost high-altitude balloon system that achieves multi-day flight using inexpensive latex balloons by automatically venting lifting gas and dispensing ballast to maintain altitude. Traditionally, superpressure balloons have been used for high-altitude scientific missions; however, despite their long endurance and payload capacity in the tens of kilograms, their cost is in excess of tens of thousands of dollars. Latex balloons are significantly less expensive, typically costing little more than a hundred dollars, but in normal use fly for only a couple hours, rising until reduced atmospheric pressure causes the balloon to stretch beyond its limits. Precision-weighted latex balloons have demonstrated multi-day flights, but such systems cannot change altitude while aloft and offer minimal payload capacity (measuring in tens of grams). Our system, known as ValBal, offers altitude control capabilities exceeding those of a superpressure balloon at a two order of magnitude reduction in cost. ValBal can stabilize anywhere in its operational range of 10-25 km altitude, and can execute scheduled or remotely commanded altitude transitions during flight. In its current iteration, ValBal can be configured to accommodate payloads on the order of 10000 cubic centimeters and 2 kilograms. In June 2016, a ValBal demonstration mission flew for over 70 hours continuously, surpassing the previous world record of 57 hours, for the longest duration of a latex balloon flight. ValBal has flown twice more since then, including a flight of almost 80 hours. Planned developments will seek to improve the endurance to a week and increase the payload interface capabilities for scientific missions.

    @inproceedings{SushkoTedjaratiEtAl2017,
      author = {Sushko, A. and Tedjarati, A. and Creus-Costa, J. and Maldonado, S. and Marshland, K. and Pavone, M.},
      title = {Low cost, high endurance, altitude-controlled latex balloon for near-space research ({ValBal})},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2017},
      address = {Big Sky, Montana},
      month = mar,
      url = {../wp-content/papercite-data/pdf/Suskho.Tedjarati.ea.AERO2017.pdf},
      owner = {frossi2},
      timestamp = {2017-10-05}
    }
    
  37. 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}
    }
    
  38. S. Singh, A. Majumdar, J.-J. E. Slotine, and M. Pavone, “Robust Online Motion Planning via Contraction Theory and Convex Optimization,” in Proc. IEEE Conf. on Robotics and Automation, Singapore, 2017.

    Abstract: We present a framework for online generation of robust motion plans for robotic systems with nonlinear dynamics subject to bounded disturbances, control constraints, and online state constraints such as obstacles. In an offline phase, one computes the structure of a feedback controller that can be efficiently implemented online to track any feasible nominal trajectory. The offline phase leverages contraction theory and convex optimization to characterize a fixed-size “tube” that the state is guaranteed to remain within while tracking a nominal trajectory (representing the center of the tube). In the online phase, when the robot is faced with obstacles, a motion planner uses such a tube as a robustness margin for collision checking, yielding nominal trajectories that can be safely executed (i.e., tracked without collisions under disturbances). In contrast to recent work on robust online planning using funnel libraries, our approach is not restricted to a fixed library of maneuvers computed offline and is thus particularly well-suited to applications such as UAV flight in densely cluttered environments where complex maneuvers may be required to reach a goal. We demonstrate our approach through simulations of a 6-state planar quadrotor navigating cluttered environments in the presence of a cross-wind. We also discuss applications of our approach to Tube Model Predictive Control (TMPC) and compare the merits of our method with state-of-the-art nonlinear TMPC techniques.

    @inproceedings{SinghMajumdarEtAl2017,
      author = {Singh, S. and Majumdar, A. and Slotine, J.-J. E. and Pavone, M.},
      title = {Robust Online Motion Planning via Contraction Theory and Convex Optimization},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2017},
      note = {{Extended Version, Available at }\url{http://asl.stanford.edu/wp-content/papercite-data/pdf/Singh.Majumdar.Slotine.Pavone.ICRA17.pdf}},
      address = {Singapore},
      month = may,
      url = {../wp-content/papercite-data/pdf/Singh.Majumdar.Slotine.Pavone.ICRA17.pdf},
      owner = {bylard},
      timestamp = {2018-06-30}
    }
    
  39. 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}
    }
    
  40. B. Ichter, E. Schmerling, and M. Pavone, “Group Marching Tree: Sampling-Based Approximately Optimal Motion Planning on GPUs,” in IEEE Int. Conf. on Robotic Computing, Taichung, Taiwan, 2017.

    Abstract: This paper presents a novel approach, named the Group Marching Tree (GMT*) algorithm, to planning on GPUs at rates amenable to application within control loops, allowing planning in real-world settings via repeated computation of near-optimal plans. GMT*, like the Fast Marching Tree (FMT*) algorithm, explores the state space with a “lazy” dynamic programming recursion on a set of samples to grow a tree of near-optimal paths. GMT*, however, alters the approach of FMT* with approximate dynamic programming by expanding, in parallel, the group of all active samples with cost below an increasing threshold, rather than only the minimum cost sample. This group approximation enables low-level parallelism over the sample set and removes the need for sequential data structures, while the “lazy” collision checking limits thread divergence—all contributing to a very efficient GPU implementation. While this approach incurs some suboptimality, we prove that GMT* remains asymptotically optimal up to a constant multiplicative factor. We show solutions for complex planning problems under differential constraints can be found in  10 ms on a desktop GPU and  30 ms on an embedded GPU, representing a significant speed up over the state of the art, with only small losses in performance. Finally, we present a scenario demonstrating the efficacy of planning within the control loop ( 100 Hz) towards operating in dynamic, uncertain settings.

    @inproceedings{IchterSchmerlingEtAl2017b,
      author = {Ichter, B. and Schmerling, E. and Pavone, M.},
      title = {Group Marching Tree: Sampling-Based Approximately Optimal Motion Planning on {GPUs}},
      booktitle = {{IEEE Int. Conf. on Robotic Computing}},
      year = {2017},
      address = {Taichung, Taiwan},
      month = apr,
      url = {../wp-content/papercite-data/pdf/Ichter.Schmerling.Pavone.ICRC17.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  41. 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}
    }
    
  42. J. Harrison et al., “ADAPT: Zero-Shot Adaptive Policy Transfer for Stochastic Dynamical Systems,” in Int. Symp. on Robotics Research, Puerto Varas, Chile, 2017.

    Abstract: Model-free policy learning has enabled robust performance of complex tasks with relatively simple algorithms. However, this simplicity comes at the cost of requiring an Oracle and arguably very poor sample complexity. This renders such methods unsuitable for physical systems. Variants of model-based methods address this problem through the use of simulators, however, this gives rise to the problem of policy transfer from simulated to the physical system. Model mismatch due to systematic parameter shift and unmodelled dynamics error may cause suboptimal or unsafe behavior upon direct transfer. We introduce the Adaptive Policy Transfer for Stochastic Dynamics (ADAPT) algorithm that achieves provably safe and robust, dynamically-feasible zero-shot transfer of RL-policies to new domains with dynamics error. ADAPT combines the strengths of offline policy learning in a black-box source simulator with online tube-based MPC to attenuate bounded model mismatch between the source and target dynamics. ADAPT allows online transfer of policy, trained solely in a simulation offline, to a family of unknown targets without fine-tuning. We also formally show that (i) ADAPT guarantees state and control safety through state-action tubes under the assumption of Lipschitz continuity of the divergence in dynamics and, (ii) ADAPT results in a bounded loss of reward accumulation in case of direct transfer with ADAPT as compared to a policy trained only on target. We evaluate ADAPT on 2 continuous, non-holonomic simulated dynamical systems with 4 different disturbance models, and find that ADAPT performs between 50%-300% better on mean reward accrual than direct policy transfer.

    @inproceedings{HarrisonGargEtAl2017,
      author = {Harrison, J. and Garg, A. and Ivanovic, B. and Zhu, Y. and Savarese, S. and Li, F.-F. and Pavone, M.},
      title = {{ADAPT:} Zero-Shot Adaptive Policy Transfer for Stochastic Dynamical Systems},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2017},
      address = {Puerto Varas, Chile},
      month = dec,
      url = {https://arxiv.org/pdf/1707.04674.pdf},
      owner = {pavone},
      timestamp = {2018-01-16}
    }
    
  43. S. P. Chinchali, S. C. Livingston, and M. Pavone, “Multi-objective optimal control for proactive decision-making with temporal logic models,” in Int. Symp. on Robotics Research, Puerto Varas, Chile, 2017.

    Abstract: The operation of today’s robots increasingly entails interactions with humans, in settings ranging from autonomous driving amidst human-driven vehicles to collaborative manufacturing. To effectively do so, robots must proactively decode the intent or plan of humans and concurrently leverage such a knowledge for safe, cooperative task satisfaction—a problem we refer to as proactive decision making. However, the problem of proactive intent decoding coupled with robotic control is computationally intractable as a robot must reason over several possible human behavioral models and resulting high-dimensional state trajectories. In this paper, we address the proactive decision making problem using a novel combination of algorithmic and data mining techniques. First, we distill high-dimensional state trajectories of human-robot interaction into concise, symbolic behavioral summaries that can be learned from data. Second, we leverage formal methods to model high-level agent goals, safe interaction, and information-seeking behavior with temporal logic formulae. Finally, we design a novel decision-making scheme that simply maintains a belief distribution over high-level, symbolic models of human behavior, and proactively plans informative control actions. Leveraging a rich dataset of real human driving data in crowded merging scenarios, we generate temporal logic models and use them to synthesize control strategies using tree-based value iteration and reinforcement learning (RL). Results from two simulated self-driving car scenarios, one cooperative and the other adversarial, demonstrate that our data-driven control strategies enable safe interaction, correct model identification, and significant dimensionality reduction.

    @inproceedings{ChinchaliLivingstonEtAl2017,
      author = {Chinchali, S. P. and Livingston, S. C. and Pavone, M.},
      title = {Multi-objective optimal control for proactive decision-making with temporal logic models},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2017},
      address = {Puerto Varas, Chile},
      month = dec,
      url = {../wp-content/papercite-data/pdf/Chinchali.Livingston.Pavone.ISRR17.pdf},
      owner = {pavone},
      timestamp = {2018-01-16}
    }
    
  44. A. Majumdar and M. Pavone, “How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics,” in Int. Symp. on Robotics Research, Puerto Varas, Chile, 2017.

    Abstract: Endowing robots with the capability of assessing risk and making risk-aware decisions is widely considered a key step toward ensuring safety for robots operating under uncertainty. But, how should a robot quantify risk? A natural and common approach is to consider the framework whereby costs are assigned to stochastic outcomes - an assignment captured by a cost random variable. Quantifying risk then corresponds to evaluating a risk metric, i.e., a mapping from the cost random variable to a real number. Yet, the question of what constitutes a "good" risk metric has received little attention within the robotics community. The goal of this paper is to explore and partially address this question by advocating axioms that risk metrics in robotics applications should satisfy in order to be employed as rational assessments of risk. We discuss general representation theorems that precisely characterize the class of metrics that satisfy these axioms (referred to as distortion risk metrics), and provide instantiations that can be used in applications. We further discuss pitfalls of commonly used risk metrics in robotics, and discuss additional properties that one must consider in sequential decision making tasks. Our hope is that the ideas presented here will lead to a foundational framework for quantifying risk (and hence safety) in robotics applications.

    @inproceedings{MajumdarPavone2017,
      author = {Majumdar, A. and Pavone, M.},
      title = {How Should a Robot Assess Risk? {Towards} an Axiomatic Theory of Risk in Robotics},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2017},
      address = {Puerto Varas, Chile},
      month = dec,
      url = {../wp-content/papercite-data/pdf/Majumdar.Pavone.ISRR17.pdf},
      owner = {anirudha},
      timestamp = {2018-01-16}
    }
    
  45. B. Hockman and M. Pavone, “Stochastic Motion Planning for Hopping Rovers on Small Solar System Bodies,” in Int. Symp. on Robotics Research, Puerto Varas, Chile, 2017.

    Abstract: Hopping rovers have emerged as a promising platform for the future surface exploration of small Solar System bodies, such as asteroids and comets. However, hopping dynamics are governed by nonlinear gravity fields and stochastic bouncing on highly irregular surfaces, which pose several challenges for traditional motion planning methods. This paper presents the first ever discussion of motion planning for hopping rovers that explicitly accounts for various sources of uncertainty. We first address the problem of planning a single hopping trajectory by developing (1) an algorithm for robustly solving Lambert’s orbital boundary value problems in irregular gravity fields, and (2) a method for computing landing distributions by propagating control and model uncertainties—from which, a time/energy-optimal hop can be selected using a (myopic) policy gradient. We then cast the sequential planning problem as a Markov decision process and apply a sample-efficient, off-line, off-policy reinforcement learning algorithm—namely, a variant of least squares policy iteration (LSPI)—to derive approximately optimal control policies that are safe, efficient, and amenable to real-time implementation on computationally-constrained rover hardware. These policies are demonstrated in simulation to be robust to modelling errors and outperform previous heuristics.

    @inproceedings{HockmanPavone2017,
      author = {Hockman, B. and Pavone, M.},
      title = {Stochastic Motion Planning for Hopping Rovers on Small Solar System Bodies},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2017},
      address = {Puerto Varas, Chile},
      month = dec,
      url = {../wp-content/papercite-data/pdf/Hockman.Pavone.ISRR17.pdf},
      owner = {bhockman},
      timestamp = {2018-01-16}
    }
    
  46. B. Ichter, B. Landry, E. Schmerling, and M. Pavone, “Perception-Aware Motion Planning via Multiobjective Search on GPUs,” in Int. Symp. on Robotics Research, Puerto Varas, Chile, 2017.

    Abstract: In this paper we approach the robust motion planning problem through the lens of perception-aware planning, whereby we seek a low-cost motion plan subject to a separate constraint on perception localization quality. To solve this problem we introduce the Multiobjective Perception-Aware Planning (MPAP) algorithm which explores the state space via a multiobjective search, considering both cost and a perception heuristic. This perception-heuristic formulation allows us to both capture the history dependence of localization drift and represent complex modern perception methods. The solution trajectory from this heuristic-based search is then certified via Monte Carlo methods to be robust. The additional computational burden of perception-aware planning is offset through massive parallelization on a GPU. Through numerical experiments the algorithm is shown to find robust solutions in about a second. Finally, we demonstrate MPAP on a quadrotor flying perception-aware and perception-agnostic plans using Google Tango for localization, finding the quadrotor safely executes the perception-aware plan every time, while crashing over 20% of the time on the perception-agnostic due to loss of localization.

    @inproceedings{IchterLandryEtAl2017,
      author = {Ichter, B. and Landry, B. and Schmerling, E. and Pavone, M.},
      title = {Perception-Aware Motion Planning via Multiobjective Search on {GPUs}},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2017},
      address = {Puerto Varas, Chile},
      month = dec,
      url = {https://arxiv.org/pdf/1705.02408.pdf},
      owner = {ichter},
      timestamp = {2018-01-16}
    }
    
  47. A. Majumdar, S. Singh, A. Mandlekar, and M. Pavone, “Risk-sensitive Inverse Reinforcement Learning via Coherent Risk Models,” in Robotics: Science and Systems, Cambridge, Massachusetts, 2017.

    Abstract: The literature on Inverse Reinforcement Learning (IRL) typically assumes that humans take actions in order to minimize the expected value of a cost function, i.e., that humans are risk neutral. Yet, in practice, humans are often far from being risk neutral. To fill this gap, the objective of this paper is to devise a framework for risk-sensitive IRL in order to explicitly account for an expert’s risk sensitivity. To this end, we propose a flexible class of models based on coherent risk metrics, which allow us to capture an entire spectrum of risk preferences from risk-neutral to worst-case. We propose efficient algorithms based on Linear Programming for inferring an expert’s underlying risk metric and cost function for a rich class of static and dynamic decision-making settings. The resulting approach is demonstrated on a simulated driving game with ten human participants. Our method is able to infer and mimic a wide range of qualitatively different driving styles from highly risk-averse to risk-neutral in a data-efficient manner. Moreover, comparisons of the Risk-Sensitive (RS) IRL approach with a risk-neutral model show that the RS-IRL framework more accurately captures observed participant behavior both qualitatively and quantitatively.

    @inproceedings{MajumdarSinghEtAl2017,
      author = {Majumdar, A. and Singh, S. and Mandlekar, A. and Pavone, M.},
      title = {Risk-sensitive Inverse Reinforcement Learning via Coherent Risk Models},
      booktitle = {{Robotics: Science and Systems}},
      year = {2017},
      address = {Cambridge, Massachusetts},
      month = jul,
      url = {../wp-content/papercite-data/pdf/Majumdar.Singh.Mandlekar.Pavone.RSS17.pdf},
      owner = {ssingh19},
      timestamp = {2017-04-28}
    }
    
  48. E. Schmerling and M. Pavone, “Evaluating Trajectory Collision Probability through Adaptive Importance Sampling for Safe Motion Planning,” in Robotics: Science and Systems, Cambridge, Massachusetts, 2017.

    Abstract: This paper presents a tool for addressing a key component in many algorithms for planning robot trajectories under uncertainty: evaluation of the safety of a robot whose actions are governed by a closed-loop feedback policy near a nominal planned trajectory. We describe an adaptive importance sampling Monte Carlo framework that enables the evaluation of a given control policy for satisfaction of a probabilistic collision avoidance constraint which also provides an associated certificate of accuracy (in the form of a confidence interval). In particular this adaptive technique is well-suited to addressing the complexities of rigid-body collision checking applied to non-linear robot dynamics. As a Monte Carlo method it is amenable to parallelization for computational tractability, and is generally applicable to a wide gamut of simulatable systems, including alternative noise models. Numerical experiments demonstrating the effectiveness of the adaptive importance sampling procedure are presented and discussed.

    @inproceedings{SchmerlingPavone2017,
      author = {Schmerling, E. and Pavone, M.},
      title = {Evaluating Trajectory Collision Probability through Adaptive Importance Sampling for Safe Motion Planning},
      booktitle = {{Robotics: Science and Systems}},
      year = {2017},
      address = {Cambridge, Massachusetts},
      month = jul,
      url = {https://arxiv.org/pdf/1609.05399.pdf},
      owner = {schmrlng},
      timestamp = {2018-01-16}
    }
    
  49. M. A. Estrada, H. Jiang, B. Noll, E. W. Hawkes, M. Pavone, and M. R. Cutkosky, “Force and Moment Constraints of a Curved Surface Gripper and Wrist for Assistive Free Flyers,” in Proc. IEEE Conf. on Robotics and Automation, Singapore, 2017.

    Abstract: Free-flying robots have the potential to autonomously fulfill a wide range of tasks involving manipulation of objects in space. In this paper we study the design of a wrist mechanism for free-flying robots that are equipped with an adhesive gripper for attaching to objects and surfaces. The wrist and gripper allow the robots to apply moments in addition to forces, which increases their versatility for object manipulation. We apply grasp optimization to establish limitations on the forces/moments that the wrist can impart, subject to adhesion capabilities. Building on these results, we present an approach for tuning a passive wrist mechanism, or controlling an active wrist, to broaden the range of forces and moments that the robot can exert. Our theoretical insights and wrist designs are validated in simulations and on a planar micro-gravity test bed.

    @inproceedings{EstradaJiangEtAl2017,
      author = {Estrada, M. A. and Jiang, H. and Noll, B. and Hawkes, E. W. and Pavone, M. and Cutkosky, M. R.},
      title = {Force and Moment Constraints of a Curved Surface Gripper and Wrist for Assistive Free Flyers},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2017},
      address = {Singapore},
      month = may,
      url = {../wp-content/papercite-data/pdf/Estrada.Jiang.Noll.ea.ICRA17.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  50. B. Ichter, E. Schmerling, A. Agha-mohammadi, and M. Pavone, “Real-Time Stochastic Kinodynamic Motion Planning via Multiobjective Search on GPUs,” in Proc. IEEE Conf. on Robotics and Automation, Singapore, 2017.

    Abstract: In this paper we present the PUMP (Parallel Uncertainty-aware Multiobjective Planning) algorithm for addressing the stochastic kinodynamic motion planning problem, whereby we seek a low-cost, dynamically-feasible motion plan subject to a constraint on collision probability (CP). As a departure from previous methods for chance-constrained motion planning, PUMP directly considers both CP and the optimization objective at equal priority when planning through the free configuration space, achieving an unprecedented combination of cost performance, certified safety, and speed. Planning is conducted through a massively parallel multiobjective search, here implemented with a particular application focus on GPU hardware. PUMP explores the configuration space while maintaining a Pareto optimal front of motion plans, considering cost and approximate collision probability. We introduce a novel particle-based CP approximation scheme, designed for efficient GPU implementation, which accounts for dependencies over the history of a trajectory execution. Upon termination of the exploration phase, PUMP performs a search over the Pareto optimal set of solution motion plans to identify the lowest cost motion plan that is certified to satisfy the CP constraint (according to an asymptotically exact estimator). We present numerical experiments for quadrotor planning wherein PUMP identifies solutions in  100 ms, evaluating over one hundred thousand partial plans through the course of its exploration phase. The results show that this multiobjective search achieves a lower motion plan cost, for the same collision probability constraint, compared to a safety buffer-based search heuristic and repeated RRT trials.

    @inproceedings{IchterSchmerlingEtAl2017,
      author = {Ichter, B. and Schmerling, E. and Agha-mohammadi, A. and Pavone, M.},
      title = {Real-Time Stochastic Kinodynamic Motion Planning via Multiobjective Search on {GPUs}},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2017},
      address = {Singapore},
      month = may,
      url = {http://arxiv.org/pdf/1607.06886.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  51. J. A. Starek, E. Schmerling, G. D. Maher, B. W. Barbee, and M. Pavone, “Real-Time, Propellant-Optimized Spacecraft Motion Planning under Clohessy-Wiltshire-Hill Dynamics,” in IEEE Aerospace Conference, Big Sky, Montana, 2016.

    Abstract: This paper presents a sampling-based motion planning algorithm for real-time, propellant-optimized autonomous spacecraft trajectory generation in near-circular orbits. Specifically, this paper leverages recent algorithmic advances in the field of robot motion planning to the problem of impulsively-actuated, propellant-optimized rendezvous and proximity operations under the Clohessy-Wiltshire-Hill (CWH) dynamics model. The approach calls upon a modified version of the Fast Marching Tree (FMT*) algorithm to grow a set of feasible and actively-safe trajectories over a deterministic, low-dispersion set of sample points covering the free state space. Key features of the proposed algorithm include: (i) theoretical guarantees of trajectory safety and performance, (ii) real-time implementability, and (iii) generality, in the sense that a large class of constraints can be handled directly. As a result, the proposed algorithm offers the potential for widespread application, ranging from on-orbit satellite servicing to orbital debris removal and autonomous inspection missions.

    @inproceedings{StarekSchmerlingEtAl2016b,
      author = {Starek, J. A. and Schmerling, E. and Maher, G. D. and Barbee, B. W. and Pavone, M.},
      title = {Real-Time, Propellant-Optimized Spacecraft Motion Planning under {Clohessy-Wiltshire-Hill} Dynamics},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2016},
      address = {Big Sky, Montana},
      doi = {10.1109/aero.2016.7500704},
      month = mar,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Starek.Schmerling.ea.AeroConf16.pdf}
    }
    
  52. R. Allen and M. Pavone, “A Real-Time Framework for Kinodynamic Planning with Application to Quadrotor Obstacle Avoidance,” in AIAA Conf. on Guidance, Navigation and Control, San Diego, CA, 2016.

    Abstract: The objective of this paper is to present a full-stack, real-time kinodynamic planning framework and demonstrate it on a quadrotor for collision avoidance. Specifically, the proposed framework utilizes an offline-online computation paradigm, neighborhood classification through machine learning, sampling-based motion planning with an optimal control distance metric, and trajectory smoothing to achieve real-time planning for aerial vehicles. The approach is demonstrated on a quadrotor navigating obstacles in an indoor space and stands as, arguably, one of the first demonstrations of full-online kinodynamic motion planning; exhibiting execution times under 1/3 of a second. For the quadrotor, a simplified dynamics model is used during the planning phase to accelerate online computation. A trajectory smoothing phase, which leverages the differentially flat nature of quadrotor dynamics, is then implemented to guarantee a dynamically feasible trajectory.

    @inproceedings{AllenPavone2016b,
      author = {Allen, R. and Pavone, M.},
      title = {A Real-Time Framework for Kinodynamic Planning with Application to Quadrotor Obstacle Avoidance},
      booktitle = {{AIAA Conf. on Guidance, Navigation and Control}},
      year = {2016},
      address = {San Diego, CA},
      doi = {10.2514/6.2016-1374},
      month = jan,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Allen.Pavone.AIAAGNC16.pdf}
    }
    
  53. M. A. Estrada, B. Hockman, A. Bylard, E. W. Hawkes, M. R. Cutkosky, and M. Pavone, “Free-Flyer Acquisition of Spinning Objects with Gecko-Inspired Adhesives,” in Proc. IEEE Conf. on Robotics and Automation, Stockholm, Sweden, 2016.

    Abstract: We explore the use of grippers with gecko-inspired adhesives for spacecraft docking and acquisition of tumbling objects in microgravity. Towards the goal of autonomous object manipulation in space, adhesive grippers mounted on planar free-floating platforms are shown to be tolerant of a range of incoming linear and angular velocities. Through modeling, simulations, and experiments, we characterize the dynamic “grasping envelope” for successful acquisition and derive insights to inform future gripper designs and grasping strategies for motion planning.

    @inproceedings{EstradaHockmanEtAl2016,
      author = {Estrada, M. A. and Hockman, B. and Bylard, A. and Hawkes, E. W. and Cutkosky, M. R. and Pavone, M.},
      title = {Free-Flyer Acquisition of Spinning Objects with Gecko-Inspired Adhesives},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2016},
      address = {Stockholm, Sweden},
      doi = {10.1109/ICRA.2016.7487696},
      month = may,
      url = {../wp-content/papercite-data/pdf/Estrada.Hockman.Bylard.ea.ICRA16.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  54. Z. Sunberg, M. Kochenderfer, and M. Pavone, “Optimized and Trusted Collision Avoidance for Unmanned Aerial Vehicles using Approximate Dynamic Programming,” in Proc. IEEE Conf. on Robotics and Automation, Stockholm, Sweden, 2016.

    Abstract: Safely integrating unmanned aerial vehicles into civil airspace is contingent upon development of a trustworthy collision avoidance system. This paper proposes an approach whereby a parameterized resolution logic that is considered trusted for a given range of its parameters is adaptively tuned online. Specifically, to address the potential conservatism of the resolution logic with static parameters, we present a dynamic programming approach for adapting the parameters dynamically based on the encounter state. We compute the adaptation policy offline using simulation-based approximate dynamic programming which can handle the high dimensionality of the problem. Numerical experiments show that this approach improves safety and operational performance compared to the baseline resolution logic, while retaining trustworthiness.

    @inproceedings{SunbergKochenderferEtAl2016,
      author = {Sunberg, Z. and Kochenderfer, M. and Pavone, M.},
      title = {Optimized and Trusted Collision Avoidance for Unmanned Aerial Vehicles using Approximate Dynamic Programming},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2016},
      address = {Stockholm, Sweden},
      doi = {10.1109/ICRA.2016.7487280},
      month = may,
      url = {../wp-content/papercite-data/pdf/Sunberg.Pavone.Kochenderfer.ICRA16.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  55. R. Zhang, F. Rossi, and M. Pavone, “Model Predictive Control of Autonomous Mobility-on-Demand Systems,” in Proc. IEEE Conf. on Robotics and Automation, Stockholm, Sweden, 2016.

    Abstract: In this paper we present a model predictive control (MPC) approach to optimize vehicle scheduling and routing in an autonomous mobility-on-demand (AMoD) system. In AMoD systems, robotic, self-driving vehicles transport customers within an urban environment and are coordinated to optimize service throughout the entire network. Specifically, we first propose a novel discrete-time model of an AMoD system and we show that this formulation allows the easy integration of a number of real-world constraints, e.g., electric vehicle charging constraints. Second, leveraging our model, we design a model predictive control algorithm for the optimal coordination of an AMoD system and prove its stability in the sense of Lyapunov. At each optimization step, the vehicle scheduling and routing problem is solved as a mixed integer linear program (MILP) where the decision variables are binary variables representing whether a vehicle will 1) wait at a station, 2) service a customer, or 3) rebalance to another station. Finally, by using real-world data, we show that the MPC algorithm can be run in real-time for moderately-sized systems and outperforms previous control strategies for AMoD systems.

    @inproceedings{ZhangRossiEtAl2016b,
      author = {Zhang, R. and Rossi, F. and Pavone, M.},
      title = {Model Predictive Control of {Autonomous} {Mobility-on-Demand} Systems},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2016},
      address = {Stockholm, Sweden},
      doi = {10.1109/ICRA.2016.7487272},
      month = may,
      url = {http://arxiv.org/pdf/1509.03985.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  56. R. Zhang, F. Rossi, and M. Pavone, “Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms,” in Robotics: Science and Systems, 2016.

    Abstract: This paper considers the problem of routing and rebalancing a shared fleet of autonomous (i.e., self-driving) vehicles providing on-demand mobility within a capacitated transportation network, where congestion might disrupt throughput. We model the problem within a network flow framework and show that under relatively mild assumptions the rebalancing vehicles, if properly coordinated, do not lead to an increase in congestion (in stark contrast to common belief). From an algorithmic standpoint, such theoretical insight suggests that the problem of routing customers and rebalancing vehicles can be decoupled, which leads to a computationally-efficient routing and rebalancing algorithm for the autonomous vehicles. Numerical experiments and case studies corroborate our theoretical insights and show that the proposed algorithm outperforms state-of-the-art point-to-point methods by avoiding excess congestion on the road. Collectively, this paper provides a rigorous approach to the problem of congestion-aware, system-wide coordination of autonomously driving vehicles, and to the characterization of the sustainability of such robotic systems.

    @inproceedings{ZhangRossiEtAl2016,
      author = {Zhang, R. and Rossi, F. and Pavone, M.},
      title = {Routing Autonomous Vehicles in Congested Transportation Networks: Structural Properties and Coordination Algorithms},
      booktitle = {{Robotics: Science and Systems}},
      year = {2016},
      doi = {10.15607/rss.2016.xii.032},
      month = jul,
      url = {http://arxiv.org/pdf/1603.00939.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  57. S. Carpin, Y. Chow, and M. Pavone, “Risk Aversion in Finite Markov Decision Processes Using Total Cost Criteria and Average Value at Risk,” in Proc. IEEE Conf. on Robotics and Automation, Stockholm, Sweden, 2016.

    Abstract: In this paper we present an algorithm to compute risk averse policies in Markov Decision Processes (MDP) when the total cost criterion is used together with the average value at risk (AVaR) metric. Risk averse policies are needed when large deviations from the expected behavior may have detrimental effects, and conventional MDP algorithms usually ignore this aspect. We provide conditions for the structure of the underlying MDP ensuring that approximations for the exact problem can be derived and solved efficiently. Our findings are novel inasmuch as average value at risk has not previously been considered in association with the total cost criterion. Our method is demonstrated in a rapid deployment scenario, whereby a robot is tasked with the objective of reaching a target location within a temporal deadline where increased speed is associated with increased probability of failure. We demonstrate that the proposed algorithm not only produces a risk averse policy reducing the probability of exceeding the expected temporal deadline, but also provides the statistical distribution of costs, thus offering a valuable analysis tool.

    @inproceedings{CarpinChowEtAl2016,
      author = {Carpin, S. and Chow, Y. and Pavone, M.},
      title = {Risk Aversion in Finite {Markov} {Decision} {Processes} Using Total Cost Criteria and Average Value at Risk},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2016},
      address = {Stockholm, Sweden},
      doi = {10.1109/ICRA.2016.7487152},
      month = may,
      url = {../wp-content/papercite-data/pdf/Carpin.Chow.Pavone.ICRA16.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  58. R. Iglesias, F. Rossi, R. Zhang, and M. Pavone, “A BCMP Network Approach to Modeling and Controlling Autonomous Mobility-on-Demand Systems,” in Workshop on Algorithmic Foundations of Robotics, San Francisco, California, 2016.

    Abstract: In this paper, we present a queueing network approach to the problem of routing and rebalancing a fleet of self-driving vehicles providing on-demand mobility within a capacitated road network. We refer to such systems as autonomous mobility-on-demand systems, or AMoD. We first cast an AMoD system into a closed, multi-class BCMP queueing network model. Second, we present analysis tools that allow the characterization of performance metrics for a given routing policy, in terms, e.g., of vehicle availabilities and second-order moments of vehicle throughput. Third, we propose a scalable method for the synthesis of routing policies, with performance guarantees in the limit of large fleet sizes. Finally, we validate our theoretical results on a case study of New York City. Collectively, this paper provides a unifying framework for the analysis and control of AMoD systems, which subsumes earlier Jackson and flow network models, provides a quite large set of modeling options (e.g., the inclusion of road capacities and general travel time distributions), and allows the analysis of second and higher-order moments for the performance metrics.

    @inproceedings{IglesiasRossiEtAl2016,
      author = {Iglesias, R. and Rossi, F. and Zhang, R. and Pavone, M.},
      title = {A {BCMP} Network Approach to Modeling and Controlling {Autonomous} {Mobility-on-Demand} Systems},
      booktitle = {{Workshop on Algorithmic Foundations of Robotics}},
      year = {2016},
      address = {San Francisco, California},
      url = {../wp-content/papercite-data/pdf/Iglesias.Rossi.Zhang.Pavone.WAFR16.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  59. B. Hockman, R. G. Reid, I. A. D. Nesnas, and M. Pavone, “Experimental Methods for Mobility and Surface Operations of Microgravity Robots,” in Int. Symp. on Experimental Robotics, Tokyo, Japan, 2016.

    Abstract: We propose an experimental method for studying mobility and surface operations of microgravity robots on zero-gravity parabolic flights - a test bed traditionally used for experiments requiring strictly zero gravity. By strategically exploiting turbulence-induced gravity fluctuations, our technique enables a new experimental approach for testing surface interactions of robotic systems in micro- to milli-gravity environments. This strategy is used to evaluate the performance of internally-actuated hopping rovers designed for controlled surface mobility on small Solar System bodies. In experiments, these rovers demonstrated a range of maneuvers on various surfaces, including both rigid and granular. Results are compared with analytical predictions and numerical simulations, yielding new insights into the dynamics and control of hopping rovers.

    @inproceedings{HockmanReidEtAl2016,
      author = {Hockman, B. and Reid, R. G. and Nesnas, I. A. D. and Pavone, M.},
      title = {Experimental Methods for Mobility and Surface Operations of Microgravity Robots},
      booktitle = {{Int. Symp. on Experimental Robotics}},
      year = {2016},
      address = {Tokyo, Japan},
      month = oct,
      url = {../wp-content/papercite-data/pdf/Hockman.Reid.ea.ISER16.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  60. S. P. Chinchali, S. C. Livingston, M. Pavone, and J. W. Burdick, “Simultaneous Model Identification and Task Satisfaction in the Presence of Temporal Logic Constraints,” in Proc. IEEE Conf. on Robotics and Automation, Stockholm, Sweden, 2016.

    Abstract: Recent proliferation of cyber-physical systems, ranging from autonomous cars to nuclear hazard inspection robots, has exposed several challenging research problems on automated fault detection and recovery. This paper considers how recently developed formal synthesis and model verification techniques may be used to automatically generate information-seeking trajectories for anomaly detection. In particular, we consider the problem of how a robot could select its actions so as to maximally disambiguate between different model hypotheses that govern the environment it operates in or its interaction with other agents whose prime motivation is a priori unknown. The identification problem is posed as selection of the most likely model from a set of candidates, where each candidate is an adversarial Markov decision process (MDP) together with a linear temporal logic (LTL) formula that constrains robot-environment interaction. An adversarial MDP is an MDP in which transitions depend on both a (controlled) robot action and an (uncontrolled) adversary action. States are labeled, thus allowing interpretation of satisfaction of LTL formulae, which have a special form admitting satisfaction decisions in bounded time. An example where a robotic car must discern whether neighboring vehicles are following its trajectory for a surveillance operation is used to illustrate the problem and demonstrate our approach.

    @inproceedings{ChinchaliLivingstonEtAl2016,
      author = {Chinchali, S. P. and Livingston, S. C. and Pavone, M. and Burdick, J. W.},
      title = {Simultaneous Model Identification and Task Satisfaction in the Presence of Temporal Logic Constraints},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2016},
      address = {Stockholm, Sweden},
      doi = {10.1109/ICRA.2016.7487553},
      month = may,
      url = {../wp-content/papercite-data/pdf/Chinchali.Livingston.ea.ICRA16.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  61. I. B. Flader et al., “Autonomous calibration of MEMS disk resonating gyroscope for improved sensor performance,” in American Control Conference, Boston, Massechusetts, 2016.

    Abstract: This work describes a new method for autonomous mode-matching and quadrature nulling of a Microelectromechanical system (MEMS) wineglass mode gyroscope, utilizing particle swarm optimization. Use of this derivative-free optimization scheme allows for multi-objective optimization of gyroscopic performance parameters. Modal frequency split and both mode shapes’ quadrature and amplitude were optimized through this method. Optimal parameters for frequency split, quadratures, and principle axis amplitudes were found to be 0.71 Hz, 13.9 and 10.5 mV, and 284.6 and 299.6 mV, respectively. Autonomous calibration greatly increased the scale factor of the sensor and enhanced the noise performance to levels typically achieved by diligent hand tuning.

    @inproceedings{FladerAhnEtAl2016,
      author = {Flader, I. B. and Ahn, C. H. and Gerrard, D. D. and Ng, E. J. and Yang, Y. and Hong, V. A. and Pavone, M. and Kenny, T. W.},
      title = {Autonomous calibration of {MEMS} disk resonating gyroscope for improved sensor performance},
      booktitle = {{American Control Conference}},
      year = {2016},
      address = {Boston, Massechusetts},
      doi = {10.1109/ACC.2016.7526579},
      month = jul,
      url = {../wp-content/papercite-data/pdf/Flader.Ahn.Gerrard.etal.ACC16.pdf},
      owner = {bylard},
      timestamp = {2018-04-08}
    }
    
  62. L. Janson, E. Schmerling, and M. Pavone, “Monte Carlo Motion Planning for Robot Trajectory Optimization Under Uncertainty,” in Int. Symp. on Robotics Research, Sestri Levante, Italy, 2015.

    Abstract: This article presents a novel approach, named MCMP (Monte Carlo Motion Planning), to the problem of motion planning under uncertainty, i.e., to the problem of computing a low-cost path that fulfills probabilistic collision avoidance constraints. MCMP estimates the collision probability (CP) of a given path by sampling via Monte Carlo the execution of a reference tracking controller (in this paper we consider LQG). The key algorithmic contribution of this paper is the design of statistical variance-reduction techniques, namely control variates and importance sampling, to make such a sampling procedure amenable to real-time implementation. MCMP applies this CP estimation procedure to motion planning by iteratively (i) computing an (approximately) optimal path for the deterministic version of the problem (here, using the FMT* algorithm), (ii) computing the CP of this path, and (iii) inflating or deflating the obstacles by a common factor depending on whether the CP is higher or lower than a target value. The advantages of MCMP are threefold: (i) asymptotic correctness of CP estimation, as opposed to most current approximations, which, as shown in this paper, can be off by large multiples and hinder the computation of feasible plans; (ii) speed and parallelizability, and (iii) generality, i.e., the approach is applicable to virtually any planning problem provided that a path tracking controller and a notion of distance to obstacles in the configuration space are available. Numerical results illustrate the correctness (in terms of feasibility), efficiency (in terms of path cost), and computational speed of MCMP

    @inproceedings{JansonSchmerlingEtAl2015b,
      author = {Janson, L. and Schmerling, E. and Pavone, M.},
      title = {{Monte} {Carlo} Motion Planning for Robot Trajectory Optimization Under Uncertainty},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2015},
      address = {Sestri Levante, Italy},
      month = sep,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://arxiv.org/pdf/1504.08053.pdf}
    }
    
  63. J. A. Starek, B. W. Barbee, and M. Pavone, “A Sampling-Based Approach to Spacecraft Autonomous Maneuvering with Safety Specifications,” in AAS GN&C Conference, Breckenridge, Colorado, 2015.

    Abstract: This paper presents a method for safe spacecraft autonomous maneuvering that leverages robotic motion planning techniques to spacecraft control. Specifically, the scenario we consider is an in-plane rendezvous of a chaser spacecraft in proximity to a target spacecraft at the origin of the Clohessy-Wiltshire-Hill frame. The trajectory for the chaser spacecraft is generated in a receding-horizon fashion by executing a sampling-based robotic motion planning algorithm named Fast Marching Trees (FMT*), which efficiently grows a tree of trajectories over a set of probabilistically-drawn samples in the state space. To enforce safety, the tree is only grown over actively safe samples, from which there exists a one-burn collision avoidance maneuver that circularizes the spacecraft orbit along a collision-free coasting arc and that can be executed under potential thruster failures. The overall approach establishes a provably-correct framework for the systematic encoding of safety specifications into the spacecraft trajectory generation process and appears promising for real-time implementation on orbit. Simulation results are presented for a two-fault tolerant spacecraft during autonomous approach to a single client in Low Earth Orbit.

    @inproceedings{StarekBarbeeEtAl2015,
      author = {Starek, J. A. and Barbee, B. W. and Pavone, M.},
      title = {A Sampling-Based Approach to Spacecraft Autonomous Maneuvering with Safety Specifications},
      booktitle = {{AAS GN\&C Conference}},
      year = {2015},
      address = {Breckenridge, Colorado},
      month = feb,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Starek.Barbee.ea.AASGNC15.pdf}
    }
    
  64. Z. Zhu, E. Schmerling, and M. Pavone, “A Convex Optimization Approach to Smooth Trajectories for Motion Planning with Car-Like Robots,” in Proc. IEEE Conf. on Decision and Control, Osaka, Japan, 2015.

    Abstract: In the recent past, several sampling-based algorithms have been proposed to compute trajectories that are collision-free and dynamically-feasible. However, the outputs of such algorithms are notoriously jagged. In this paper, by focusing on robots with car-like dynamics, we present a fast and simple heuristic algorithm, named Convex Elastic Smoothing (CES) algorithm, for trajectory smoothing and speed optimization. The CES algorithm is inspired by earlier work on elastic band planning and iteratively performs shape and speed optimization. The key feature of the algorithm is that both optimization problems can be solved via convex programming, making CES particularly fast. A range of numerical experiments show that the CES algorithm returns high-quality solutions in a matter of a few hundreds of milliseconds and hence appears amenable to a real-time implementation.

    @inproceedings{ZhuSchmerlingEtAl2015,
      author = {Zhu, Z. and Schmerling, E. and Pavone, M.},
      title = {A Convex Optimization Approach to Smooth Trajectories for Motion Planning with Car-Like Robots},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2015},
      address = {Osaka, Japan},
      doi = {10.1109/CDC.2015.7402333},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://arxiv.org/pdf/1506.01085.pdf}
    }
    
  65. L. Janson, B. Ichter, and M. Pavone, “Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance,” in Int. Symp. on Robotics Research, Sestri Levante, Italy, 2015.

    Abstract: Probabilistic sampling-based algorithms, such as the probabilistic roadmap (PRM) and the rapidly-exploring random tree (RRT) algorithms, represent one of the most successful approaches to robotic motion planning, due to their strong theoretical properties (in terms of probabilistic completeness or even asymptotic optimality) and remarkable practical performance. Such algorithms are probabilistic in that they compute a path by connecting independently and identically distributed (i.i.d.) random points in the configuration space. Their randomization aspect, however, makes several tasks challenging, including certification for safety-critical applications and use of offline computation to improve real-time execution. Hence, an important open question is whether similar (or better) theoretical guarantees and practical performance could be obtained by considering deterministic, as opposed to random sampling sequences. The objective of this paper is to provide a rigorous answer to this question. The focus is on the PRM algorithm—our results, however, generalize to other batch-processing algorithms such as FMT∗. Specifically, we first show that PRM, for a certain selection of tuning parameters and deterministic low-dispersion sampling sequences, is deterministically asymptotically optimal,i.e., it returns a path whose cost converges deterministically to the optimal one as the number of points goes to infinity. Second, we characterize the convergence rate, and we find that the factor of sub-optimality can be very explicitly upper-bounded in terms of the ‘2-dispersion of the sampling sequence and the connection radius of PRM. Third, we show that an asymptotically optimal version of PRM exists with computational and space complexity arbitrarily close to O(n) (the theoretical lower bound), where n is the number of points in the sequence. This is in stark contrast to the O(n logn) complexity results for existing asymptotically-optimal probabilistic planners. Finally, through numerical experiments, we show that planning with deterministic low-dispersion sampling generally provides superior performance in terms of path cost and success rate

    @inproceedings{JansonIchterEtAl2015b,
      author = {Janson, L. and Ichter, B. and Pavone, M.},
      title = {Deterministic Sampling-Based Motion Planning: Optimality, Complexity, and Performance},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2015},
      address = {Sestri Levante, Italy},
      month = sep,
      url = {http://arxiv.org/pdf/1505.00023.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  66. S. Singh, E. Schmerling, and M. Pavone, “Decentralized Algorithms for 3D Symmetric Formations in Robotic Networks - A Contraction Theory Approach,” in Proc. IEEE Conf. on Robotics and Automation, Seattle, Washington, 2015.

    Abstract: This paper presents distributed algorithms for formation control of multiple robots in three dimensions. In particular, we leverage the mathematical properties of cyclic pursuit along with results from contraction and partial contraction theory to design distributed control algorithms ensuring global convergence to symmetric formations. As a base case we consider regular polygons as desired formations and then provide extensions to Johnson solid formations. Finally, we analyze the robustness of the control algorithms under bounded additive disturbances and provide performance bounds with respect to the formation error.

    @inproceedings{SinghSchmerlingEtAl2015,
      author = {Singh, S. and Schmerling, E. and Pavone, M.},
      title = {Decentralized Algorithms for {3D} Symmetric Formations in Robotic Networks - A Contraction Theory Approach},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2015},
      address = {Seattle, Washington},
      doi = {10.1109/ICRA.2015.7139355},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Singh.Pavone.ICRA2015.pdf}
    }
    
  67. S. Singh, S. D’Amico, and M. Pavone, “High-Fidelity Modeling and Control System Synthesis for a Drag-Free Microsatellite,” in Int. Symp. on Space Flight Dynamics, Munich, Germany, 2015.

    Abstract: A drag-free satellite is a spacecaft composed of an internal test mass shielded by an external satellite that compensates all dominant disturbance forces encountered in the space environment such as aerodynamic drag and solar radiation pressure. By minimizing all non-gravitational disturbances on the test mass, the trajectory of the spacecraft is a near perfect geodesic. In concert with precise orbit determination techniques, drag-free satellites allow us to investigate topics in geodesy, aeronomy, and gravitational physics and conduct challenging experiments in low-disturbance environments to unprecedented accuracy. This paper addresses the development of a high-fidelity simulator and control system design for the Modular Gravitational Reference Sensor (MGRS) drag-free satellite. MGRS is a 100 kg microsatellite due to launch in 2018 into a Sun-synchronous orbit with a mean altitude of 657 km that aims to demonstrate three-axis drag-free operations with residual non-gravitational acceleration of a test mass under 10^-12 \msrootHz in the frequency range 0.01 to 1 Hz. The drag-free performance goal reflects a substantial improvement upon past drag-free missions such as TRIAD I, GPB, and GOCE, and will be accomplished at a fraction of the cost. Additionally, this mission represents a key technology demonstration within a larger research endeavour that aims to develop a multi-purpose distributed drag-free architecture based on microsatellite platforms. Our modeling framework allows us to gain a comprehensive insight into the range of expected disturbances, derive sizing constraints for a suitable micropropulsion system, and formulate a preliminary drag-free translational and attitude control system using H_∞- control techniques.

    @inproceedings{SinghDAmicoEtAl2015,
      author = {Singh, S. and D'Amico, S.. and Pavone, M.},
      title = {High-Fidelity Modeling and Control System Synthesis for a Drag-Free Microsatellite},
      booktitle = {{Int. Symp. on Space Flight Dynamics}},
      year = {2015},
      address = {Munich, Germany},
      month = oct,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Singh.Damico.Pavone.ISSFD15.pdf}
    }
    
  68. E. Schmerling, L. Janson, and M. Pavone, “Optimal Sampling-Based Motion Planning under Differential Constraints: the Drift Case with Linear Affine Dynamics,” in Proc. IEEE Conf. on Decision and Control, Osaka, Japan, 2015.

    Abstract: In this paper we provide a thorough, rigorous theoretical framework to assess optimality guarantees of samplingbased algorithms for drift control systems: systems that, loosely speaking, can not stop instantaneously due to momentum. We exploit this framework to design and analyze a sampling-based algorithm (the Differential Fast Marching Tree algorithm) that is asymptotically optimal, that is, it is guaranteed to converge, as the number of samples increases, to an optimal solution. In addition, our approach allows us to provide concrete bounds on the rate of this convergence. The focus of this paper is on mixed time/control energy cost functions and on linear affine dynamical systems, which encompass a range of models of interest to applications (e.g., double-integrators) and represent a necessary step to design, via successive linearization, samplingbased and provably-correct algorithms for non-linear drift control systems. Our analysis relies on an original perturbation analysis for two-point boundary value problems, which could be of independent interest.

    @inproceedings{SchmerlingJansonEtAl2015b,
      author = {Schmerling, E. and Janson, L. and Pavone, M.},
      title = {Optimal Sampling-Based Motion Planning under Differential Constraints: the Drift Case with Linear Affine Dynamics},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2015},
      address = {Osaka, Japan},
      doi = {10.1109/CDC.2015.7402604},
      month = dec,
      url = {http://arxiv.org/pdf/1405.7421.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  69. E. Schmerling, L. Janson, and M. Pavone, “Optimal Sampling-Based Motion Planning under Differential Constraints: the Driftless Case,” in Proc. IEEE Conf. on Robotics and Automation, Seattle, Washington, 2015.

    Abstract: Motion planning under differential constraints is a classic problem in robotics. To date, the state of the art is represented by sampling-based techniques, with the Rapidly-exploring Random Tree algorithm as a leading example. Yet, the problem is still open in many aspects, including guarantees on the quality of the obtained solution. In this paper we provide a thorough theoretical framework to assess optimality guarantees of sampling-based algorithms for planning under differential constraints. We exploit this framework to design and analyze two novel sampling-based algorithms that are guaranteed to converge, as the number of samples increases, to an optimal solution (namely, the Differential Probabilistic RoadMap algorithm and the Differential Fast Marching Tree algorithm). Our focus is on driftless control-affine dynamical models, which accurately model a large class of robotic systems. In this paper we use the notion of convergence in probability (as opposed to convergence almost surely): the extra mathematical flexibility of this approach yields convergence rate bounds - a first in the field of optimal sampling-based motion planning under differential constraints. Numerical experiments corroborating our theoretical results are presented and discussed.

    @inproceedings{SchmerlingJansonEtAl2015,
      author = {Schmerling, E. and Janson, L. and Pavone, M.},
      title = {Optimal Sampling-Based Motion Planning under Differential Constraints: the Driftless Case},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2015},
      note = {{Extended version available at }\url{http://arxiv.org/abs/1403.2483/}},
      address = {Seattle, Washington},
      doi = {10.1109/ICRA.2015.7139514},
      month = may,
      url = {http://arxiv.org/pdf/1403.2483.pdf},
      owner = {bylard},
      timestamp = {2018-06-30}
    }
    
  70. R. Zhang, K. Spieser, E. Frazzoli, and M. Pavone, “Models, Algorithms and Evaluation for Autonomous Mobility-on-Demand Systems,” in American Control Conference, Chicago, Illinois, 2015.

    Abstract: This tutorial paper examines the operational and economic aspects of autonomous mobility-on-demand (AMoD) systems, a rapidly emerging mode of personal transportation wherein robotic, self-driving vehicles transport customers in a given environment. We address AMoD systems along three dimensions: (1) modeling - analytical models capable of capturing the salient dynamic and stochastic features of customer demand, (2) control - coordination algorithms for the vehicles aimed at stability and subsequently throughput maximization, and (3) economic - fleet sizing and financial analyses for case studies of New York City and Singapore. Collectively, the models and algorithms presented in this paper enable a rigorous assessment of the value of AMoD systems. In particular, the case study of New York City shows that the current taxi demand in Manhattan can be met with about 8,000 robotic vehicles (roughly 70% of the size of the current taxi fleet), while the case study of Singapore suggests that an AMoD system can meet the personal mobility need of the entire population of Singapore with a number of robotic vehicles that is less than 40% of the current number of passenger vehicles. Directions for future research on AMoD systems are presented and discussed.

    @inproceedings{ZhangSpieserEtAl2015,
      author = {Zhang, R. and Spieser, K. and Frazzoli, E. and Pavone, M.},
      title = {Models, Algorithms and Evaluation for {Autonomous} {Mobility-on-Demand} Systems},
      booktitle = {{American Control Conference}},
      year = {2015},
      address = {Chicago, Illinois},
      doi = {10.1109/ACC.2015.7171122},
      month = jul,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.ea.ACC15.pdf}
    }
    
  71. R. Allen and M. Pavone, “Toward A Real-Time Framework for Solving the Kinodynamic Motion Planning Problem,” in Proc. IEEE Conf. on Robotics and Automation, Seattle, Washington, 2015.

    Abstract: n this paper we propose a framework combining techniques from sampling-based motion planning, machine learning, and trajectory optimization to address the kinody- namic motion planning problem in real-time environments. This framework relies on a look-up table that stores precomputed optimal solutions to boundary value problems (assuming no obstacles), which form the directed edges of a precomputed motion planning roadmap. A sampling-based motion planning algorithm then leverages such a precomputed roadmap to compute online an obstacle-free trajectory. Machine learning techniques are employed to minimize the number of online solutions to boundary value problems required to compute the neighborhoods of the start state and goal regions. This approach is demonstrated to reduce online planning times up to six orders of magnitude. Simulation results are presented and discussed. Problem-specific framework modifications are then discussed that would allow further computation time reductions.

    @inproceedings{AllenPavone2015,
      author = {Allen, R. and Pavone, M.},
      title = {Toward A Real-Time Framework for Solving the Kinodynamic Motion Planning Problem},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2015},
      address = {Seattle, Washington},
      doi = {10.1109/ICRA.2015.7139288},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Allen.Pavone.ICRA15.pdf}
    }
    
  72. R. Zhang and M. Pavone, “A Queueing Network Approach to the Analysis and Control of Mobility-on-Demand Systems,” in American Control Conference, Chicago, Illinois, 2015.

    Abstract: This paper presents a queueing network approach to the analysis and control of mobility-on-demand (MoD) systems for urban personal transportation. A MoD system consists of a fleet of vehicles providing one-way car sharing service and a team of drivers to rebalance such vehicles. The drivers then rebalance themselves by driving select customers similar to a taxi service. We model the MoD system as two coupled closed Jackson networks with passenger loss. We show that the system can be approximately balanced by solving two decoupled linear programs and exactly balanced through nonlinear optimization. The rebalancing techniques are applied to a system sizing example using taxi data in three neighborhoods of Manhattan, which suggests that the optimal vehicle-to-driver ratio in a MoD system is between 3 and 5. Lastly, we formulate a real-time closed-loop rebalancing policy for drivers and demonstrate its stability (in terms of customer wait times) for typical system loads.

    @inproceedings{ZhangPavone2015,
      author = {Zhang, R. and Pavone, M.},
      title = {A Queueing Network Approach to the Analysis and Control of {Mobility-on-Demand} Systems},
      booktitle = {{American Control Conference}},
      year = {2015},
      address = {Chicago, Illinois},
      doi = {10.1109/ACC.2015.7172070},
      month = jul,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://arxiv.org/pdf/1409.6775v2.pdf}
    }
    
  73. Y. Chow, A. Tamar, S. Mannor, and M. Pavone, “Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach,” in Conf. on Neural Information Processing Systems, Montreal, Canada, 2015.

    Abstract: In this paper we address the problem of decision making within a Markov decision process (MDP) framework where risk and modeling errors are taken into account. Our approach is to minimize a risk-sensitive conditional-value-at-risk (CVaR) objective, as opposed to a standard risk-neutral expectation. We refer to such problem as CVaR MDP. Our first contribution is to show that a CVaR objective, besides capturing risk sensitivity, has an alternative interpretation as expected cost under worst-case modeling errors, for a given error budget. This result, which is of independent interest, motivates CVaR MDPs as a unifying framework for risk-sensitive and robust decision making. Our second contribution is to present a value-iteration algorithm for CVaR MDPs, and analyze its convergence rate. To our knowledge, this is the first solution algorithm for CVaR MDPs that enjoys error guarantees. Finally, we present results from numerical experiments that corroborate our theoretical findings and show the practicality of our approach.

    @inproceedings{ChowTamarEtAl2015,
      author = {Chow, Y. and Tamar, A. and Mannor, S. and Pavone, M.},
      title = {Risk-Sensitive and Robust Decision-Making: a {CVaR} Optimization Approach},
      booktitle = {{Conf. on Neural Information Processing Systems}},
      year = {2015},
      address = {Montreal, Canada},
      url = {../wp-content/papercite-data/pdf/Chow.Tamar.Mannor.Pavone.NIPS15.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  74. B. Hockman, A. Frick, I. A. D. Nesnas, and M. Pavone, “Design, Control, and Experimentation of Internally-Actuated Rovers for the Exploration of Low-Gravity Planetary Bodies,” in Field and Service Robotics, Toronto, Canada, 2015.

    Abstract: In this paper we discuss the design, control, and experimentation of internally-actuated rovers for the exploration of low-gravity (micro-g to milli-g) planetary bodies, such as asteroids, comets, or small moons. The actuation of the rover relies on spinning three internal flywheels, which allows all subsystems to be packaged in one sealed enclosure and enables the platform to be minimalistic, thereby reducing its cost. By controlling flywheels’ spin rate, the rover is capable of achieving large surface coverage by attitude-controlled hops, fine mobility by tumbling, and coarse instrument pointing by changing orientation relative to the ground. We discuss the dynamics of such rovers, their control, and key design features (e.g., flywheel design and orientation, geometry of external spikes, and system engineering aspects). The theoretical analysis is validated on a first-of-a-kind 6 degree-of-freedom (DoF) microgravity test bed, which consists of a 3 DoF gimbal attached to an actively controlled gantry crane.

    @inproceedings{HockmanFrickEtAl2015,
      author = {Hockman, B. and Frick, A. and Nesnas, I. A. D. and Pavone, M.},
      title = {Design, Control, and Experimentation of Internally-Actuated Rovers for the Exploration of Low-Gravity Planetary Bodies},
      booktitle = {{Field and Service Robotics}},
      year = {2015},
      address = {Toronto, Canada},
      doi = {10.1007/978-3-319-27702-8_19},
      url = {../wp-content/papercite-data/pdf/Hockman.Pavone.ea.FSR15.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  75. J. A. Starek, J. V. Gomez, E. Schmerling, L. Janson, L. Moreno, and M. Pavone, “An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Hamburg, Germany, 2015.

    Abstract: Bi-directional search is a widely used strategy to increase the success and convergence rates of sampling-based motion planning algorithms. Yet, few results are available that merge both bi-directional search and asymptotic optimality into existing optimal planners, such as PRM*, RRT*, and FMT*. The objective of this paper is to fill this gap. Specifically, this paper presents a bi-directional, sampling-based, asymptotically-optimal algorithm named Bi-directional FMT* (BFMT*) that extends the Fast Marching Tree (FMT*) algorithm to bidirectional search while preserving its key properties, chiefly lazy search and asymptotic optimality through convergence in probability. BFMT* performs a two-source, lazy dynamic programming recursion over a set of randomly-drawn samples, correspondingly generating two search trees: one in cost-to-come space from the initial configuration and another in cost-to-go space from the goal configuration. Numerical experiments illustrate the advantages of BFMT* over its unidirectional counterpart, as well as a number of other state-of-the-art planners.

    @inproceedings{StarekGomezEtAl2015,
      author = {Starek, J. A. and Gomez, J. V. and Schmerling, E. and Janson, L. and Moreno, L. and Pavone, M.},
      title = {An Asymptotically-Optimal Sampling-Based Algorithm for Bi-directional Motion Planning},
      booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}},
      year = {2015},
      address = {Hamburg, Germany},
      doi = {10.1109/IROS.2015.7353652},
      month = sep,
      url = {../wp-content/papercite-data/pdf/Starek.Gomez.ea.IROS15.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  76. Y. Chow and M. Pavone, “A Framework for Time-Consistent, Risk-Averse Model Predictive Control: Theory and Algorithms,” in American Control Conference, Portland, Oregon, 2014.

    Abstract: In this paper we present a framework for risk-averse model predictive control (MPC) of linear systems affected by multiplicative uncertainty. Our key innovation is to consider time-consistent, dynamic risk metrics as objective functions to be minimized. This framework is axiomatically justified in terms of time-consistency of risk preferences, is amenable to dynamic optimization, and is unifying in the sense that it captures a full range of risk assessments from risk-neutral to worst case. Within this framework, we propose and analyze an online risk-averse MPC algorithm that is provably stabilizing. Furthermore, by exploiting the dual representation of time-consistent, dynamic risk metrics, we cast the computation of the MPC control law as a convex optimization problem amenable to implementation on embedded systems. Simulation results are presented and discussed.

    @inproceedings{ChowPavone2014,
      author = {Chow, Y. and Pavone, M.},
      title = {A Framework for Time-Consistent, Risk-Averse Model Predictive Control: Theory and Algorithms},
      booktitle = {{American Control Conference}},
      year = {2014},
      address = {Portland, Oregon},
      doi = {10.1109/ACC.2014.6859437},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Chow.Pavone.ACC14.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  77. R. Allen, A. Clark, J. A. Starek, and M. Pavone, “A Machine Learning Approach for Real-time Computation of Dynamical System Reachability Sets,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Chicago, Illinois, 2014.

    Abstract: Assessing reachability for a dynamical system, that is deciding whether a certain state is reachable from a given initial state within a given cost threshold, is a central concept in controls, robotics, and optimization. Direct approaches to assess reachability involve the solution to a two-point boundary value problem (2PBVP) between a pair of states. Alternative, indirect approaches involve the characterization of reachable sets as level sets of the value function of an appropriate optimal control problem. Both methods solve the problem accurately, but are computationally intensive and do no appear amenable to real-time implementation for all but the simplest cases. In this work, we leverage machine learning techniques to devise query-based algorithms for the approximate, yet real-time solution of the reachability problem. Specifically, we show that with a training set of pre-solved 2PBVP problems, one can accurately classify the cost-reachable sets of a differentially-constrained system using either (1) locally-weighted linear regression or (2) support vector machines. This novel, query-based approach is demonstrated on two systems: the Dubins car and a deep-space spacecraft. Classification errors on the order of 10% (and often significantly less) are achieved with average execution times on the order of milliseconds, representing 4 orders-of-magnitude improvement over exact methods. The proposed algorithms could find application in a variety of time-critical robotic applications, where the driving factor is computation time rather than optimality.

    @inproceedings{AllenClarkEtAl2014,
      author = {Allen, R. and Clark, A. and Starek, J. A. and Pavone, M.},
      title = {A Machine Learning Approach for Real-time Computation of Dynamical System Reachability Sets},
      booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}},
      year = {2014},
      address = {Chicago, Illinois},
      doi = {10.1109/IROS.2014.6942859},
      month = sep,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Allen.Clark.Starek.ea.IROS2014.pdf}
    }
    
  78. R. Zhang and M. Pavone, “Control of Robotic Mobility-on-Demand Systems: a Queueing-Theoretical Perspective,” in Robotics: Science and Systems, Berkeley, California, 2014.

    Abstract: In this paper we present and analyze a queueing-theoretical model for autonomous mobility-on-demand (MOD) systems where robotic, self-driving vehicles transport customers within an urban environment and rebalance themselves to ensure acceptable quality of service throughout the entire network. We cast an autonomous MOD system within a closed Jackson network model with passenger loss. It is shown that an optimal rebalancing algorithm minimizing the number of (autonomously) rebalancing vehicles and keeping vehicles availabilities balanced throughout the network can be found by solving a linear program. The theoretical insights are used to design a robust, real-time rebalancing algorithm, which is applied to a case study of New York City. The case study shows that the current taxi demand in Manhattan can be met with about 8,000 robotic vehicles (roughly 70% of the size of the current taxi fleet operating in Manhattan). Finally, we extend our queueing-theoretical setup to include congestion effects, and we study the impact of autonomously rebalancing vehicles on overall congestion. Collectively, this paper provides a rigorous approach to the problem of system-wide coordination of autonomously driving vehicles, and provides one of the first characterizations of the sustainability benefits of robotic transportation networks.

    @inproceedings{ZhangPavone2014,
      author = {Zhang, R. and Pavone, M.},
      title = {Control of Robotic {Mobility-on-Demand} Systems: a Queueing-Theoretical Perspective},
      booktitle = {{Robotics: Science and Systems}},
      year = {2014},
      note = {Best Paper Award Finalist},
      address = {Berkeley, California},
      doi = {10.15607/rss.2014.x.026},
      month = jul,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {http://web.stanford.edu/~pavone/papers/Zhang.Pavone.RSS14.pdf}
    }
    
  79. F. Rossi and M. Pavone, “Distributed Consensus with Mixed Time/Communication Bandwidth Performance Metrics,” in Allerton Conf. on Communications, Control and Computing, Champaign, Illinois, 2014.

    Abstract: In this paper we study the inherent trade-off between time and communication complexity for the distributed consensus problem. In our model, communication complexity is measured as the maximum data throughput (in bits per second) sent through the network at a given instant. Such a notion of communication complexity, referred to as bandwidth complexity, is related to the frequency bandwidth a designer should collectively allocate to the agents if they were to communicate via a wireless channel, which represents an important constraint for dense robotic networks. We prove a lower bound on the bandwidth complexity of the consensus problem and provide a consensus algorithm that is bandwidth-optimal for a wide class of consensus functions. We then propose a distributed algorithm that can trade communication complexity versus time complexity as a function of a tunable parameter, which can be adjusted by a system designer as a function of the properties of the wireless communication channel. We rigorously characterize the tunable algorithm’s worst-case bandwidth complexity and show that it compares favorably with the bandwidth complexity of well-known consensus algorithm.

    @inproceedings{RossiPavone2014b,
      author = {Rossi, F. and Pavone, M.},
      title = {Distributed Consensus with Mixed Time/Communication Bandwidth Performance Metrics},
      booktitle = {{Allerton Conf. on Communications, Control and Computing}},
      year = {2014},
      address = {Champaign, Illinois},
      doi = {10.1109/ALLERTON.2014.7028468},
      url = {http://arxiv.org/pdf/1410.0956.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  80. F. Rossi and M. Pavone, “On the Fundamental Limitations of Performance for Distributed Decision-Making in Robotic Networks,” in Proc. IEEE Conf. on Decision and Control, Los Angeles, California, 2014.

    Abstract: This paper studies fundamental limitations of performance for distributed decision-making in robotic networks. The class of decision-making problems we consider encompasses a number of prototypical problems such as average-based consensus as well as distributed optimization, leader election, majority voting, MAX, MIN, and logical formulas. We first propose a formal model for distributed computation on robotic networks that is based on the concept of I/O automata and is inspired by the Computer Science literature on distributed computing clusters. Then, we present a number of bounds on time, message, and byte complexity, which we use to discuss the relative performance of a number of approaches for distributed decision-making. From a methodological standpoint, our work sheds light on the relation between the tools developed by the Computer Science and Controls communities on the topic of distributed algorithms.

    @inproceedings{RossiPavone2014,
      author = {Rossi, F. and Pavone, M.},
      title = {On the Fundamental Limitations of Performance for Distributed Decision-Making in Robotic Networks},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2014},
      address = {Los Angeles, California},
      doi = {10.1109/CDC.2014.7039760},
      month = dec,
      url = {http://arxiv.org/pdf/1409.4863.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  81. R. G. Reid, L. Roveda, I. A. D. Nesnas, and M. Pavone, “Contact Dynamics of Internally-Actuated Platforms for the Exploration of Small Solar System Bodies,” in Int. Symp. on Artificial Intelligence, Robotics and Automation in Space, Montréal, Quebec, 2014.

    Abstract: Directed in-situ science and exploration on the surface of small Solar System bodies requires controlled mobility. In the microgravity environment of small bodies such as asteroids, comets or small moons, the low gravitational and frictional forces at the surface make typical wheeled rovers ineffective. Through a joint collaboration, the Jet Propulsion Laboratory together with Stanford University have been studying microgravity mobility approaches using hopping/tumbling platforms. They have developed an internally-actuated spacecraft/rover hybrid platform, known as "Hedgehog", that uses flywheels and brakes to impart mobility. This paper presents a model of the platform’s mobility, analyzing its three main states of motion (pivoting, slipping and hopping) and the contact dynamics between the platform’s spikes and various regolith simulants. To experimentally validate the model, an Atwood machine (pulley and counterbalance) was used to emulate microgravity. Experiments were performed with a range of torques on both rigid and granular surfaces while a high-speed camera tracked the platform’s motion. Using parameters measured during the experiments, the platform was simulated numerically and its motion compared. Within the limits of the experimental setup, the model is consistent with observations; it indicates the ability to perform controlled forward motions in microgravity on a range of rigid and granular regolith simulants.

    @inproceedings{ReidRovedaEtAl2014,
      author = {Reid, R. G. and Roveda, L. and Nesnas, I. A. D. and Pavone, M.},
      title = {Contact Dynamics of Internally-Actuated Platforms for the Exploration of Small {Solar} {System} Bodies},
      booktitle = {{Int. Symp. on Artificial Intelligence, Robotics and Automation in Space}},
      year = {2014},
      address = {Montr\'{e}al, Quebec},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Reid.Roveda.ea.iSAIRAS14.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  82. S. Carpin, M. Pavone, and B. M. Sadler, “Rapid Multirobot Deployment with Time Constraints,” in IEEE/RSJ Int. Conf. on Intelligent Robots & Systems, Chicago, Illinois, 2014.

    Abstract: In this paper we consider the problem of multirobot deployment under temporal deadlines. The objective is to compute strategies trading off safety for speed to maximize the probability of reaching a given set of target locations within a pre-assigned temporal deadline. We formulate this problem using the theory of Constrained Markov Decision Processes and we show that thanks to this framework it is possible to determine deploying strategies maximizing the probability of success while satisfying the deadline. Moreover, the formulation allows to exactly compute the failure probability of complex deployment tasks. Simulation results illustrate how the proposed method works in different scenarios and show how informed decisions can be made regarding the size of the robot team.

    @inproceedings{CarpinPavoneEtAl2014,
      author = {Carpin, S. and Pavone, M. and Sadler, B. M.},
      title = {Rapid Multirobot Deployment with Time Constraints},
      booktitle = {{IEEE/RSJ Int. Conf. on Intelligent Robots \& Systems}},
      year = {2014},
      address = {Chicago, Illinois},
      doi = {10.1109/IROS.2014.6942702},
      month = sep,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Carpin.Pavone.ea.IROS14.pdf}
    }
    
  83. A. W. Koenig, M. Pavone, J. C. Castillo-Rogez, and I. A. D. Nesnas, “A Dynamical Characterization of Internally-Actuated Microgravity Mobility Systems,” in Proc. IEEE Conf. on Robotics and Automation, Hong Kong, 2014.

    Abstract: The in-situ exploration of small Solar System bodies (such as asteroids or comets) is becoming a central objective for future planetary exploration. Such bodies are characterized by very weak gravitational fields, which make hopping mobility platforms one of the preferred mobility strategies for microgravity surface exploration, as recognized by space agencies worldwide. However, little is known about the dynamical behavior of hopping platforms in low gravity environments, where small bodies’ rotational dynamics can have a critical effect. Accordingly, the objective of this paper is to study in detail the dynamic envelope of hopping microgravity rovers, with a focus on internal actuation. Specifically, we first perform a static analysis with the goal of determining regions of a small body where an internally-actuated hopping rover can stably remain at rest. Then, we perform a dynamic analysis and discuss the actuation and instrument pointing performance of hopping microgravity platforms as a function of a number of system and environmental parameters (e.g., rover shape, body rotation rate). Finally, we tailor our analysis to a potential mission to Mars’ moon Phobos. Collectively, our results show that internally-actuated rovers, from an actuation standpoint, are a viable mobility solution for a vast class of small Solar System bodies. Also, our analysis represents a key first step to develop path planning algorithms for microgravity explorers to safely explore dynamically feasible regions.

    @inproceedings{KoenigPavoneEtAl2014,
      author = {Koenig, Adam W. and Pavone, M. and Castillo-Rogez, Julie C. and Nesnas, I. A. D.},
      title = {A Dynamical Characterization of Internally-Actuated Microgravity Mobility Systems},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2014},
      address = {Hong Kong},
      doi = {10.1109/ICRA.2014.6907836},
      month = may,
      url = {../wp-content/papercite-data/pdf/Koenig.Pavone.ea.ICRA14.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  84. M. Pavone, J. Castillo, I. Nesnas, J. A. Hoffman, and N. Strange, “Spacecraft/Rover Hybrids for the Exploration of Small Solar System Bodies,” in IEEE Aerospace Conference, Big Sky, Montana, 2013.

    Abstract: In this paper we present a mission architecture for the systematic and affordable in-situ exploration of small Solar System bodies (such as asteroids, comets, and Martian moons). At a general level, a mother spacecraft would deploy on the surface of a small body one, or several, spacecraft/rover hybrids, which are small (<= 5 kg,  15 Watts), multi-faceted robots enclosing three mutually orthogonal flywheels and surrounded by external spikes (in particular, there is no external propulsion). By accelerating/decelerating the flywheels and by exploiting the low gravity environment, the hybrids would be capable of performing both long excursions (by hopping) and short traverses to specific locations (through a sequence of controlled "tumbles"). Their control would rely on synergistic operations with the mother spacecraft (where most of hybrids perception and localization functionalities would be hosted), which would make the platforms minimalistic and in turn the entire mission architecture affordable. Specifically, in the first part of the paper we present preliminary models and laboratory experiments for the hybrids, first-order estimates for critical subsystems, and a preliminary study for synergistic mission operations. In the second part, we tailor our mission architecture to the exploration of Mars’ moon Phobos. The mission aims at exploring Phobos’ Stickney crater, whose spectral similarities with C-type asteroids and variety of terrain properties make it a particularly interesting exploration target to address both high-priority science for the Martian system and strategic knowledge gaps for the future human exploration of Mars.

    @inproceedings{PavoneCastilloEtAl2013,
      author = {Pavone, M. and Castillo, J. and Nesnas, I. and Hoffman, J. A. and Strange, N.},
      title = {Spacecraft/Rover Hybrids for the Exploration of Small {Solar} {System} Bodies},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2013},
      address = {Big Sky, Montana},
      doi = {10.1109/AERO.2013.6497160},
      month = mar,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Castillo.ea.Aero13.pdf}
    }
    
  85. S. L. Smith, M. Pavone, M. Schwager, E. Frazzoli, and D. Rus, “Rebalancing the Rebalancers: Optimally Routing Vehicles and Drivers in Mobility-on-Demand Systems,” in American Control Conference, Washington, D.C., 2013.

    Abstract: In this paper we study rebalancing strategies for a mobility-on-demand urban transportation system blending customer-driven vehicles with a taxi service. In our system, a customer arrives at one of many designated stations and is transported to any other designated station, either by driving themselves, or by being driven by an employed driver. The system allows for one-way trips, so that customers do not have to return to their origin. When some origins and destinations are more popular than others, vehicles will become unbalanced, accumulating at some stations and becoming depleted at others. This problem is addressed by employing rebalancing drivers to drive vehicles from the popular destinations to the unpopular destinations. However, with this approach the rebalancing drivers themselves become unbalanced, and we need to "rebalance the rebalancers" by letting them travel back to the popular destinations with a customer. Accordingly, in this paper we study how to optimally route the rebalancing vehicles and drivers so that stability (in terms of boundedness of the number of waiting customers) is ensured while minimizing the number of rebalancing vehicles traveling in the network and the number of rebalancing drivers needed; surprisingly, these two objectives are aligned, and one can find the optimal rebalancing strategy by solving two decoupled linear programs. Leveraging our analysis, we determine the minimum number of drivers and minimum number of vehicles needed to ensure stability in the system. Interestingly, our simulations suggest that, in Euclidean network topologies, one would need between 1/3 and 1/4 as many drivers as vehicles.

    @inproceedings{SmithPavoneEtAl2013,
      author = {Smith, S. L. and Pavone, M. and Schwager, M. and Frazzoli, E. and Rus, D.},
      title = {Rebalancing the Rebalancers: Optimally Routing Vehicles and Drivers in {Mobility-on-Demand} Systems},
      booktitle = {{American Control Conference}},
      year = {2013},
      address = {Washington, D.C.},
      doi = {10.1109/ACC.2013.6580187},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Smith.Pavone.ea.ACC13.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  86. F. Rossi and M. Pavone, “Decentralized Decision-Making on Robotic Networks with Hybrid Performance Metrics,” in Allerton Conf. on Communications, Control and Computing, Champaign, Illinois, 2013.

    Abstract: The past decade has witnessed a rapidly growing interest in decentralized algorithms for collective decision-making in cyber-physical networks. For a large variety of settings, control strategies are now known that either minimize time complexity (i.e., convergence time) or optimize communication complexity (i.e., number and size of exchanged messages). Yet, little attention has beed paid to the problem of studying the inherent trade-off between time and communication complexity. Generally speaking, time-optimal algorithms are fast and robust, but require a large (and sometimes impractical) number of exchanged messages; in contrast, communication optimal algorithms minimize the amount of information routed through the network, but are slow and sensitive to link failures. In this paper we address this gap by focusing on a generalized version of the decentralized consensus problem (that includes voting and mediation) on undirected network topologies and in the presence of "infrequent" link failures. We present and rigorously analyze a tunable, semi-hierarchical algorithm, where the tuning parameter allows a graceful transition from time-optimal to communication-optimal performance (hence, allowing hybrid performance metrics), and determines the algorithm’s robustness, measured as the time required to recover from a failure. An interesting feature of our algorithm is that it leads the decision-making agents to self-organize into a semi-hierarchical structure with variable-size clusters, among which information is flooded. Our results make use of a novel connection between the consensus problem and the theory of gamma synchronizers. Simulation experiments are presented and discussed.

    @inproceedings{RossiPavone2013,
      author = {Rossi, F. and Pavone, M.},
      title = {Decentralized Decision-Making on Robotic Networks with Hybrid Performance Metrics},
      booktitle = {{Allerton Conf. on Communications, Control and Computing}},
      year = {2013},
      address = {Champaign, Illinois},
      doi = {10.1109/Allerton.2013.6736546},
      month = oct,
      url = {../wp-content/papercite-data/pdf/Rossi.Pavone.Allerton13.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  87. R. Allen et al., “Internally-Actuated Rovers for All-Access Surface Mobility: Theory and Experimentation,” in Proc. IEEE Conf. on Robotics and Automation, Karlsruhe, Germany, 2013.

    Abstract: The future exploration of small Solar System bodies will, in part, depend on the availability of mobility platforms capable of performing both large surface coverage and short traverses to specific locations. Weak gravitational fields, however, make the adoption of traditional mobility systems difficult. In this paper we present a planetary mobility platform (called "spacecraft/rover hybrid") that relies on internal actuation. A hybrid is a small ( 5 kg), multifaceted robot enclosing three mutually orthogonal flywheels and surrounded by external spikes or contact surfaces. By accelerating/decelerating the flywheels and by exploiting the low-gravity environment, such a platform can perform both long excursions (by hopping) and short, precise traverses (through controlled "tumbles"). This concept has the potential to lead to small, quasi-expendable, yet maneuverable rovers that are robust as they have no external moving parts. In the first part of the paper we characterize the dynamics of such platforms (including fundamental limitations of performance) and we discuss control and planning algorithms. In the second part, we discuss the development of a prototype and present experimental results both in simulations and on physical test stands emulating low-gravity environments. Collectively, our results lay the foundations for the design of internally-actuated rovers with controlled mobility (as opposed to random hopping motion).

    @inproceedings{AllenPavoneEtAl2013,
      author = {Allen, R. and Pavone, M. and McQuin, C. and Nesnas, Issa and {Castillo-Rogez}, Julie C. and Nguyen, {Tam-Nguyen} and Hoffman, Jeffrey A.},
      title = {Internally-Actuated Rovers for All-Access Surface Mobility: Theory and Experimentation},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2013},
      address = {Karlsruhe, Germany},
      doi = {10.1109/ICRA.2013.6631363},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Allen.Pavone.ea.ICRA13.pdf}
    }
    
  88. L. Janson and M. Pavone, “Fast Marching Trees: A Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions,” in Int. Symp. on Robotics Research, Singapore, 2013.

    Abstract: In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a "lazy" dynamic programming recursion on a predetermined number of probabilistically-drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds–the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O(n-1/d+ρ), where n is the number of sampled points, d is the dimension of the configuration space, and ρis an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our theoretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.

    @inproceedings{JansonPavone2013,
      author = {Janson, L. and Pavone, M.},
      title = {{Fast} {Marching} {Trees:} A Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions},
      booktitle = {{Int. Symp. on Robotics Research}},
      year = {2013},
      address = {Singapore},
      month = dec,
      url = {../wp-content/papercite-data/pdf/Janson.Pavone.ISRR13.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  89. Y. Chow and M. Pavone, “A Uniform-Grid Discretization Algorithm for Stochastic Optimal Control with Risk Constraints,” in Proc. IEEE Conf. on Decision and Control, Firenze, Italy, 2013.

    Abstract: In this paper, we present a discretization algorithm for the solution of stochastic optimal control problems with dynamic, time-consistent risk constraints. Previous works have shown that such problems can be cast as Markov decision problems (MDPs) on an augmented state space where a constrained form of Bellman’s recursion can be applied. However, even if both the state space and action spaces for the original optimization problem are finite, the augmented state in the induced MDP problem contains state variables that are continuous. Our approach is to apply a uniform-grid discretization scheme for the augmented state. To prove the correctness of this approach, we develop novel Lipschitz bounds for constrained dynamic programming operators. We show that convergence to the optimal value functions is linear in the step size, which is the same convergence rate for discretization algorithms for unconstrained dynamic programming operators. Simulation experiments are presented and discussed.

    @inproceedings{ChowPavone2013b,
      author = {Chow, Y. and Pavone, M.},
      title = {A Uniform-Grid Discretization Algorithm for Stochastic Optimal Control with Risk Constraints},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2013},
      address = {Firenze, Italy},
      doi = {10.1109/CDC.2013.6760250},
      month = dec,
      url = {../wp-content/papercite-data/pdf/Chow.Pavone.CDC13.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  90. Y. Chow and M. Pavone, “Stochastic Optimal Control with Dynamic, Time-Consistent Risk Constraints,” in American Control Conference, Washington, D.C., 2013.

    Abstract: In this paper we present a dynamic programing approach to stochastic optimal control problems with dynamic, time-consistent risk constraints. Constrained stochastic optimal control problems, which naturally arise when one has to consider multiple objectives, have been extensively investigated in the past 20 years; however, in most formulations, the constraints are formulated as either risk-neutral (i.e., by considering an expected cost), or by applying static, singleperiod risk metrics with limited attention to "time-consistency" (i.e., to whether such metrics ensure rational consistency of risk preferences across multiple periods). Recently, significant strides have been made in the development of a rigorous theory of dynamic, time-consistent risk metrics for multi-period (risk-sensitive) decision processes; however, their integration within constrained stochastic optimal control problems has received little attention. The goal of this paper is to bridge this gap. First, we formulate the stochastic optimal control problem with dynamic, time-consistent risk constraints and we characterize the tail subproblems (which requires the addition of a Markovian structure to the risk metrics). Second, we develop a dynamic programming approach for its solution, which allows to compute the optimal costs by value iteration. Finally, we discuss both theoretical and practical features of our approach, such as generalizations, construction of optimal control policies, and computational aspects. A simple, two-state example is given to illustrate the problem setup and the solution approach.

    @inproceedings{ChowPavone2013,
      author = {Chow, Y. and Pavone, M.},
      title = {Stochastic Optimal Control with Dynamic, Time-Consistent Risk Constraints},
      booktitle = {{American Control Conference}},
      year = {2013},
      address = {Washington, D.C.},
      doi = {10.1109/ACC.2013.6579868},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Chow.Pavone.ACC13.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  91. A. Stoica et al., “Using Arm and Hand Gestures to Command Robots during Stealth Operations,” in Proc. of SPIE, Baltimore, Maryland, 2012.

    Abstract: Command of support robots by the warfighter requires intuitive interfaces to quickly communicate high degree-of-freedom (DOF) information while leaving the hands unencumbered. Stealth operations rule out voice commands and vision-based gesture interpretation techniques, as they often entail silent operations at night or in other low visibility conditions. Targeted at using bio-signal inputs to set navigation and manipulation goals for the robot (say, simply by pointing), we developed a system based on an electromyography (EMG) "BioSleeve", a high density sensor array for robust, practical signal collection from forearm muscles. The EMG sensor array data is fused with inertial measurement unit (IMU) data. This paper describes the BioSleeve system and presents initial results of decoding robot commands from the EMG and IMU data using a BioSleeve prototype with up to sixteen bipolar surface EMG sensors. The BioSleeve is demonstrated on the recognition of static hand positions (e.g. palm facing front, fingers upwards) and on dynamic gestures (e.g. hand wave). In preliminary experiments, over 90% correct recognition was achieved on five static and nine dynamic gestures. We use the BioSleeve to control a team of five LANdroid robots in individual and group/squad behaviors. We define a gesture composition mechanism that allows the specification of complex robot behaviors with only a small vocabulary of gestures/commands, and we illustrate it with a set of complex orders.

    @inproceedings{StoicaAssadEtAl2012,
      author = {Stoica, A. and Assad, C. and Wolf, M. and You, K. S. and Pavone, M. and Huntsberger, T. and Iwashita, Y.},
      title = {Using Arm and Hand Gestures to Command Robots during Stealth Operations},
      booktitle = {{Proc. of SPIE}},
      year = {2012},
      address = {Baltimore, Maryland},
      doi = {10.1117/12.923690},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Stoica.Assad.ea.SPIE12.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  92. K. Treleaven, M. Pavone, and E. Frazzoli, “Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems,” in American Control Conference, Montréal, Canada, 2012.

    Abstract: Demand-responsive transport (DRT) systems, where users generate requests for transportation from a pickup point to a delivery point, are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. However, despite the increasing role of DRT systems, there are very few rigorous results characterizing achievable performance (in terms, e.g., of stability conditions). In this paper, our aim is to bridge this gap for a rather general model of DRT systems, which takes the form of a generalized Dynamic Pickup and Delivery Problem. The key strategy is to develop analytical bounds for the optimal cost of the Euclidean Stacker Crane Problem (ESCP), which represents a general static model for DRT systems. By leveraging such bounds, we characterize a necessary and sufficient condition for the stability of DRT systems; the condition depends only on the workspace geometry, the stochastic distributions of pickup and delivery points, customers’ arrival rate, and the number of vehicles. Our results exhibit some surprising features that are absent in traditional spatially-distributed queueing systems.

    @inproceedings{TreleavenPavoneEtAl2012,
      author = {Treleaven, K. and Pavone, M. and Frazzoli, E.},
      title = {Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems},
      booktitle = {{American Control Conference}},
      year = {2012},
      address = {Montr\'{e}al, Canada},
      doi = {10.1109/ACC.2012.6315329},
      month = jun,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Treleaven.Pavone.ea.ACC12.pdf}
    }
    
  93. Y. Kuwata, M. Pavone, and J. Balaram, “A Risk-Constrained Multi-Stage Decision Making Approach to the Architectural Analysis of Mars Missions,” in Proc. IEEE Conf. on Decision and Control, Maui, Hawaii, 2012.

    Abstract: This paper presents a novel risk-constrained multi-stage decision making approach to the architectural analysis of planetary rover missions. In particular, focusing on a 2018 Mars rover concept, which was considered as part of a potential Mars Sample Return campaign, we model the entry, descent, and landing (EDL) phase and the rover traverse phase as four sequential decision-making stages. The problem is to find a sequence of divert and driving maneuvers so that the rover drive is minimized and the probability of a mission failure (e.g., due to a failed landing) is below a user specified bound. By solving this problem for several different values of the model parameters (e.g., divert authority), this approach enables rigorous, accurate and systematic trade-offs for the EDL system vs. the mobility system, and, more in general, cross-domain trade-offs for the different phases of a space mission. The overall optimization problem can be seen as a chance-constrained dynamic programming problem, with the additional complexity that 1) in some stages the disturbances do not have any probabilistic characterization, and 2) the state space is extremely large (i.e, hundreds of millions of states for trade-offs with high-resolution Martian maps). To this purpose, we solve the problem by performing an unconventional combination of average and minimax cost analysis and by leveraging high efficient computation tools from the image processing community. Preliminary trade-off results are presented.

    @inproceedings{KuwataPavoneEtAl2012,
      author = {Kuwata, Y. and Pavone, M. and Balaram, J.},
      title = {A Risk-Constrained Multi-Stage Decision Making Approach to the Architectural Analysis of {M}ars Missions},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2012},
      address = {Maui, Hawaii},
      doi = {10.1109/CDC.2012.6426090},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Kuwata.Pavone.ea.CDC12.pdf}
    }
    
  94. K. Treleaven, M. Pavone, and E. Frazzoli, “Models and Efficient Algorithms for Pickup and Delivery Problems on Roadmaps,” in Proc. IEEE Conf. on Decision and Control, Maui, Hawaii, 2012.

    Abstract: One of the most common combinatorial problems in logistics and transportation-after the Traveling Salesman Problem-is the Stacker Crane Problem (SCP), where commodities or customers are associated each with a pickup location and a delivery location, and the objective is to find a minimum-length tour ’picking up’ and ’delivering’ all items, while ensuring the number of items on-board never exceeds a given capacity. While vastly many SCPs encountered in practice are embedded in road or road-like networks, very few studies explicitly consider such environments. In this paper, first, we formulate an environment model capturing the essential features of a "small-neighborhood" road network, along with models for omni-directional vehicles and directed vehicles. Then, we formulate a stochastic version of the unit-capacity SCP, on our road network model, where pickup/delivery sites are random points along segments of the network. Our main contribution is a polynomial-time algorithm for the problem that is asymptotically constant-factor; i.e., it produces a solution no worse than κ+o(1) times the length of the optimal one, where o(1) goes to zero as the number of items grows large, almost surely. The constant κis at most 3, and for omni-directional vehicles it is provably 1, i.e., optimal. Simulations show that with a number of pickup/delivery pairs as low as 50, the proposed algorithm delivers a solution whose cost is consistently within 10% of that of an optimal solution.

    @inproceedings{TreleavenPavoneEtAl2012b,
      author = {Treleaven, K. and Pavone, M. and Frazzoli, E.},
      title = {Models and Efficient Algorithms for Pickup and Delivery Problems on Roadmaps},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2012},
      address = {Maui, Hawaii},
      doi = {10.1109/CDC.2012.6426164},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Treleaven.Pavone.ea.CDC12.pdf}
    }
    
  95. J. Castillo, M. Pavone, I. Nesnas, and J. A. Hoffman, “Expected Science Return of Spatially-Extended In-Situ Exploration at Small Solar System Bodies,” in IEEE Aerospace Conference, Big Sky, Montana, 2012.

    Abstract: The recent decadal survey report for planetary science (compiled by the National Research Council) has prioritized three main areas for planetary exploration: (1) the characterization of the early Solar system history, (2) the search for planetary habitats, and (3) an improved understanding about the nature of planetary processes. A growing number of ground and space observations suggest that small bodies are ideally suited for addressing all these three priorities. In parallel, several technological advances have been recently made for microgravity rovers, penetrators, and MEMS-based instruments. Motivated by these findings and new technologies, the objective of this paper is to study the expected science return of spatially-extended in-situ exploration at small bodies, as a function of surface covered and in the context of the key science priorities identified by the decadal survey report. Specifically, targets within the scope of our analysis belong to three main classes: main belt asteroids and irregular satellites, Near Earth Objects, and comets. For each class of targets, we identify the corresponding science objectives for potential future exploration, we discuss the types of measurements and instruments that would be required, and we discuss mission architectures (with an emphasis on spatially-extended in-situ exploration) to achieve such objectives. Then, we characterize (notionally) how the science return for two reference targets would scale with the amount (and type) of surface that is expected to be covered by a robotic mobile platform. The conclusion is that spatially-extended in-situ information about the chemical and physical heterogeneity of small bodies has the potential to lead to a much improved understanding about their origin, evolution, and astrobiological relevance.

    @inproceedings{CastilloPavoneEtAl2012,
      author = {Castillo, J. and Pavone, M. and Nesnas, I. and Hoffman, J. A.},
      title = {Expected Science Return of Spatially-Extended In-Situ Exploration at Small {Solar} {System} Bodies},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2012},
      address = {Big Sky, Montana},
      doi = {10.1109/AERO.2012.6187034},
      month = mar,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Castillo.Pavone.ea.Aero12.pdf}
    }
    
  96. K. Treleaven, M. Pavone, and E. Frazzoli, “An Asymptotically Optimal Algorithm for Pickup and Delivery Problems,” in Proc. IEEE Conf. on Decision and Control, Orlando, Florida, 2011.

    Abstract: The Stacker Crane Problem is NP-Hard and the best known approximation algorithm only provides a 9/5 approximation ratio. The objective of this paper is threefold. First, by embedding the problem within a stochastic framework, we present a novel algorithm for the SCP that: (i) is asymptotically optimal, i.e., it produces, almost surely, a solution approaching the optimal one as the number of pickups/deliveries goes to infinity; and (ii) has computational complexity O(n^2+\eps), where n is the number of pickup/delivery pairs and \eps is an arbitrarily small positive constant. Second, we asymptotically characterize the length of the optimal SCP tour. Finally, we study a dynamic version of the SCP, whereby pickup and delivery requests arrive according to a Poisson process, and which serves as a model for large-scale demand-responsive transport (DRT) systems. For such a dynamic counterpart of the SCP, we derive a necessary and sufficient condition for the existence of stable vehicle routing policies, which depends only on the workspace geometry, the stochastic distributions of pickup and delivery points, the arrival rate of requests, and the number of vehicles. Our results leverage a novel connection between the Euclidean Bipartite Matching Problem and the theory of random permutations, and, for the dynamic setting, exhibit novel features that are absent in traditional spatially-distributed queueing systems.

    @inproceedings{TreleavenPavoneEtAl2011,
      author = {Treleaven, K. and Pavone, M. and Frazzoli, E.},
      title = {An Asymptotically Optimal Algorithm for Pickup and Delivery Problems},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2011},
      address = {Orlando, Florida},
      doi = {10.1109/CDC.2011.6161406},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Treleaven.Pavone.ea.CDC11.pdf}
    }
    
  97. M. Pavone, S. L. Smith, E. Frazzoli, and D. Rus, “Load Balancing for Mobility-on-Demand Systems,” in Robotics: Science and Systems, Los Angeles, California, 2011.

    Abstract: In this paper we develop methods for maximizing the throughput of a mobility-on-demand urban transportation system. We consider a finite group of shared vehicles, located at a set of stations. Users arrive at the stations, pick-up vehicles, and drive (or are driven) to their destination station where they drop-off the vehicle. When some origins and destinations are more popular than others, the system will inevitably become out of balance: Vehicles will build up at some stations, and become depleted at others. We propose a robotic solution to this rebalancing problem that involves empty robotic vehicles autonomously driving between stations. We develop a rebalancing policy that minimizes the number of vehicles performing rebalancing trips. To do this, we utilize a fluid model for the customers and vehicles in the system. The model takes the form of a set of nonlinear time-delay differential equations. We then show that the optimal rebalancing policy can be found as the solution to a linear program. By analyzing the dynamical system model, we show that every station reaches an equilibrium in which there are excess vehicles and no waiting customers. We use this solution to develop a real-time rebalancing policy which can operate in highly variable environments. We verify policy performance in a simulated mobility-on-demand environment with stochastic features found in real-world urban transportation networks.

    @inproceedings{PavoneSmithEtAl2011,
      author = {Pavone, M. and Smith, S. L. and Frazzoli, E. and Rus, D.},
      title = {Load Balancing for {Mobility-on-Demand} Systems},
      booktitle = {{Robotics: Science and Systems}},
      year = {2011},
      address = {Los Angeles, California},
      doi = {10.15607/rss.2011.vii.034},
      month = jun,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Smith.ea.RSS11.pdf}
    }
    
  98. M. Pavone and E. Frazzoli, “Dynamic Vehicle Routing with Stochastic Time Constraints,” in Proc. IEEE Conf. on Robotics and Automation, Anchorage, Alaska, 2010.

    Abstract: In this paper we study a dynamic vehicle routing problem where demands have stochastic deadlines on their waiting times. Specifically, a network of robotic vehicles must service demands whose time of arrival, location and on-site service are stochastic; moreover, once a demand arrives, it remains active for a stochastic amount of time, and then expires. An active demand is successfully serviced when one of the vehicles visits its location before its deadline and provide the required on-site service. The aim is to find the minimum number of vehicles needed to ensure that the steady-state probability that a demand is successfully serviced is larger than a desired value, and to determine the policy the vehicles should execute to ensure that such objective is attained. First, we carefully formulate the problem, and we show its well-posedness by providing some novel ergodic results. Second, we provide a lower bound on the optimal number of vehicles; finally, we analyze two service policies, and we show that one of them is optimal in light load. Simulation results are presented and discussed.

    @inproceedings{PavoneFrazzoli2010,
      author = {Pavone, M. and Frazzoli, E.},
      title = {Dynamic Vehicle Routing with Stochastic Time Constraints},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2010},
      address = {Anchorage, Alaska},
      doi = {10.1109/ROBOT.2010.5509222},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Frazzoli.ICRA10.pdf}
    }
    
  99. M. Pavone, K. Treleaven, and E. Frazzoli, “Fundamental Performance Limits and Efficient Policies for Transportation-On-Demand Systems,” in Proc. IEEE Conf. on Decision and Control, Atlanta, Georgia, 2010.

    Abstract: Transportation-On-Demand (TOD) systems, where users generate requests for transportation from a pick-up point to a delivery point, are already very popular and are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. Routing service vehicles through customers is usually accomplished with heuristic algorithms. In this paper we study TOD systems in a formal setting that allows us to characterize fundamental performance limits and devise dynamic routing policies with provable performance guarantees. Specifically, we study TOD systems in the form of a unit-capacity, multiple-vehicle dynamic pick-up and delivery problem, whereby pick-up requests arrive according to a Poisson process and are randomly located according to a general probability density. Corresponding delivery locations are also randomly distributed according to a general probability density, and a number of unit-capacity vehicles must transport demands from their pick-up locations to their delivery locations. We derive insightful fundamental bounds on the steady-state waiting times for the demands, and we devise constant-factor optimal dynamic routing policies. Simulation results are presented and discussed.

    @inproceedings{PavoneTreleavenEtAl2010,
      author = {Pavone, M. and Treleaven, K. and Frazzoli, E.},
      title = {Fundamental Performance Limits and Efficient Policies for {Transportation-On-Demand} Systems},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2010},
      address = {Atlanta, Georgia},
      doi = {10.1109/CDC.2010.5717552},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Treleaven.ea.CDC10.pdf}
    }
    
  100. J. L. Ramirez, M. Pavone, E. Frazzoli, and D. W. Miller, “Distributed Control of Spacecraft Formation via Cyclic Pursuit: Theory and Experiments,” in American Control Conference, St. Louis, Missouri, 2009.

    Abstract: In this paper we study distributed control policies for spacecraft formations that draw inspiration from the simple idea of cyclic pursuit. First, we extend existing cyclic-pursuit control laws devised for single-integrator models in two dimensions to the case of double-integrator models in three dimensions. In particular, we develop control laws that only require relative measurements of position and velocity with respect to the two leading neighbors in the ring topology of cyclic pursuit, and allow the spacecraft to converge to a variety of symmetric formations, including evenly spaced circular formations and evenly spaced Archimedes’ spirals. Second, we discuss potential applications, including spacecraft coordination for interferometric imaging and convergence to zero-effort orbits. Finally, we present and discuss experimental results obtained by implementing the aforementioned control laws on three nanospacecraft on board the International Space Station.

    @inproceedings{RamirezPavoneEtAl2009,
      author = {Ramirez, J. L. and Pavone, M. and Frazzoli, E. and Miller, D. W.},
      title = {Distributed Control of Spacecraft Formation via Cyclic Pursuit: Theory and Experiments},
      booktitle = {{American Control Conference}},
      year = {2009},
      address = {St. Louis, Missouri},
      doi = {10.1109/ACC.2009.5160735},
      month = jun,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Ramirez.Pavone.ea.ACC09.pdf}
    }
    
  101. M. Pavone, S. L. Smith, F. Bullo, and E. Frazzoli, “Dynamic Multi-Vehicle Routing with Multiple Classes of Demands,” in American Control Conference, St. Louis, Missouri, 2009.

    Abstract: In this paper we study a dynamic vehicle routing problem in which there are multiple vehicles and multiple classes of demands. Demands of each class arrive in the environment randomly over time and require a random amount of on-site service that is characteristic of the class. To service a demand, one of the vehicles must travel to the demand location and remain there for the required on-site service time. The quality of service provided to each class is given by the expected delay between the arrival of a demand in the class, and that demand’s service completion. The goal is to design a routing policy for the service vehicles which minimizes a convex combination of the delays for each class. First, we provide a lower bound on the achievable values of the convex combination of delays. Then, we propose a novel routing policy and analyze its performance under heavy load conditions (i.e., when the fraction of time the service vehicles spend performing on-site service approaches one). The policy performs within a constant factor of the lower bound (and thus the optimal), where the constant depends only on the number of classes, and is independent of the number of vehicles, the arrival rates of demands, the on-site service times, and the convex combination coefficients.

    @inproceedings{PavoneSmithEtAl2009,
      author = {Pavone, M. and Smith, S. L. and Bullo, F. and Frazzoli, E.},
      title = {Dynamic Multi-Vehicle Routing with Multiple Classes of Demands},
      booktitle = {{American Control Conference}},
      year = {2009},
      address = {St. Louis, Missouri},
      doi = {10.1109/ACC.2009.5160557},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Pavone.Smith.ea.ACC09.pdf},
      owner = {bylard},
      timestamp = {2017-02-20}
    }
    
  102. M. Pavone, A. Arsie, E. Frazzoli, and F. Bullo, “Equitable Partitioning Policies for Robotic Networks,” in Proc. IEEE Conf. on Robotics and Automation, Kobe, Japan, 2009.

    Abstract: The most widely applied resource allocation strategy is to balance, or equalize, the total workload assigned to each resource. In mobile multi-agent systems, this principle directly leads to equitable partitioning policies in which (i) the workspace is divided into subregions of equal measure, (ii) there is a bijective correspondence between agents and subregions, and (iii) each agent is responsible for service requests originating within its own subregion. In this paper, we provide the first distributed algorithm that provably allows m agents to converge to an equitable partition of the workspace, from any initial configuration, i.e., globally. Our approach is related to the classic Lloyd algorithm, and provides novel insights into the properties of power diagrams. Simulation results are presented and discussed.

    @inproceedings{PavoneArsieEtAl2009,
      author = {Pavone, M. and Arsie, A. and Frazzoli, E. and Bullo, F.},
      title = {Equitable Partitioning Policies for Robotic Networks},
      booktitle = {{Proc. IEEE Conf. on Robotics and Automation}},
      year = {2009},
      address = {Kobe, Japan},
      doi = {10.1109/ROBOT.2009.5152809},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Arsie.ea.ICRA09.pdf}
    }
    
  103. S. L. Smith, M. Pavone, F. Bullo, and E. Frazzoli, “Dynamic Vehicle Routing with Heterogeneous Demands,” in Proc. IEEE Conf. on Decision and Control, Cancun, Mexico, 2008.

    Abstract: In this paper we study a variation of the Dynamic Traveling Repairperson Problem (DTRP) in which there are two classes of demands; high priority, and low priority. In the problem, demands arrive in the environment randomly over time and assume a random location and on-site service requirement. A service vehicle must travel to each demand location and provide the required on-site service. The quality of service provided to each class of demands is measured by the expected delay between a demand’s arrival and its service completion. The goal is to design policies for the service vehicle which minimize a convex combination of the delays for each class. We provide a lower bound on the achievable delay for this problem, and propose a policy which performs within a known constant factor of the optimal in heavy load (i.e., when the fraction of time the service vehicle spends performing on-site service approaches one). The problem studied in this paper is analogous to the multi-class queuing problem in classical queuing theory.

    @inproceedings{SmithPavoneEtAl2008,
      author = {Smith, S. L. and Pavone, M. and Bullo, F. and Frazzoli, E.},
      title = {Dynamic Vehicle Routing with Heterogeneous Demands},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2008},
      address = {Cancun, Mexico},
      doi = {10.1109/CDC.2008.4739284},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Smith.Pavone.ea.CDC08.pdf}
    }
    
  104. M. Pavone, E. Frazzoli, and F. Bullo, “Distributed Policies for Equitable Partitioning: Theory and Applications,” in Proc. IEEE Conf. on Decision and Control, Cancun, Mexico, 2008.

    Abstract: The most widely applied resource allocation strategy is to balance, or equalize, the total workload assigned to each resource. In mobile multi-agent systems, this principle directly leads to equitable partitioning policies in which (i) the workspace is divided into subregions of equal measure, (ii) each agent is assigned to a unique subregion, and (iii) each agent is responsible for service requests originating within its own subregion. In this paper, we design distributed and adaptive policies to allow a team of agents to achieve a convex and equitable partition of a convex workspace. Our approach is related to the classic Lloyd algorithm, and exploits the unique features of Power Diagrams. We discuss possible applications to routing of vehicles in stochastic and dynamic environments, and to wireless networks. Simulation results are presented and discussed.

    @inproceedings{PavoneFrazzoliEtAl2008,
      author = {Pavone, M. and Frazzoli, E. and Bullo, F.},
      title = {Distributed Policies for Equitable Partitioning: Theory and Applications},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2008},
      address = {Cancun, Mexico},
      doi = {10.1109/CDC.2008.4739483},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Frazzoli.ea.CDC08.pdf}
    }
    
  105. M. Pavone, N. Bisnik, E. Frazzoli, and V. Isler, “Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience,” in Int. Conf. on Robot Communication and Coordination, Athens, Greece, 2007.

    Abstract: Consider the following scenario: a spatio-temporal stochastic process generates service requests, localized at points in a bounded region on the plane; these service requests are fulfilled when one of a team of mobile agents visits the location of the request. For example, a service request may represent the detection of an event in a sensor network application, which needs to be investigated on site. Once a service request has been generated, it remains active for an amount of time which is itself a random variable, and then expires. The problem we investigate is the following: What is the minimum number of mobile agents needed to ensure that each service request is fulfilled before expiring, with probability at least 1 - \eps? What strategy should they use to ensure this objective is attained? Formulating the probability of successfully servicing requests before expiration as a performance metric, we derive bounds on the minimum number of agents required to ensure a given performance level, and present decentralized motion coordination algorithms that approximate the optimal strategy.

    @inproceedings{PavoneBisnikEtAl2007,
      author = {Pavone, M. and Bisnik, N. and Frazzoli, E. and Isler, V.},
      title = {Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience},
      booktitle = {{Int. Conf. on Robot Communication and Coordination}},
      year = {2007},
      address = {Athens, Greece},
      doi = {10.4108/icst.robocomm2007.2220},
      month = oct,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Bisnik.ea.Robocomm07.pdf}
    }
    
  106. M. Pavone and E. Frazzoli, “Decentralized Policies for Geometric Pattern Formation,” in American Control Conference, New York, New York, 2007.

    Abstract: This paper presents a decentralized control policy for symmetric formations in multi-agent systems. It is shown that n agents, each one pursuing its leading neighbor along the line of sight rotated by a common offset angle α, eventually converge to a single point, a circle or a logarithmic spiral pattern, depending on the value of α. Simulation results are presented and discussed.

    @inproceedings{PavoneFrazzoli2007b,
      author = {Pavone, M. and Frazzoli, E.},
      title = {Decentralized Policies for Geometric Pattern Formation},
      booktitle = {{American Control Conference}},
      year = {2007},
      address = {New York, New York},
      doi = {10.1109/ACC.2007.4283108},
      month = jul,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Frazzoli.ACC07.pdf}
    }
    
  107. M. Pavone, E. Frazzoli, and F. Bullo, “Decentralized Algorithms for Stochastic and Dynamic Vehicle Routing with General Demand Distribution,” in Proc. IEEE Conf. on Decision and Control, New Orleans, Louisiana, 2007.

    Abstract: We present decentralized algorithms for a class of stochastic and dynamic vehicle routing problems, known as the multiple-vehicle dynamic traveling repairperson problem (m-DTRP), in which demands arrive randomly over time and their locations have an arbitrary distribution, and the objective is to minimize the average waiting time between the appearance of a demand and the time it is visited by a vehicle. The best previously known control algorithms rely on centralized, a-priori task assignment, and are therefore of limited applicability in scenarios involving large ad-hoc networks of autonomous vehicles. By combining results from geometric probability and locational optimization, we provide a policy that solves, providing a constant-factor approximation to the optimal achievable performance, the decentralized version of the m-DTRP; such policy (i) does not rely on centralized and a priori task assignment, (ii) is spatially distributed, scalable to large networks, and adaptive to network changes. Simulation results are presented and discussed.

    @inproceedings{PavoneFrazzoliEtAl2007,
      author = {Pavone, M. and Frazzoli, E. and Bullo, F.},
      title = {Decentralized Algorithms for Stochastic and Dynamic Vehicle Routing with General Demand Distribution},
      booktitle = {{Proc. IEEE Conf. on Decision and Control}},
      year = {2007},
      address = {New Orleans, Louisiana},
      doi = {10.1109/CDC.2007.4434989},
      month = dec,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Frazzoli.ea.CDC07.pdf}
    }
    
  108. P. Arena, L. Fortuna, M. Frasca, L. Patanè, and M. Pavone, “Realization of a CNN-Driven Cockroach-Inspired Robot,” in Int. Symp. on Circuits and Systems, Kos, Greece, 2006.

    Abstract: This paper describes the implementation of a bio-inspired six legged robot: Gregor I. Both structure and locomotion control are inspired by biological observations in cockroaches. Robot mechanics attempts to emulate main structural features in cockroaches, like self-stabilizing posture and specializing legged function; in turn, locomotion control is based on the theory of the central pattern generator implemented on a VLSI chip. The final aim is to artificially replicate the fundamental principles that guarantee cockroach’s extraordinary agility. Our major concern was on the implementation of rear legs, that seem to play a crucial role in obstacle overcoming and payload capability, and on the locomotion control, performed in this work by a cellular neural network playing the role of an artificial central pattern generator. Experimental tests showed that Gregor I is able to walk at the travel speed of 0.1 body length per second and to successfully negotiate obstacles more than 170% of the height of its mass center.

    @inproceedings{ArenaFortunaEtAl2006b,
      author = {Arena, P. and Fortuna, L. and Frasca, M. and Patan\`e, L. and Pavone, M},
      title = {Realization of a {CNN}-Driven Cockroach-Inspired Robot},
      booktitle = {{Int. Symp. on Circuits and Systems}},
      year = {2006},
      address = {Kos, Greece},
      doi = {10.1109/ISCAS.2006.1693168},
      month = may,
      url = {../wp-content/papercite-data/pdf/Arena.Fortuna.ea.ISCAS06b.pdf},
      owner = {bylard},
      timestamp = {2017-01-28}
    }
    
  109. P. Arena, L. Fortuna, M. Frasca, L. Patanè, and M. Pavone, “Towards Autonomous Adaptive Behavior in a Bio-inspired CNN-controlled Robot,” in Int. Symp. on Circuits and Systems, Kos, Greece, 2006.

    Abstract: This paper describes a general approach for the adaptive supervised learning of behaviors in a behavior-based robot. The key idea is to formalize a behavior produced by a Motor Map driven by an internal adaptive reward function. Aim of the adaptive reward function is to select the most significant sensory inputs and to use them in the best way. The greatest challenge is to keep small the search space. Motor map learning relies on the classical Kohonen algorithm, while the structure of the reward function is learnt through a non-associative reinforcement learning algorithm. Simulation results on a six legged biologically-inspired robot confirm the suitability of the approach. This methodology allows the human designer to easily embody all the a priori knowledge on the robot controller, while providing at the same time a high degree of adaptability and robustness against the sensory malfunctioning.

    @inproceedings{ArenaFortunaEtAl2006,
      author = {Arena, P. and Fortuna, L. and Frasca, M. and Patan\`e, L. and Pavone, M.},
      title = {Towards Autonomous Adaptive Behavior in a Bio-inspired {CNN}-controlled Robot},
      booktitle = {{Int. Symp. on Circuits and Systems}},
      year = {2006},
      address = {Kos, Greece},
      doi = {10.1109/ISCAS.2006.1692549},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Arena.Fortuna.ea.ISCAS06a.pdf}
    }
    
  110. M. Pavone, P. Arena, and L. Patanè, “An Innovative Mechanical and Control Architecture for a Biomimetic Hexapod for Planetary Exploration,” in Int. Astronautical Congress, Fukuoka, Japan, 2005.

    Abstract: This paper addresses the design of a six legged robot for planetary exploration. The robot is specifically designed for uneven terrains and is bio-logically inspired on different levels: mechanically as well as in control. A novel structure is developed basing on a (careful) emulation of the cockroach, whose extraordinary agility and speed are principally due to its self-stabilizing posture and specializing legged function. Structure design enhances these properties, in particular with an innovative piston-like scheme for rear legs, while avoiding an excessive and useless complexity. Locomotion control is designed following an analog electronics approach, that in space applications could hold many benefits. In particular, the locomotion control is based on a Cellular Neural Network playing the role of an artificial Central Pattern Generator. Several dynamical simulations were carried out to test the structure and the locomotion control. Simulation results led to the implementation of the first prototype: Gregor I. Experimental tests showed that Gregor I is able to walk at the travel speed of 0.1 body length per second and to successfully negotiate obstacles more than 170% of the height of its center of mass.

    @inproceedings{PavoneArenaEtAl2005,
      author = {Pavone, M. and Arena, P. and Patan\`e, L.},
      title = {An Innovative Mechanical and Control Architecture for a Biomimetic Hexapod for Planetary Exploration},
      booktitle = {{Int. Astronautical Congress}},
      year = {2005},
      note = {Paper \# IAC-05-A3.2.B.09},
      address = {Fukuoka, Japan},
      doi = {10.2514/6.IAC-05-A3.2.B.09},
      month = oct,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Arena.IAC05.pdf}
    }
    
  111. P. Arena, L. Fortuna, M. Frasca, L. Patanè, and M. Pavone, “Climbing Obstacles via Bio-Inspired CNN-CPG and Adaptive Attitude Control,” in Int. Symp. on Circuits and Systems, Kobe, Japan, 2005.

    Abstract: A control system based on the principles used by cockroaches to climb obstacles is introduced and applied to a bio-inspired hexapod robot. Cockroaches adaptively use different strategies as functions of the ground morphology and obstacle characteristics. The control system introduced in this paper consists of two parts working in parallel. Locomotion control is performed by a cellular neural network (CNN) playing the role of an artificial central pattern generator (CPG) for the robot, while a new attitude control system has been designed. In order to reproduce the adaptative capabilities of the biological model, the attitude control system is based on a motor map and is aimed at regulating the posture of the robot to allow it to overcome obstacles. In fact, high obstacles require the locomotion gait to be reorganized by changing the posture of the robot to be more effective during the overcoming of the obstacle. Both proprioceptive and exteroceptive information are needed to solve this problem, they constitute the input of the adaptive attitude control. Simulation results illustrating the suitability of the control system are also shown.

    @inproceedings{ArenaFortunaEtAl2005,
      author = {Arena, P. and Fortuna, L. and Frasca, M. and Patan\`e, L. and Pavone, M.},
      title = {Climbing Obstacles via Bio-Inspired {CNN-CPG} and Adaptive Attitude Control},
      booktitle = {{Int. Symp. on Circuits and Systems}},
      year = {2005},
      address = {Kobe, Japan},
      doi = {10.1109/ISCAS.2005.1465810},
      month = may,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Arena.Fortuna.ea.ISCAS05.pdf}
    }
    

Technical Reports

  1. K. Leung, E. Schmerling, and M. Pavone, “Distributional Prediction of Human Driving Behaviours using Mixture Density Networks,” Stanford University, 2016.

    Abstract: Confident predictions of human driving behaviours are necessary in designing safe and efficient control policies for autonomous vehicles. A better understanding of how human drivers react to their surrounding may avoid the design of overly-conservative control policies which require greater cost (e.g., time, traffic flow disruption) to achieve their objective. In this paper, we explore ways to learn distributions over human driver actions that are typical of a highway setting. We use actions filtered from Next Generation SIMulation (NGSIM) vehicle trajectory data gathered on the US 101 highway as training data for a Recurrent Neural Network. In particular, we use a Mixture Density Network (MDN) model to represent predicted driver actions as a Gaussian Mixture Model. We present and discuss exploratory results on the filtering of the raw NGSIM data and design of the MDN model.

    @techreport{LeungSchmerlingEtAl2016,
      author = {Leung, K. and Schmerling, E. and Pavone, M.},
      title = {Distributional Prediction of Human Driving Behaviours using Mixture Density Networks},
      institution = {{Stanford University}},
      year = {2016},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Leung.Schmerling.Pavone.2016.pdf}
    }
    
  2. M. Quadrelli et al., “Guidance, Navigation, and Control Technology Assessment for Future Planetary Science Missions Part III, Surface Guidance, Navigation, and Control,” Planetary Science Division, NASA Science Mission Directorate, 2013.

    Abstract: Future planetary explorations envisioned by the National Research Council’s (NRC’s) Vision and Voyages for Planetary Science in the Decade 2013-2022, developed at the request of NASA the Science Mission Directorate (SMD) Planetary Science Division (PSD), seek to reach targets of broad scientific interest across the solar system. This goal can be achieved by missions with next-generation capabilities such as innovative interplanetary trajectory solutions, highly accurate landings, the ability to be in close proximity to targets of interest, advanced pointing precision, multiple spacecraft in collaboration, multitarget tours, and advanced robotic surface exploration. Advancements in guidance, navigation, and control (GN&C) and mission design-ranging from software and algorithm development to new sensors-will be necessary to enable these future missions. Spacecraft GN&C technologies have been evolving since the launch of the first rocket. Guidance is defined to be the onboard determination of the desired path of travel from the vehicle’s current location to a designated target. Navigation is defined as the science behind transporting ships, aircraft, or spacecraft from place to place; particularly, the method of determining position, course, and distance traveled as well as the determination of the time reference. Control is defined as the onboard manipulation of vehicle steering controls to track guidance commands while maintaining vehicle pointing with the required precision. As missions become more complex, technological demands on GN&C increase, and so continuous technology progress is necessary. Recognizing the significance of this research, the NRC of the National Academies listed many GN&C technologies as top priorities in the recently released NASA Space Technology Roadmaps and Priorities: Restoring NASA’s Technological Edge and Paving the Way for a New Era in Space. This document-Part III, Surface Guidance, Navigation, and Control-is the third, and last, in a series of technology assessments evaluating the capabilities and technologies needed for future missions pursuing SMD PSD’s scientific goals. These reports cover the status of technologies and provide findings and recommendations to NASA PSD for future needs in GN&C and mission design technologies. Part I covers planetary mission design in general, as well as the estimation and control of vehicle flight paths when flight path and attitude dynamics may be treated as decoupled or only loosely coupled (as is the case the majority of the time in a typical planetary mission). Part II, Onboard Guidance, Navigation, and Control, covers attitude estimation and control in general, as well as the estimation and control of vehicle flight paths when flight path and attitude dynamics are strongly coupled (as is the case during certain critical phases, such as entry, descent, and landing, in some planetary missions). Part III, Surface Guidance, Navigation, and Control, examines GN&C for vehicles that are not in free flight, but that operate on or near the surface of a natural body of the solar system. It should be noted that this is the first time that Surface GNC has been assessed and requirements given for future missions. Together, these documents provide the PSD with a roadmap for achieving science missions in the next decade

    @techreport{QuadrelliMcHenryEtAl2013,
      author = {Quadrelli, M. and McHenry, M. and Wilcox, B. and Hall, J. and Volpe, R. and Nesnas, I. and Nayar, H. and Backes, P. and Mukherjee, R. and Matthies, L. and Zimmerman, W. and Mittman, D. and Pavone, M. and Elfes, A.},
      title = {Guidance, Navigation, and Control Technology Assessment for Future Planetary Science Missions Part {III}, Surface Guidance, Navigation, and Control},
      institution = {{Planetary Science Division, NASA Science Mission Directorate}},
      year = {2013},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {https://solarsystem.nasa.gov/scitech/display.cfm?ST_ID=2547}
    }
    
  3. M. Pavone, J. Castillo, J. A. Hoffman, and I. Nesnas, “Spacecraft/Rover Hybrids for the Exploration of Small Solar System Bodies,” NASA NIAC Program, 2012.

    Abstract: This study investigated a novel mission architecture for the systematic and affordable in-situ exploration of small Solar System bodies. Specifically, a mother spacecraft would deploy over the surface of a small body one, or several, spacecraft/rover hybrids, which are small, multi-faceted enclosed robots with internal actuation and external spikes. They would be capable of 1) long excursions (by hopping), 2) short traverses to specific locations (through a sequence of controlled tumbles), and 3) high-altitude, attitude-controlled ballistic flight (akin to spacecraft flight). Their control would rely on synergistic operations with the mother spacecraft (where most of hybrids’ perception and localization functionalities would be hosted), which would make the platforms minimalistic and, in turn, the entire mission architecture affordable. The Phase I study was aimed at providing an initial feasibility assessment of the proposed architecture and had, in particular, four main objectives: 1) to characterize the expected science return of spatially-extended in-situ exploration at small Solar System bodies, 2) to demonstrate that a hybrid can achieve both large surface coverage via hopping and fine mobility via tumbling in low gravity environments (specifically, for a boulder-free environment with a gravity level on the order of mm/s^2, the requirement was 20%-30% motion accuracy with an average speed on the order of cm/s); 3) to provide first-order estimates for the critical subsystems, and 4) to study mission operations and a mission scenario to Phobos.

    @techreport{PavoneCastilloEtAl2012,
      author = {Pavone, M. and Castillo, J. and Hoffman, J. A. and Nesnas, I.},
      title = {Spacecraft/Rover Hybrids for the Exploration of Small {Solar} {System} Bodies},
      institution = {{NASA NIAC Program}},
      year = {2012},
      note = {Final report},
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.ea.NIAC.Final.Report.2012.pdf}
    }
    

Theses

  1. F. Rossi, “On the Interaction between Autonomous Mobility-on-Demand Systems and the Built Environment: Models and Large Scale Coordination Algorithms,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2018.

    Abstract: Autonomous Mobility-on-Demand systems (that is, fleets of self-driving cars offering on-demand transportation) hold promise to reshape urban transportation by offering high quality of service at lower cost compared to private vehicles. However, the impact of such systems on the infrastructure of our cities (and in particular on traffic congestion and the electric power network) is an active area of research. In particular, Autonomous Mobility-on-Demand (AMoD) systems could greatly increase traffic congestion due to additional "rebalancing" trips required to re-align the distribution of available vehicles with customer demand; furthermore, charging of large fleets of electric vehicles can induce significantly stress in the electric power network, leading to high electricity prices and potential network instability. In this thesis, we build analytical tools and algorithms to model and control the interaction between AMoD systems and our cities. We open our work by exploring the interaction between AMoD systems and urban congestion. Leveraging the theory of network flows, we devise models for AMoD systems that capture endogenous traffic congestion and are amenable to efficient optimization. These models allow us to show the key theoretical result that, under mild assumptions that are substantially verified for U.S. cities, AMoD systems do not increase congestion compared to privately-owned vehicles for a given level of customer demand if empty-traveling vehicles are properly routed. We leverage this insight to design a real-time congestion-aware routing algorithm for empty vehicles; microscopic agent-based simulations with New York City taxi data show that the algorithm significantly reduces congestion compared to a state-of-the-art congestion-agnostic rebalancing algorithm, resulting in 22% lower wait times for AMoD customers. We then devise a randomized congestion-aware routing algorithm for customer-carrying vehicles and prove rigorous analytical bounds on its performance. Preliminary results based on New York City taxi data show that the algorithm could yield a further reduction in congestion and, as a result, 5% lower service times for AMoD customers. We then turn our attention to the interaction between AMoD fleets with electric vehicles and the power network. We extend the network flow model developed in the first part of the thesis to capture the vehicles’ state-of-charge and their interaction with the power network (including charging and the ability to inject power in the network in exchange for a payment, denoted as "vehicle-to-grid"). We devise an algorithmic procedure to losslessly reduce the size of the resulting model, making it amenable to efficient optimization, and test our models and optimization algorithms on a hypothetical deployment of an AMoD system in Dallas-Fort Worth, TX with the goal of maximizing social welfare. Simulation results show that coordination between the AMoD system and the power network can reduce electricity prices by over \180M/year, with savings of \120M/year for local power network customers and $35M/year for the AMoD operator. In order to realize such benefits, the transportation operator must cooperate with the power network: we prove that a pricing scheme can be used to enforce the socially optimal solution as a general equilibrium, aligning the interests of a self-interested transportation operator and self-interested power generators with the goal of maximizing social welfare. We then design privacy-preserving algorithms to compute such coordination-promoting prices in a distributed fashion. Finally, we propose a receding-horizon implementation that trades off optimality for speed and demonstrate that it can be deployed in real-time with microscopic simulations in Dallas-Fort Worth. Collectively, these results lay the foundations for congestion-aware and power-aware control of AMoD systems; in particular, the models and algorithms in this thesis provide tools that will enable transportation network operators and urban planners to foster the positive externalities of AMoD and avoid the negative ones, thus fully realizing the benefits of AMoD systems in our cities.

    @phdthesis{Rossi2018,
      author = {Rossi, F.},
      title = {On the Interaction between {Autonomous Mobility-on-Demand} Systems and the Built Environment: Models and Large Scale Coordination Algorithms},
      school = {{Stanford University, Dept. of Aeronautics and Astronautics}},
      year = {2018},
      address = {Stanford, California},
      month = mar,
      url = {../wp-content/papercite-data/pdf/Rossi.PhD18.pdf},
      owner = {frossi2},
      timestamp = {2018-03-19}
    }
    
  2. Y. Chow, “Risk-Sensitive and Data-Driven Sequential Decision Making,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2017.

    Abstract: Markov decision processes (MDPs) provide a mathematical framework for modeling sequential decision making where system evolution and cost/reward depend on uncertainties and control actions of a decision. MDP models have been widely adopted in numerous domains such as robotics, control systems, finance, economics, and manufacturing. At the same time, optimization theories of MDPs serve as the theoretical underpinnings to numerous dynamic programming and reinforcement learning algorithms in stochastic control problems. While the study in MDPs is attractive for several reasons, there are two main challenges associated with its practicality: (1) An accurate MDP model is oftentimes not available to the decision maker. Affected by modeling errors, the resultant MDP solution policy is non-robust to system fluctuations. (2) The most widely-adopted optimization criterion for MDPs is represented by the risk-neutral expectation of a cumulative cost. This does not take into account the notion of risk, i.e., increased awareness of events of small probability but high consequences. In this thesis we study multiple important aspects in risk-sensitive sequential decision making where the variability of stochastic costs and robustness to modeling errors are taken into account. First, we address a special type of risk-sensitive decision making problems where the percentile behaviors are considered. Here risk is either modeled by the conditional value-at-risk (CVaR) or the Value-at-risk (VaR). VaR measures risk as the maximum cost that might be incurred with respect to a given confidence level, and is appealing due to its intuitive meaning and its connection to chance-constraints. The VaR risk measure has many fundamental engineering applications such as motion planning, where a safety constraint is imposed to upper bound the probability of maneuvering into dangerous regimes. Despite its popularity, VaR suffers from being unstable, and its singularity often introduces mathematical issues to optimization problems. To alleviate this problem, an alternative measure that addresses most of VaR?s shortcomings is CVaR. CVaR is a risk-measure that is rapidly gaining popularity in various financial applications, due to its favorable computational properties (i.e., CVaR is a coherent risk) and superior ability to safeguard a decision maker from the "outcomes that hurt the most". As a risk that measures the conditional expected cost given that such cost is greater than or equal to VaR, CVaR accounts for the total cost of undesirable events (it corresponds to events whose associated probability is low, but the corresponding cost is high) and is therefore preferable in financial application ssuch as portfolio optimization. Second, we consider optimization problems in which the objective function involves a coherent risk measure of the random cost. Here the term coherent risk [7] denotes a general class of risks that satisfies convexity, monotonicity, translational-invariance and positive homogeneity. These properties not only guarantee that the optimization problems are mathematically well-posed, but they are also axiomatically justified. Therefore modeling risk-aversion with coherent risks has already gained widespread acceptance in engineering, finance and operations research applications, among others. On the other hand, when the optimization problem is sequential, another important property of a risk measure is time consistency. A time consistent risk metric satisfies the "dynamic-programming" style property which ensures rational decision making, i.e., the strategy that is risk-optimal at the current stage will also be deemed optimal in subsequent stages. To get the best of both worlds, the recently proposed Markov risk measures [119] satisfy both the coherent risk properties and time consistency. Thus to ensure rationality in risk modeling and algorithmic tractability, this thesis will focus on risk-sensitive sequential decision making problems modeled by Markov risk measures.

    @phdthesis{Chow2017,
      author = {Chow, Y.},
      title = {Risk-Sensitive and Data-Driven Sequential Decision Making},
      school = {{Stanford University, Dept. of Aeronautics and Astronautics}},
      year = {2017},
      address = {Stanford, California},
      month = mar,
      url = {../wp-content/papercite-data/pdf/Chow.PhD17.pdf},
      owner = {frossi2},
      timestamp = {2018-03-19}
    }
    
  3. J. A. Starek, “Sampling-Based Motion Planning for Safe and Efficient Spacecraft Proximity Operations,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2016.

    Abstract: Autonomy has demonstrated success in many vehicle control problems, but has yet to show significant breakthroughs for spacecraft guidance during proximity operations. In part due to a costly verification and validation process as well as from limited access to formally-safe guidance algorithms, mission planners have instead had to rely on maneuver plans with straightforward, easily-verified trajectories and extensive human oversight. Unfortunately, this strategy often introduces propellant inefficiencies, adds significant labor overhead, and limits missions to Earth proximity where two-way communication times are short. This dissertation seeks to remedy these issues by developing a provably-safe and propellant-efficient sampling-based motion planning framework for fully-autonomous spacecraft proximity operations. The framework is designed for a wide range of hazardous guidance scenarios, including autonomous orbital rendezvous and inspection, pinpoint small-body descent, and on-orbit satellite servicing. Due to the dangers associated with operating near other objects, special care is taken to enable real-time guidance as well as ensure the availability of safe abort trajectories so that spacecraft can respond quickly and safely to control failures and sudden environmental changes. Through its generality, efficiency, and speed, the proposed approach offers the potential to enable entirely new capabilities for next-generation space missions, while also increasing the frequency, flexibility, and reliability of present-day operations in space.

    @phdthesis{Starek2016,
      author = {Starek, J. A.},
      title = {Sampling-Based Motion Planning for Safe and Efficient Spacecraft Proximity Operations},
      school = {{Stanford University, Dept. of Aeronautics and Astronautics}},
      year = {2016},
      address = {Stanford, California},
      month = jun,
      url = {../wp-content/papercite-data/pdf/Starek.PhD16.pdf},
      owner = {bylard},
      timestamp = {2017-03-07}
    }
    
  4. R. Zhang, “Models and Large-Scale Coordination Algorithms for Autonomous Mobility-on-Demand,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2016.

    Abstract: Urban mobility in the 21st century faces significant challenges, as the unsustainable trends of urban population growth, congestion, pollution, and low vehicle utilization worsen in large cities around the world. As autonomous vehicle technology draws closer to realization, a solution is beginning to emerge in the form of autonomous mobility-on-demand (AMoD), whereby fleets of self-driving vehicles transport customers within an urban environment. This dissertation introduces a systematic approach to the design, control, and evaluation of these systems. In the first part of the dissertation, a stochastic queueing-theoretical model of AMoD is developed, which allows both the analysis of quality-of-service metrics as well as the synthesis of control policies. This model is then extended to one-way car sharing systems, or human-driven mobility-on-demand (MoD) systems. Based on these models, closed-loop control algorithms are designed to efficiently route empty (rebalancing) vehicles in very large systems with thousands of vehicles. The performance of the algorithms and the potential societal benefits of AMoD and MoD are evaluated through case studies of New York City and Singapore using real-world data. In the second part of the dissertation, additional structural and operational constraints are considered for AMoD systems. First, the impact of AMoD on traffic congestion with respect to the underlying structural properties of the road network is analyzed using a network flow model. In particular, it is shown that empty rebalancing vehicles in AMoD systems will not increase congestion, in stark contrast to popular belief. Finally, the control of AMoD systems with additional operational constraints is studied under a model predictive control framework, with a focus on range and charging constraints of electric vehicles. The technical approach developed in this dissertation allows us to evaluate the societal benefits of AMoD systems as well as lays the foundation for the design and control of future urban transportation networks.

    @phdthesis{Zhang2016,
      author = {Zhang, R.},
      title = {Models and Large-Scale Coordination Algorithms for {Autonomous} {Mobility-on-Demand}},
      school = {{Stanford University, Dept. of Aeronautics and Astronautics}},
      year = {2016},
      address = {Stanford, California},
      month = jun,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Zhang.PhD16.pdf}
    }
    
  5. R. Allen, “A Real-Time Framework for Kinodynamic Planning with Application to Quadrotor Obstacle Avoidance,” PhD thesis, Stanford University, Dept. of Aeronautics and Astronautics, Stanford, California, 2016.

    Abstract: This thesis presents a full-stack, real-time planning framework for kinodynamic robots that is enabled by a novel application of machine learning for reachability analysis. As products of this work, three contributions are discussed in detail in this thesis. The first contribution is the novel application of machine learning for rapid approximation of reachable sets for dynamical systems. The second contribution is the synthesis of machine learning, sampling-based motion planning, and optimal control into a cohesive planning framework that is built on an offline-online computation paradigm. The final contribution is the application of this planning framework on a quadrotor system to produce, arguably, one of the first demonstrations of fully-online kinodynamic motion planning. During physical experiments, the framework is shown to execute planning cycles at a rate 3 Hz to 5 Hz, a significant improvement over existing techniques. For the quadrotor, a simplified dynamics model is used during the planning phase to accelerate online computation. A trajectory smoothing phase, which leverages the differentially flat nature of quadrotor dynamics, is then implemented to guarantee a dynamically feasible trajectory. An event-based replanning structure is implemented to handle the case of dynamic, even adversarial, obstacles. A locally reactive control layer, inspired by potential fields methods, is added to the framework to help minimizes replanning events and produce graceful avoidance maneuvers in the presence of high speed obstacles.

    @phdthesis{Allen2016,
      author = {Allen, R.},
      title = {A Real-Time Framework for Kinodynamic Planning with Application to Quadrotor Obstacle Avoidance},
      school = {{Stanford University, Dept. of Aeronautics and Astronautics}},
      year = {2016},
      address = {Stanford, California},
      month = jun,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Allen.PhD16.pdf}
    }
    
  6. M. Pavone, “Dynamic Vehicle Routing for Robotic Networks,” PhD thesis, Massachusetts Inst. of Technology, Dept. of Aeronautics and Astronautics, Cambridge, MA, 2010.

    Abstract: Recent years have witnessed great advancements in the sciences and technology of autonomy, robotics and networking. This dissertation develops concepts and algorithms for dynamic vehicle routing (DVR), that is, for the automatic planning of optimal multi-vehicle routes to provide service to demands (or more generally to perform tasks) that are generated over time by an exogenous process. We consider a rich variety of scenarios relevant for robotic applications. We begin by reviewing some of the approaches available to tackle DVR problems. Next, we study different multi-vehicle scenarios based on different models for demands (in particular, demands with time constraints, demands with different priority levels, and demands that must be transported from a pick-up to a delivery location). The performance criterion used in these scenarios is either the expected waiting time of the demands or the fraction of demands serviced successfully. In each specific DVR scenario we adopt a rigorous technical approach, which we call algorithmic queueing theory and which relies upon methods from queueing theory, combinatorial optimization, and stochastic geometry. Algorithmic queueing theory consists of three basics steps: 1) queueing model of the DVR problem and analysis of its structure; 2) establishment of fundamental limitations on performance, independent of algorithms; and 3) design of algorithms that are either optimal or constant-factor away from optimal. In the second part of the dissertation, we address problems concerning the implementation of routing policies in large-scale robotic networks, such as adaptivity and decentralized computation. We first present distributed algorithms for environment partitioning, and then we apply them to devise routing policies for DVR problems that (i) are spatially distributed, scalable to large networks, and adaptive to network changes, and (ii) have remarkably good performance guarantees. The technical approach developed in this dissertation is applicable to a wide variety of DVR problems: several possible extensions are discussed throughout the thesis.

    @phdthesis{Pavone2010,
      author = {Pavone, M.},
      title = {Dynamic Vehicle Routing for Robotic Networks},
      school = {{Massachusetts Inst. of Technology, Dept. of Aeronautics and Astronautics}},
      year = {2010},
      address = {Cambridge, MA},
      month = jun,
      owner = {bylard},
      timestamp = {2017-01-28},
      url = {../wp-content/papercite-data/pdf/Pavone.Thesis.PHD.AA10.pdf}
    }