BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Emilio Frazzoli

Emilio Frazzoli contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Systems and ControlRoboticsmath.OCeess.SYmath.DSArtificial IntelligenceComputer Science and Game TheoryMultiagent Systemsnlin.AOmath.CAmath.PRComputationComputer VisionData Structures and Algorithmseess.SPFormal Languages and Automata TheoryLogic in Computer ScienceMachine Learningmath.CT

Trust snapshot

Quick read

Trust 21 - Emerging
59works
0followers
19topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

59 published item(s)

preprint2025arXiv

Reproducibility in the Control of Autonomous Mobility-on-Demand Systems

Autonomous Mobility-on-Demand (AMoD) systems, powered by advances in robotics, control, and Machine Learning (ML), offer a promising paradigm for future urban transportation. AMoD offers fast and personalized travel services by leveraging centralized control of autonomous vehicle fleets to optimize operations and enhance service performance. However, the rapid growth of this field has outpaced the development of standardized practices for evaluating and reporting results, leading to significant challenges in reproducibility. As AMoD control algorithms become increasingly complex and data-driven, a lack of transparency in modeling assumptions, experimental setups, and algorithmic implementation hinders scientific progress and undermines confidence in the results. This paper presents a systematic study of reproducibility in AMoD research. We identify key components across the research pipeline, spanning system modeling, control problems, simulation design, algorithm specification, and evaluation, and analyze common sources of irreproducibility. We survey prevalent practices in the literature, highlight gaps, and propose a structured framework to assess and improve reproducibility. Specifically, concrete guidelines are offered, along with a "reproducibility checklist", to support future work in achieving replicable, comparable, and extensible results. While focused on AMoD, the principles and practices we advocate generalize to a broader class of cyber-physical systems that rely on networked autonomy and data-driven control. This work aims to lay the foundation for a more transparent and reproducible research culture in the design and deployment of intelligent mobility systems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Compositional Controller Synthesis for Interconnected Stochastic Systems with Markovian Switching

In this work, we propose a compositional scheme for the safety controller synthesis of interconnected discrete-time stochastic systems with Markovian switching signals. Our proposed approach is based on a notion of so-called control storage certificates computed for individual subsystems, by leveraging which, one can synthesize state-feedback controllers for interconnected systems to enforce safety specifications over finite time horizons. To do so, we employ a sum-of-squares (SOS) optimization approach to search for multiple storage certificates of each switching subsystem while synthesizing its corresponding safety controller. We then utilize dissipativity theory to compositionally construct barrier certificates for interconnected systems based on storage certificates of individual subsystems. The proposed dissipativity-type compositional conditions can leverage the structure of the interconnection topology and be fulfilled independently of the number or gains of subsystems. We eventually employ the constructed barrier certificate and quantify upper bounds on the probability that the interconnected system reaches certain unsafe regions in a finite time horizon. We apply our results to a room temperature network of 200 rooms with Markovian switching signals while accepting multiple storage certificates. We compositionally synthesize safety controllers to maintain the temperature of each room in a comfort zone for a bounded time horizon.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Constructing MDP Abstractions Using Data with Formal Guarantees

This paper is concerned with a data-driven technique for constructing finite Markov decision processes (MDPs) as finite abstractions of discrete-time stochastic control systems with unknown dynamics while providing formal closeness guarantees. The proposed scheme is based on notions of stochastic bisimulation functions (SBF) to capture the probabilistic distance between state trajectories of an unknown stochastic system and those of finite MDP. In our proposed setting, we first reformulate corresponding conditions of SBF as a robust convex program (RCP). We then propose a scenario convex program (SCP) associated to the original RCP by collecting a finite number of data from trajectories of the system. We ultimately construct an SBF between the data-driven finite MDP and the unknown stochastic system with a given confidence level by establishing a probabilistic relation between optimal values of the SCP and the RCP. We also propose two different approaches for the construction of finite MDPs from data. We illustrate the efficacy of our results over a nonlinear jet engine compressor with unknown dynamics. We construct a data-driven finite MDP as a suitable substitute of the original system to synthesize controllers maintaining the system in a safe set with some probability of satisfaction and a desirable confidence level.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Data-Driven Synthesis of Symbolic Abstractions with Guaranteed Confidence

In this work, we propose a data-driven approach for the construction of finite abstractions (a.k.a., symbolic models) for discrete-time deterministic control systems with unknown dynamics. We leverage notions of so-called alternating bisimulation functions (ABF), as a relation between each unknown system and its symbolic model, to quantify the mismatch between state behaviors of two systems. Accordingly, one can employ our proposed results to perform formal verification and synthesis over symbolic models and then carry the results back over unknown original systems. In our data-driven setting, we first cast the required conditions for constructing ABF as a robust optimization program (ROP). Solving the provided ROP is not tractable due to the existence of unknown models in the constraints of ROP. To tackle this difficulty, we collect finite numbers of data from trajectories of unknown systems and propose a scenario optimization program (SOP) corresponding to the original ROP. By establishing a probabilistic relation between optimal values of SOP and ROP, we formally construct ABF between unknown systems and their symbolic models based on the number of data and a required confidence level. We verify the effectiveness of our data-driven results over two physical case studies with unknown models including (i) a DC motor and (ii) a nonlinear jet engine compressor. We construct symbolic models from data as appropriate substitutes of original systems and synthesize policies maintaining states of unknown systems in a safe set within infinite time horizons with some guaranteed confidence levels.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Formal Estimation of Collision Risks for Autonomous Vehicles: A Compositional Data-Driven Approach

In this work, we propose a compositional data-driven approach for the formal estimation of collision risks for autonomous vehicles (AVs) while acting in a stochastic multi-agent framework. The proposed approach is based on the construction of sub-barrier certificates for each stochastic agent via a set of data collected from its trajectories while providing an a-priori guaranteed confidence on the data-driven estimation. In our proposed setting, we first cast the original collision risk problem for each agent as a robust optimization program (ROP). Solving the acquired ROP is not tractable due to an unknown model that appears in one of its constraints. To tackle this difficulty, we collect finite numbers of data from trajectories of each agent and provide a scenario optimization program (SOP) corresponding to the original ROP. We then establish a probabilistic bridge between the optimal value of SOP and that of ROP, and accordingly, we formally construct the sub-barrier certificate for each unknown agent based on the number of data and a required level of confidence. We then propose a compositional technique based on small-gain reasoning to quantify the collision risk for multi-agent AVs with some desirable confidence based on sub-barrier certificates of individual agents constructed from data. For the case that the proposed compositionality conditions are not satisfied, we provide a relaxed version of compositional results without requiring any compositionality conditions but at the cost of providing a potentially conservative collision risk. Eventually, we also present our approaches for non-stochastic multi-agent AVs. We demonstrate the effectiveness of our proposed results by applying them to a vehicle platooning consisting of 100 vehicles with 1 leader and 99 followers. We formally estimate the collision risk by collecting data from trajectories of each agent.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

nuReality: A VR environment for research of pedestrian and autonomous vehicle interactions

We present nuReality, a virtual reality 'VR' environment designed to test the efficacy of vehicular behaviors to communicate intent during interactions between autonomous vehicles 'AVs' and pedestrians at urban intersections. In this project we focus on expressive behaviors as a means for pedestrians to readily recognize the underlying intent of the AV's movements. VR is an ideal tool to use to test these situations as it can be immersive and place subjects into these potentially dangerous scenarios without risk. nuReality provides a novel and immersive virtual reality environment that includes numerous visual details (road and building texturing, parked cars, swaying tree limbs) as well as auditory details (birds chirping, cars honking in the distance, people talking). In these files we present the nuReality environment, its 10 unique vehicle behavior scenarios, and the Unreal Engine and Autodesk Maya source files for each scenario. The files are publicly released as open source at www.nuReality.org, to support the academic community studying the critical AV-pedestrian interaction.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Safety Barrier Certificates for Stochastic Hybrid Systems

This work is concerned with the safety controller synthesis of stochastic hybrid systems, in which continuous evolutions are described by stochastic differential equations with both Brownian motions and Poisson processes, and instantaneous jumps are governed by stochastic difference equations with additive noises. Our proposed framework leverages the notion of control barrier certificates (CBC), as a discretization-free approach, to synthesize safety controllers for stochastic hybrid systems while providing safety guarantees in finite time horizons. In our proposed scheme, we first provide an augmented framework to characterize each stochastic hybrid system containing continuous evolutions and instantaneous jumps with a unified system covering both scenarios. We then introduce an augmented control barrier certificate (ACBC) for augmented systems and propose sufficient conditions to construct an ACBC based on CBC of original hybrid systems. By utilizing the constructed ACBC, we quantify upper bounds on the probability that the stochastic hybrid system reaches certain unsafe regions in a finite time horizon. The proposed approach is verified over a nonlinear case study.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Co-Design of Autonomous Systems: From Hardware Selection to Control Synthesis

Designing cyber-physical systems is a complex task which requires insights at multiple abstraction levels. The choices of single components are deeply interconnected and need to be jointly studied. In this work, we consider the problem of co-designing the control algorithm as well as the platform around it. In particular, we leverage a monotone theory of co-design to formalize variations of the LQG control problem as monotone feasibility relations. We then show how this enables the embedding of control co-design problems in the higher level co-design problem of a robotic platform. We illustrate the properties of our formalization by analyzing the co-design of an autonomous drone performing search-and-rescue tasks and show how, given a set of desired robot behaviors, we can compute Pareto efficient design solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On the Co-Design of AV-Enabled Mobility Systems

The design of autonomous vehicles (AVs) and the design of AV-enabled mobility systems are closely coupled. Indeed, knowledge about the intended service of AVs would impact their design and deployment process, whilst insights about their technological development could significantly affect transportation management decisions. This calls for tools to study such a coupling and co-design AVs and AV-enabled mobility systems in terms of different objectives. In this paper, we instantiate a framework to address such co-design problems. In particular, we leverage the recently developed theory of co-design to frame and solve the problem of designing and deploying an intermodal Autonomous Mobility-on-Demand system, whereby AVs service travel demands jointly with public transit, in terms of fleet sizing, vehicle autonomy, and public transit service frequency. Our framework is modular and compositional, allowing one to describe the design problem as the interconnection of its individual components and to tackle it from a system-level perspective. To showcase our methodology, we present a real-world case study for Washington D.C., USA. Our work suggests that it is possible to create user-friendly optimization tools to systematically assess costs and benefits of interventions, and that such analytical techniques might gain a momentous role in policy-making in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Posetal Games: Efficiency, Existence, and Refinement of Equilibria in Games with Prioritized Metrics

Modern applications require robots to comply with multiple, often conflicting rules and to interact with the other agents. We present Posetal Games as a class of games in which each player expresses a preference over the outcomes via a partially ordered set of metrics. This allows one to combine hierarchical priorities of each player with the interactive nature of the environment. By contextualizing standard game theoretical notions, we provide two sufficient conditions on the preference of the players to prove existence of pure Nash Equilibria in finite action sets. Moreover, we define formal operations on the preference structures and link them to a refinement of the game solutions, showing how the set of equilibria can be systematically shrunk. The presented results are showcased in a driving game where autonomous vehicles select from a finite set of trajectories. The results demonstrate the interpretability of results in terms of minimum-rank-violation for each player.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Rule-based Optimal Control for Autonomous Driving

We develop optimal control strategies for Autonomous Vehicles (AVs) that are required to meet complex specifications imposed by traffic laws and cultural expectations of reasonable driving behavior. We formulate these specifications as rules, and specify their priorities by constructing a priority structure. We propose a recursive framework, in which the satisfaction of the rules in the priority structure are iteratively relaxed based on their priorities. Central to this framework is an optimal control problem, where convergence to desired states is achieved using Control Lyapunov Functions (CLFs), and safety is enforced through Control Barrier Functions (CBFs). We also show how the proposed framework can be used for after-the-fact, pass / fail evaluation of trajectories - a given trajectory is rejected if we can find a controller producing a trajectory that leads to less violation of the rule priority structure. We present case studies with multiple driving scenarios to demonstrate the effectiveness of the proposed framework.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Compositional Sheaf-Theoretic Framework for Event-Based Systems (Extended Version)

A compositional sheaf-theoretic framework for the modeling of complex event-based systems is presented. We show that event-based systems are machines, with inputs and outputs, and that they can be composed with machines of different types, all within a unified, sheaf-theoretic formalism. We take robotic systems as an exemplar of complex systems and rigorously describe actuators, sensors, and algorithms using this framework.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Integrated Benchmarking and Design for Reproducible and Accessible Evaluation of Robotic Agents

As robotics matures and increases in complexity, it is more necessary than ever that robot autonomy research be reproducible. Compared to other sciences, there are specific challenges to benchmarking autonomy, such as the complexity of the software stacks, the variability of the hardware and the reliance on data-driven techniques, amongst others. In this paper, we describe a new concept for reproducible robotics research that integrates development and benchmarking, so that reproducibility is obtained "by design" from the beginning of the research/development processes. We first provide the overall conceptual objectives to achieve this goal and then a concrete instance that we have built: the DUCKIENet. One of the central components of this setup is the Duckietown Autolab, a remotely accessible standardized setup that is itself also relatively low-cost and reproducible. When evaluating agents, careful definition of interfaces allows users to choose among local versus remote evaluation using simulation, logs, or remote automated hardware setups. We validate the system by analyzing the repeatability of experiments conducted using the infrastructure and show that there is low variance across different robot hardware and across different remote labs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Revisiting the Asymptotic Optimality of RRT$^*$

RRT* is one of the most widely used sampling-based algorithms for asymptotically-optimal motion planning. This algorithm laid the foundations for optimality in motion planning as a whole, and inspired the development of numerous new algorithms in the field, many of which build upon RRT* itself. In this paper, we first identify a logical gap in the optimality proof of RRT*, which was developed in Karaman and Frazzoli (2011). Then, we present an alternative and mathematically-rigorous proof for asymptotic optimality. Our proof suggests that the connection radius used by RRT* should be increased from $γ\left(\frac{\log n}{n}\right)^{1/d}$ to $γ' \left(\frac{\log n}{n}\right)^{1/(d+1)}$ in order to account for the additional dimension of time that dictates the samples' ordering. Here $γ$, $γ'$, are constants, and $n$, $d$, are the number of samples and the dimension of the problem, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Towards a Co-Design Framework for Future Mobility Systems

The design of Autonomous Vehicles (AVs) and the design of AVs-enabled mobility systems are closely coupled. Indeed, knowledge about the intended service of AVs would impact their design and deployment process, whilst insights about their technological development could significantly affect transportation management decisions. This calls for tools to study such a coupling and co-design AVs and AVs-enabled mobility systems in terms of different objectives. In this paper, we instantiate a framework to address such co-design problems. In particular, we leverage the recently developed theory of co-design to frame and solve the problem of designing and deploying an intermodal Autonomous Mobility-on-Demand system, whereby AVs service travel demands jointly with public transit, in terms of fleet sizing, vehicle autonomy, and public transit service frequency. Our framework is modular and compositional, allowing to describe the design problem as the interconnection of its individual components and to tackle it from a system-level perspective. Moreover, it only requires very general monotonicity assumptions and it naturally handles multiple objectives, delivering the rational solutions on the Pareto front and thus enabling policy makers to select a solution through political criteria. To showcase our methodology, we present a real-world case study for Washington D.C., USA. Our work suggests that it is possible to create user-friendly optimization tools to systematically assess the costs and benefits of interventions, and that such analytical techniques might gain a momentous role in policy-making in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles

Self-driving vehicles are a maturing technology with the potential to reshape mobility by enhancing the safety, accessibility, efficiency, and convenience of automotive transportation. Safety-critical tasks that must be executed by a self-driving vehicle include planning of motions through a dynamic environment shared with other vehicles and pedestrians, and their robust executions via feedback control. The objective of this paper is to survey the current state of the art on planning and control algorithms with particular regard to the urban setting. A selection of proposed techniques is reviewed along with a discussion of their effectiveness. The surveyed approaches differ in the vehicle mobility model used, in assumptions on the structure of the environment, and in computational requirements. The side-by-side comparison presented in this survey helps to gain insight into the strengths and limitations of the reviewed approaches and assists with system level design choices.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Design of Admissible Heuristics for Kinodynamic Motion Planning via Sum-of-Squares Programming

How does one obtain an admissible heuristic for a kinodynamic motion planning problem? This paper develops the analytical tools and techniques to answer this question. A sufficient condition for the admissibility of a heuristic is presented which can be checked directly from the problem data. This condition is also used to formulate a concave program to optimize an admissible heuristic. This optimization is then approximated and solved in polynomial time using sum-of-squares programming techniques. A number of examples are provided to demonstrate these concepts.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

POMDP-lite for Robust Robot Planning under Uncertainty

The partially observable Markov decision process (POMDP) provides a principled general model for planning under uncertainty. However, solving a general POMDP is computationally intractable in the worst case. This paper introduces POMDP-lite, a subclass of POMDPs in which the hidden state variables are constant or only change deterministically. We show that a POMDP-lite is equivalent to a set of fully observable Markov decision processes indexed by a hidden parameter and is useful for modeling a variety of interesting robotic tasks. We develop a simple model-based Bayesian reinforcement learning algorithm to solve POMDP-lite models. The algorithm performs well on large-scale POMDP-lite models with up to $10^{20}$ states and outperforms the state-of-the-art general-purpose POMDP algorithms. We further show that the algorithm is near-Bayesian-optimal under suitable conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Provably Safe and Deadlock-Free Execution of Multi-Robot Plans under Delaying Disturbances

One of the standing challenges in multi-robot systems is the ability to reliably coordinate motions of multiple robots in environments where the robots are subject to disturbances. We consider disturbances that force the robot to temporarily stop and delay its advancement along its planned trajectory which can be used to model, e.g., passing-by humans for whom the robots have to yield. Although reactive collision-avoidance methods are often used in this context, they may lead to deadlocks between robots. We design a multi-robot control strategy for executing coordinated trajectories computed by a multi-robot trajectory planner and give a proof that the strategy is safe and deadlock-free even when robots are subject to delaying disturbances. Our simulations show that the proposed strategy scales significantly better with the intensity of disturbances than the naive liveness-preserving approach. The empirical results further confirm that the proposed approach is more reliable and also more efficient than state-of-the-art reactive techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Selection of Input Primitives for the Generalized Label Correcting Method

The generalized label correcting method is an efficient search-based approach to trajectory optimization. It relies on a finite set of control primitives that are concatenated into candidate control signals. This paper investigates the principled selection of this set of control primitives. Emphasis is placed on a particularly challenging input space geometry, the $n$-dimensional sphere. We propose using controls which minimize a generalized energy function and discuss the optimization technique used to obtain these control primitives. A numerical experiment is presented showing a factor of two improvement in running time when using the optimized control primitives over a random sampling strategy.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Set-Point Regulation of Linear Continuous-Time Systems using Neuromorphic Vision Sensors

Recently developed neuromorphic vision sensors have become promising candidates for agile and autonomous robotic applications primarily due to, in particular, their high temporal resolution and low latency. Each pixel of this sensor independently fires an asynchronous stream of "retinal events" once a change in the light field is detected. Existing computer vision algorithms can only process periodic frames and so a new class of algorithms needs to be developed that can efficiently process these events for control tasks. In this paper, we investigate the problem of regulating a continuous-time linear time invariant (LTI) system to a desired point using measurements from a neuromorphic sensor. We present an $H_\infty$ controller that regulates the LTI system to a desired set-point and provide the set of neuromorphic sensor based cameras for the given system that fulfill the regulation task. The effectiveness of our approach is illustrated on an unstable system.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Simultaneous Input and State Estimation for Linear Time-Varying Continuous-Time Stochastic Systems

In this paper, we present an optimal filter for linear time-varying continuous-time stochastic systems that simultaneously estimates the states and unknown inputs in an unbiased minimum-variance sense. We first show that the unknown inputs cannot be estimated without additional assumptions. Then, we discuss two complementary variants of the filter: (i) for the case when an additional measurement containing information about the state derivative is available, and (ii) for the case without the additional measurement but the input signals are assumed to be sufficiently smooth and have bounded derivatives. Conditions for uniform asymptotic stability and the existence of a steady-state solution for the proposed filter, as well as the convergence rate of the state and input estimate biases are given. Moreover, we show that a principle of separation of estimation and control holds and that the unknown inputs may be rejected. Two examples, including a nonlinear vehicle reentry example, are given to illustrate that our filter is applicable even when some strong assumptions do not hold.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Simultaneous Mode, Input and State Estimation for Switched Linear Stochastic Systems

In this paper, we propose a filtering algorithm for simultaneously estimating the mode, input and state of hidden mode switched linear stochastic systems with unknown inputs. Using a multiple-model approach with a bank of linear input and state filters for each mode, our algorithm relies on the ability to find the most probable model as a mode estimate, which we show is possible with input and state filters by identifying a key property, that a particular residual signal we call generalized innovation is a Gaussian white noise. We also provide an asymptotic analysis for the proposed algorithm and provide sufficient conditions for asymptotically achieving convergence to the true model (consistency), or to the 'closest' model according to an information-theoretic measure (convergence). A simulation example of intention-aware vehicles at an intersection is given to demonstrate the effectiveness of our approach.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Martingale Approach and Time-Consistent Sampling-based Algorithms for Risk Management in Stochastic Optimal Control

In this paper, we consider a class of stochastic optimal control problems with risk constraints that are expressed as bounded probabilities of failure for particular initial states. We present here a martingale approach that diffuses a risk constraint into a martingale to construct time-consistent control policies. The martingale stands for the level of risk tolerance over time. By augmenting the system dynamics with the controlled martingale, the original risk-constrained problem is transformed into a stochastic target problem. We extend the incremental Markov Decision Process (iMDP) algorithm to approximate arbitrarily well an optimal feedback policy of the original problem by sampling in the augmented state space and computing proper boundary conditions for the reformulated problem. We show that the algorithm is both probabilistically sound and asymptotically optimal. The performance of the proposed algorithm is demonstrated on motion planning and control problems subject to bounded probability of collision in uncertain cluttered environments.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Distributed robust adaptive equilibrium computation for generalized convex games

This paper considers a class of generalized convex games where each player is associated with a convex objective function, a convex inequality constraint and a convex constraint set. The players aim to compute a Nash equilibrium through communicating with neighboring players. The particular challenge we consider is that the component functions are unknown a priori to associated players. We study two distributed computation algorithms and analyze their convergence properties in the presence of data transmission delays and dynamic changes of network topologies. The algorithm performance is verified through demand response on the IEEE 30-bus Test System. Our technical tools integrate convex analysis, variational inequalities and simultaneous perturbation stochastic approximation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Planning for Optimal Feedback Control in the Volume of Free Space

The problem of optimal feedback planning among obstacles in d-dimensional configuration spaces is considered. We present a sampling-based, asymptotically optimal feedback planning method. Our method combines an incremental construction of the Delaunay triangulation, volumetric collision-detection module, and a modified Fast Marching Method to compute a converging sequence of feedback functions. The convergence and asymptotic runtime are proven theoretically and investigated during numerical experiments, in which the proposed method is compared with the state-of-the-art asymptotically optimal path planners. The results show that our method is competitive with the previous algorithms. Unlike the shortest trajectory computed by many path planning algorithms, the resulting feedback functions can be used directly for robot navigation in our case. Finally, we present a straightforward extension of our method that handles dynamic environments where obstacles can appear, disappear, or move.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Unified Filter for Simultaneous Input and State Estimation of Linear Discrete-time Stochastic Systems

In this paper, we present a unified optimal and exponentially stable filter for linear discrete-time stochastic systems that simultaneously estimates the states and unknown inputs in an unbiased minimum-variance sense, without making any assumptions on the direct feedthrough matrix. We also derive input and state observability/detectability conditions, and analyze their connection to the convergence and stability of the estimator. We discuss two variations of the filter and their optimality and stability properties, and show that filters in the literature, including the Kalman filter, are special cases of the filter derived in this paper. Finally, illustrative examples are given to demonstrate the performance of the unified unbiased minimum-variance filter.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Back-pressure traffic signal control with unknown routing rates

The control of a network of signalized intersections is considered. Previous works proposed a feedback control belonging to the family of the so-called back-pressure controls that ensures provably maximum stability given pre-specified routing probabilities. However, this optimal back-pressure controller (BP*) requires routing rates and a measure of the number of vehicles queuing at a node for each possible routing decision. It is an idealistic assumption for our application since vehicles (going straight, turning left/right) are all gathered in the same lane apart from the proximity of the intersection and cameras can only give estimations of the aggregated queue length. In this paper, we present a back-pressure traffic signal controller (BP) that does not require routing rates, it requires only aggregated queue lengths estimation (without direction information) and loop detectors at the stop line for each possible direction. A theoretical result on the Lyapunov drift in heavy load conditions under BP control is provided and tends to indicate that BP should have good stability properties. Simulations confirm this and show that BP stabilizes the queuing network in a significant part of the capacity region.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Capacity-aware back-pressure traffic signal control

The control of a network of signalized intersections is considered. Previous work demonstrates that the so-called back-pressure control provides stability guarantees, assuming infinite queues capacities. In this paper, we highlight the failing of current back-pressure control under finite capacities by identifying sources of non work-conservation and congestion propagation. We propose the use of a normalized pressure which guarantees work conservation and mitigates congestion propagation, while ensuring fairness at low traffic densities, and recovering original back-pressure as capacities grow to infinity. This capacity-aware back-pressure control allows to improve performance as congestion increases, as indicated by simulation results, and keeps the key benefits of back-pressure: ability to be distributed over intersections and O(1) complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Game theoretic controller synthesis for multi-robot motion planning Part I : Trajectory based algorithms

We consider a class of multi-robot motion planning problems where each robot is associated with multiple objectives and decoupled task specifications. The problems are formulated as an open-loop non-cooperative differential game. A distributed anytime algorithm is proposed to compute a Nash equilibrium of the game. The following properties are proven: (i) the algorithm asymptotically converges to the set of Nash equilibrium; (ii) for scalar cost functionals, the price of stability equals one; (iii) for the worst case, the computational complexity and communication cost are linear in the robot number.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Minimum-time Paths of Bounded Curvature with Position-dependent Constraints

We consider the problem of a particle traveling from an initial configuration to a final configuration (given by a point in the plane along with a prescribed velocity vector) in minimum time with non-homogeneous velocity and with constraints on the minimum turning radius of the particle over multiple regions of the state space. Necessary conditions for optimality of these paths are derived to characterize the nature of optimal paths, both when the particle is inside a region and when it crosses boundaries between neighboring regions. These conditions are used to characterize families of optimal and nonoptimal paths. Among the optimality conditions, we derive a "refraction" law at the boundary of the regions that generalizes the so-called Snell's law of refraction in optics to the case of paths with bounded curvature. Tools employed to deduce our results include recent principles of optimality for hybrid systems. The results are validated numerically.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Throughput Optimal Distributed Traffic Signal Control

We propose a distributed algorithm for controlling traffic signals, allowing constraints such as periodic switching sequences of phases and minimum and maximum green time to be incorporated. Our algorithm is adapted from backpressure routing, which has been mainly applied to communication and power networks. We formally prove that our algorithm ensures global optimality as it leads to maximum network throughput even though the controller is constructed and implemented in a completely distributed manner.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An Explicit Formulation of the Earth Movers Distance with Continuous Road Map Distances

The Earth movers distance (EMD) is a measure of distance between probability distributions which is at the heart of mass transportation theory. Recent research has shown that the EMD plays a crucial role in studying the potential impact of Demand-Responsive Transportation (DRT) and Mobility-on-Demand (MoD) systems, which are growing paradigms for one-way vehicle sharing where people drive (or are driven by) shared vehicles from a point of origin to a point of destination. While the ubiquitous physical transportation setting is the road network, characterized by systems of roads connected together by interchanges, most analytical works about vehicle sharing represent distances between points in a plane using the simple Euclidean metric. Instead, we consider the EMD when the ground metric is taken from a class of one-dimensional, continuous metric spaces, reminiscent of road networks. We produce an explicit formulation of the Earth movers distance given any finite road network R. The result generalizes the EMD with a Euclidean R1 ground metric, which had remained one of the only known non-discrete cases with an explicit formula. Our formulation casts the EMD as the optimal value of a finite-dimensional, real-valued optimization problem, with a convex objective function and linear constraints. In the special case that the input distributions have piece-wise uniform (constant) density, the problem reduces to one whose objective function is convex quadratic. Both forms are amenable to modern mathematical programming techniques.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An O(M log M) Algorithm for Bipartite Matching with Roadmap Distances

An algorithm is presented which produces the minimum cost bipartite matching between two sets of M points each, where the cost of matching two points is proportional to the minimum distance by which a particle could reach one point from the other while constrained to travel on a connected set of curves, or roads. Given any such roadmap, the algorithm obtains O(M log M) total runtime in terms of M, which is the best possible bound in the sense that any algorithm for minimal matching has runtime Omega(M log M). The algorithm is strongly polynomial and is based on a capacity-scaling approach to the [minimum] convex cost flow problem. The result generalizes the known Theta(M log M) complexity of computing optimal matchings between two sets of points on (i) a line segment, and (ii) a circle.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Anytime computation algorithms for approach-evasion differential games

This paper studies a class of approach-evasion differential games, in which one player aims to steer the state of a dynamic system to the given target set in minimum time, while avoiding some set of disallowed states, and the other player desires to achieve the opposite. We propose a class of novel anytime computation algorithms, analyze their convergence properties and verify their performance via a number of numerical simulations. Our algorithms significantly outperform the multi-grid method for the approach-evasion differential games both theoretically and numerically. Our technical approach leverages incremental sampling in robotic motion planning and viability theory.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fast Collision Checking: From Single Robots to Multi-Robot Teams

We examine three different algorithms that enable the collision certificate method from [Bialkowski, et al.] to handle the case of a centralized multi-robot team. By taking advantage of symmetries in the configuration space of multi-robot teams, our methods can significantly reduce the number of collision checks vs. both [Bialkowski, et al.] and standard collision checking implementations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Incremental Sampling-based Algorithm for Minimum-violation Motion Planning

This paper studies the problem of control strategy synthesis for dynamical systems with differential constraints to fulfill a given reachability goal while satisfying a set of safety rules. Particular attention is devoted to goals that become feasible only if a subset of the safety rules are violated. The proposed algorithm computes a control law, that minimizes the level of unsafety while the desired goal is guaranteed to be reached. This problem is motivated by an autonomous car navigating an urban environment while following rules of the road such as "always travel in right lane'' and "do not change lanes frequently''. Ideas behind sampling based motion-planning algorithms, such as Probabilistic Road Maps (PRMs) and Rapidly-exploring Random Trees (RRTs), are employed to incrementally construct a finite concretization of the dynamics as a durational Kripke structure. In conjunction with this, a weighted finite automaton that captures the safety rules is used in order to find an optimal trajectory that minimizes the violation of safety rules. We prove that the proposed algorithm guarantees asymptotic optimality, i.e., almost-sure convergence to optimal solutions. We present results of simulation experiments and an implementation on an autonomous urban mobility-on-demand system.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Minimum-violation LTL Planning with Conflicting Specifications

We consider the problem of automatic generation of control strategies for robotic vehicles given a set of high-level mission specifications, such as "Vehicle x must eventually visit a target region and then return to a base," "Regions A and B must be periodically surveyed," or "None of the vehicles can enter an unsafe region." We focus on instances when all of the given specifications cannot be reached simultaneously due to their incompatibility and/or environmental constraints. We aim to find the least-violating control strategy while considering different priorities of satisfying different parts of the mission. Formally, we consider the missions given in the form of linear temporal logic formulas, each of which is assigned a reward that is earned when the formula is satisfied. Leveraging ideas from the automata-based model checking, we propose an algorithm for finding an optimal control strategy that maximizes the sum of rewards earned if this control strategy is applied. We demonstrate the proposed algorithm on an illustrative case study.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Real-time game theoretic coordination of competitive mobility-on-demand systems

This paper considers competitive mobility-on-demand systems where a group of vehicle sharing companies, on one hand, want to collectively regulate the traffic of the user queueing network, and on the other hand, maximize their own profits at each time instant. We formulate the strategic interconnection among the companies as a real-time game theoretic coordination problem. We propose an algorithm to achieve vehicle balance and practical regulation of the user queueing network. We quantify the relation between the regulation error and the system parameters (e.g., the maximum variation of the user arrival rates).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Rebalancing the Rebalancers: Optimally Routing Vehicles and Drivers in Mobility-on-Demand Systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A GPS Pseudorange Based Cooperative Vehicular Distance Measurement Technique

Accurate vehicular localization is important for various cooperative vehicle safety (CVS) applications such as collision avoidance, turning assistant, etc. In this paper, we propose a cooperative vehicular distance measurement technique based on the sharing of GPS pseudorange measurements and a weighted least squares method. The classic double difference pseudorange solution, which was originally designed for high-end survey level GPS systems, is adapted to low-end navigation level GPS receivers for its wide availability in ground vehicles. The Carrier to Noise Ratio (CNR) of raw pseudorange measurements are taken into account for noise mitigation. We present a Dedicated Short Range Communications (DSRC) based mechanism to implement the exchange of pseudorange information among neighboring vehicles. As demonstrated in field tests, our proposed technique increases the accuracy of the distance measurement significantly compared with the distance obtained from the GPS fixes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An Incremental Sampling-based Algorithm for Stochastic Optimal Control

In this paper, we consider a class of continuous-time, continuous-space stochastic optimal control problems. Building upon recent advances in Markov chain approximation methods and sampling-based algorithms for deterministic path planning, we propose a novel algorithm called the incremental Markov Decision Process (iMDP) to compute incrementally control policies that approximate arbitrarily well an optimal policy in terms of the expected cost. The main idea behind the algorithm is to generate a sequence of finite discretizations of the original problem through random sampling of the state space. At each iteration, the discretized problem is a Markov Decision Process that serves as an incrementally refined model of the original problem. We show that with probability one, (i) the sequence of the optimal value functions for each of the discretized problems converges uniformly to the optimal value function of the original stochastic optimal control problem, and (ii) the original optimal value function can be computed efficiently in an incremental manner using asynchronous value iterations. Thus, the proposed algorithm provides an anytime approach to the computation of optimal control policies of the continuous problem. The effectiveness of the proposed approach is demonstrated on motion planning and control problems in cluttered environments in the presence of process noise.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Asymptotically Optimal Algorithms for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems

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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Control of Probabilistic Systems under Dynamic, Partially Known Environments with Temporal Logic Specifications

We consider the synthesis of control policies for probabilistic systems, modeled by Markov decision processes, operating in partially known environments with temporal logic specifications. The environment is modeled by a set of Markov chains. Each Markov chain describes the behavior of the environment in each mode. The mode of the environment, however, is not known to the system. Two control objectives are considered: maximizing the expected probability and maximizing the worst-case probability that the system satisfies a given specification.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Distributed Traffic Signal Control for Maximum Network Throughput

We propose a distributed algorithm for controlling traffic signals. Our algorithm is adapted from backpressure routing, which has been mainly applied to communication and power networks. We formally prove that our algorithm ensures global optimality as it leads to maximum network throughput even though the controller is constructed and implemented in a completely distributed manner. Simulation results show that our algorithm significantly outperforms SCATS, an adaptive traffic signal control system that is being used in many cities.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

High-speed Flight in an Ergodic Forest

Inspired by birds flying through cluttered environments such as dense forests, this paper studies the theoretical foundations of a novel motion planning problem: high-speed navigation through a randomly-generated obstacle field when only the statistics of the obstacle generating process are known a priori. Resembling a planar forest environment, the obstacle generating process is assumed to determine the locations and sizes of disk-shaped obstacles. When this process is ergodic, and under mild technical conditions on the dynamics of the bird, it is shown that the existence of an infinite collision-free trajectory through the forest exhibits a phase transition. On one hand, if the bird flies faster than a certain critical speed, then, with probability one, there is no infinite collision-free trajectory, i.e., the bird will eventually collide with some tree, almost surely, regardless of the planning algorithm governing the bird's motion. On the other hand, if the bird flies slower than this critical speed, then there exists at least one infinite collision-free trajectory, almost surely. Lower and upper bounds on the critical speed are derived for the special case of a homogeneous Poisson forest considering a simple model for the bird's dynamics. For the same case, an equivalent percolation model is provided. Using this model, the phase diagram is approximated in Monte-Carlo simulations. This paper also establishes novel connections between robot motion planning and statistical physics through ergodic theory and percolation theory, which may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Incremental Temporal Logic Synthesis of Control Policies for Robots Interacting with Dynamic Agents

We consider the synthesis of control policies from temporal logic specifications for robots that interact with multiple dynamic environment agents. Each environment agent is modeled by a Markov chain whereas the robot is modeled by a finite transition system (in the deterministic case) or Markov decision process (in the stochastic case). Existing results in probabilistic verification are adapted to solve the synthesis problem. To partially address the state explosion issue, we propose an incremental approach where only a small subset of environment agents is incorporated in the synthesis procedure initially and more agents are successively added until we hit the constraints on computational resources. Our algorithm runs in an anytime fashion where the probability that the robot satisfies its specification increases as the algorithm progresses.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Foraging of Renewable Resources

Consider a team of agents in the plane searching for and visiting target points that appear in a bounded environment according to a stochastic renewal process with a known absolutely continuous spatial distribution. Agents must detect targets with limited-range onboard sensors. It is desired to minimize the expected waiting time between the appearance of a target point, and the instant it is visited. When the sensing radius is small, the system time is dominated by time spent searching, and it is shown that the optimal policy requires the agents to search a region at a relative frequency proportional to the square root of its renewal rate. On the other hand, when targets appear frequently, the system time is dominated by time spent servicing known targets, and it is shown that the optimal policy requires the agents to service a region at a relative frequency proportional to the cube root of its renewal rate. Furthermore, the presented algorithms in this case recover the optimal performance achieved by agents with full information of the environment. Simulation results verify the theoretical performance of the algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Road Pricing for Spreading Peak Travel: Modeling and Design

A case study of the Singapore road network provides empirical evidence that road pricing can significantly affect commuter trip timing behaviors. In this paper, we propose a model of trip timing decisions that reasonably matches the observed commuters' behaviors. Our model explicitly captures the difference in individuals' sensitivity to price, travel time and early or late arrival at destination. New pricing schemes are suggested to better spread peak travel and reduce traffic congestion. Simulation results based on the proposed model are provided in comparison with the real data for the Singapore case study.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Robust Distributed Routing in Dynamical Networks with Cascading Failures

Robustness of routing policies for networks is a central problem which is gaining increased attention with a growing awareness to safeguard critical infrastructure networks against natural and man-induced disruptions. Routing under limited information and the possibility of cascades through the network adds serious challenges to this problem. This abstract considers the framework of dynamical networks introduced in our earlier work [1,2], where the network is modeled by a system of ordinary differential equations derived from mass conservation laws on directed acyclic graphs with a single origin-destination pair and a constant inflow at the origin. The rate of change of the particle density on each link of the network equals the difference between the inflow and the outflow on that link. The latter is modeled to depend on the current particle density on that link through a flow function. The novel modeling element in this paper is that every link is assumed to have finite capacity for particle density and that the flow function is modeled to be strictly increasing as density increases from zero up to the maximum density capacity, and is discontinuous at the maximum density capacity, with the flow function value being zero at that point. This feature, in particular, allows for the possibility of spill-backs in our model. In this paper, we present our results on resilience of such networks under distributed routing, towards perturbations that reduce link-wise flow functions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Statistics and Predictability of Go-Arounds

This paper takes an empirical approach to identify operational factors at busy airports that may predate go-around maneuvers. Using four years of data from San Francisco International Airport, we begin our investigation with a statistical approach to investigate which features of airborne, ground operations (e.g., number of inbound aircraft, number of aircraft taxiing from gate, etc.) or weather are most likely to fluctuate, relative to nominal operations, in the minutes immediately preceding a missed approach. We analyze these findings both in terms of their implication on current airport operations and discuss how the antecedent factors may affect NextGen. Finally, as a means to assist air traffic controllers, we draw upon techniques from the machine learning community to develop a preliminary alert system for go-around prediction.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Robust Distributed Routing in Dynamical Flow Networks - Part I: Locally Responsive Policies and Weak Resilience

Robustness of distributed routing policies is studied for dynamical flow networks, with respect to adversarial disturbances that reduce the link flow capacities. A dynamical flow network is modeled as a system of ordinary differential equations derived from mass conservation laws on a directed acyclic graph with a single origin-destination pair and a constant inflow at the origin. Routing policies regulate the way the inflow at a non-destination node gets split among its outgoing links as a function of the current particle density, while the outflow of a link is modeled to depend on the current particle density on that link through a flow function. The dynamical flow network is called partially transferring if the total inflow at the destination node is asymptotically bounded away from zero, and its weak resilience is measured as the minimum sum of the link-wise magnitude of all disturbances that make it not partially transferring. The weak resilience of a dynamical flow network with arbitrary routing policy is shown to be upper-bounded by the network's min-cut capacity, independently of the initial flow conditions. Moreover, a class of distributed routing policies that rely exclusively on local information on the particle densities, and are locally responsive to that, is shown to yield such maximal weak resilience. These results imply that locality constraints on the information available to the routing policies do not cause loss of weak resilience. Some fundamental properties of dynamical flow networks driven by locally responsive distributed policies are analyzed in detail, including global convergence to a unique limit flow.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Robust Distributed Routing in Dynamical Flow Networks - Part II: Strong Resilience, Equilibrium Selection and Cascaded Failures

Strong resilience properties of dynamical flow networks are analyzed for distributed routing policies. The latter are characterized by the property that the way the inflow at a non-destination node gets split among its outgoing links is allowed to depend only on local information about the current particle densities on the outgoing links. The strong resilience of the network is defined as the infimum sum of link-wise flow capacity reductions under which the network cannot maintain the asymptotic total inflow to the destination node to be equal to the inflow at the origin. A class of distributed routing policies that are locally responsive to local information is shown to yield the maximum possible strong resilience under such local information constraints for an acyclic dynamical flow network with a single origin-destination pair. The maximal strong resilience achievable is shown to be equal to the minimum node residual capacity of the network. The latter depends on the limit flow of the unperturbed network and is defined as the minimum, among all the non-destination nodes, of the sum, over all the links outgoing from the node, of the differences between the maximum flow capacity and the limit flow of the unperturbed network. We propose a simple convex optimization problem to solve for equilibrium limit flows of the unperturbed network that minimize average delay subject to strong resilience guarantees, and discuss the use of tolls to induce such an equilibrium limit flow in transportation networks. Finally, we present illustrative simulations to discuss the connection between cascaded failures and the resilience properties of the network.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Sampling-based Algorithms for Optimal Motion Planning

During the last decade, sampling-based path planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g., as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g., showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e., such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Stability Analysis of Transportation Networks with Multiscale Driver Decisions

Stability of Wardrop equilibria is analyzed for dynamical transportation networks in which the drivers' route choices are influenced by information at multiple temporal and spatial scales. The considered model involves a continuum of indistinguishable drivers commuting between a common origin/destination pair in an acyclic transportation network. The drivers' route choices are affected by their, relatively infrequent, perturbed best responses to global information about the current network congestion levels, as well as their instantaneous local observation of the immediate surroundings as they transit through the network. A novel model is proposed for the drivers' route choice behavior, exhibiting local consistency with their preference toward globally less congested paths as well as myopic decisions in favor of locally less congested paths. The simultaneous evolution of the traffic congestion on the network and of the aggregate path preference is modeled by a system of coupled ordinary differential equations. The main result shows that, if the frequency of updates of path preferences is sufficiently small as compared to the frequency of the traffic flow dynamics, then the state of the transportation network ultimately approaches a neighborhood of the Wardrop equilibrium. The presented results may be read as a further evidence in support of Wardrop's postulate of equilibrium, showing robustness of it with respect to non-persistent perturbations. The proposed analysis combines techniques from singular perturbation theory, evolutionary game theory, and cooperative dynamical systems.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Incremental Sampling-based Algorithms for Optimal Motion Planning

During the last decade, incremental sampling-based motion planning algorithms, such as the Rapidly-exploring Random Trees (RRTs) have been shown to work well in practice and to possess theoretical guarantees such as probabilistic completeness. However, no theoretical bounds on the quality of the solution obtained by these algorithms have been established so far. The first contribution of this paper is a negative result: it is proven that, under mild technical conditions, the cost of the best path in the RRT converges almost surely to a non-optimal value. Second, a new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path in the RRG converges to the optimum almost surely. Third, a tree version of RRG is introduced, called the RRT$^*$ algorithm, which preserves the asymptotic optimality of RRG while maintaining a tree structure like RRT. The analysis of the new algorithms hinges on novel connections between sampling-based motion planning algorithms and the theory of random geometric graphs. In terms of computational complexity, it is shown that the number of simple operations required by both the RRG and RRT$^*$ algorithms is asymptotically within a constant factor of that required by RRT.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Maximally Stabilizing Task Release Control Policy for a Dynamical Queue

In this paper, we introduce a model of dynamical queue, in which the service time depends on the server utilization history. The proposed queueing model is motivated by widely accepted empirical laws describing human performance as a function of mental arousal. The objective of this paper is to design task release control policies that can stabilize the queue for the maximum possible arrival rate, assuming deterministic arrivals. First, we prove an upper bound on the maximum possible stabilizable arrival rate for any task release control policy. Then, we propose a simple threshold policy that releases a task to the server only if its state is below a certain fixed value. Finally, we prove that this task release control policy ensures stability of the queue for the maximum possible arrival rate.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Distributed and Adaptive Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment

In this paper we present distributed and adaptive algorithms for motion coordination of a group of m autonomous vehicles. The vehicles operate in a convex environment with bounded velocity and must service demands whose time of arrival, location and on-site service are stochastic; the objective is to minimize the expected system time (wait plus service) of the demands. The general problem is known as the m-vehicle Dynamic Traveling Repairman Problem (m-DTRP). The best previously known control algorithms rely on centralized a-priori task assignment and are not robust against changes in the environment, e.g. changes in load conditions; therefore, they are of limited applicability in scenarios involving ad-hoc networks of autonomous vehicles operating in a time-varying environment. First, we present a new class of policies for the 1-DTRP problem that: (i) are provably optimal both in light- and heavy-load condition, and (ii) are adaptive, in particular, they are robust against changes in load conditions. Second, we show that partitioning policies, whereby the environment is partitioned among the vehicles and each vehicle follows a certain set of rules in its own region, are optimal in heavy-load conditions. Finally, by combining the new class of algorithms for the 1-DTRP with suitable partitioning policies, we design distributed algorithms for the m-DTRP problem that (i) are spatially distributed, scalable to large networks, and adaptive to network changes, (ii) are within a constant-factor of optimal in heavy-load conditions and stabilize the system in any load condition. Simulation results are presented and discussed.

0 citations0 reviewsNo code linkedOpen access