Viability Under Degraded Control Authority.

In this letter, we solve the problem of quantifying and mitigating control authority degradation in real time. Here, our target systems are controlled nonlinear affine-in-control evolution equations with finite control input and finite- or infinite-dimensional state. We consider two cases of control input degradation: finitely many affine maps acting on unknown disjoint subsets of the inputs and general Lipschitz continuous maps. These degradation modes are encountered in practice due to actuator wear and tear, hard locks on actuator ranges due to over-excitation, as well as more general changes in the control allocation dynamics. We derive sufficient conditions for identifiability of control authority degradation, and propose a novel real-time algorithm for identifying or approximating control degradation modes. We demonstrate our method on a nonlinear distributed parameter system, namely a one-dimensional heat equation with a velocity-controlled moveable heat source, motivated by autonomous energy-based surgery.

Explorative Probabilistic Planning with Unknown Target Locations.

Motion planning in an unknown environment demands synthesis of an optimal control policy that balances between exploration and exploitation. In this paper, we present the environment as a labeled graph where the labels of states are initially unknown, and consider a motion planning objective to fulfill a generalized reach-avoid specification given on these labels in minimum time. By describing the record of visited labels as an automaton, we translate our problem to a Canadian traveler problem on an adapted state space. We propose a strategy that enables the agent to perform its task by exploiting possible a priori knowledge about the labels and the environment and incrementally revealing the environment online. Namely, the agent plans, follows, and replans the optimal path by assigning edge weights that balance between exploration and exploitation, given the current knowledge of the environment. We illustrate our strategy on the setting of an agent operating on a two-dimensional grid environment.

Guaranteed Reachability for Systems with Unknown Dynamics.

The problem of computing the reachable set for a given system is a quintessential question in nonlinear control theory. Motivated by prior work on safety-critical online planning, this paper considers an environment where the only available information about system dynamics is that of dynamics at a single point. Limited to such knowledge, we study the problem of describing the set of all states that are guaranteed to be reachable regardless of the unknown true dynamics. We show that such a set can be underapproximated by a reachable set of a related known system whose dynamics at every state depend on the velocity vectors that are available in all control systems consistent with the assumed knowledge. Complementing the theory, we discuss a simple model of an aircraft in distress to verify that such an underapproximation is meaningful in practice.

Repulsion-Based p-Dispersion with Distance Constraints in Non-Convex Polygons.

Motivated by the question of optimal facility placement, the classical p-dispersion problem seeks to place a fixed number of equally sized non-overlapping circles of maximal possible radius into a subset of the plane. While exact solutions to this problem may be found for placement into particular sets, the problem is provably NP-complete for general sets, and existing work is largely restricted to geometrically simple sets. This paper makes two contributions to the theory of p-dispersion. First, we propose a computationally feasible suboptimal approach to the p-dispersion problem for all non-convex polygons. The proposed method, motivated by the mechanics of the p-body problem, considers circle centers as continuously moving objects in the plane and assigns repulsive forces between different circles, as well as circles and polygon boundaries, with magnitudes inversely proportional to the corresponding distances. Additionally, following the motivating application of optimal facility placement, we consider existence of additional hard upper or lower distance bounds on pairs of circle centers, and adapt the proposed method to provide a p-dispersion solution that provably respects such constraints. We validate our proposed method by comparing it with previous exact and approximate methods for p-dispersion. The method quickly produces near-optimal results for a number of containers.

Learning and Planning for Time-Varying MDPs Using Maximum Likelihood Estimation.

This paper proposes a formal approach to online learning and planning for agents operating in a priori unknown, time-varying environments. The proposed method computes the maximally likely model of the environment, given the observations about the environment made by an agent earlier in the system run and assuming knowledge of a bound on the maximal rate of change of system dynamics. Such an approach generalizes the estimation method commonly used in learning algorithms for unknown Markov decision processes with time-invariant transition probabilities, but is also able to quickly and correctly identify the system dynamics following a change. Based on the proposed method, we generalize the exploration bonuses used in learning for time-invariant Markov decision processes by introducing a notion of uncertainty in a learned time-varying model, and develop a control policy for time-varying Markov decision processes based on the exploitation and exploration trade-off. We demonstrate the proposed methods on four numerical examples: a patrolling task with a change in system dynamics, a two-state MDP with periodically changing outcomes of actions, a wind flow estimation task, and a multi-armed bandit problem with periodically changing probabilities of different rewards.

Optimal Routing in Stochastic Networks with Reliability Guarantees.

Optimal routing in highly congested street networks where the travel times are often stochastic is a challenging problem with significant practical interest. While most approaches to this problem use minimizing the expected travel time as the sole objective, such a solution is not always desired, especially when the variance of travel time is high. In this work, we pose the problem of finding a routing policy that minimizes the expected travel time under the hard constraint of retaining a specified probability of on-time arrival. Our approach to this problem models the stochastic travel time on each segment in the road network as a discrete random variable, thus translating the model of interest into a Markov decision process. Such a setting enables us to interpret the problem as a linear program. Our work also includes a case study on the street of Manhattan, New York where we constructed the model of travel times using real-world data, and employed our approach to generate optimal routing policies.

Online Inner Approximation of Reachable Sets of Nonlinear Systems with Diminished Control Authority.

This work presents a method of efficiently computing inner approximations of forward reachable sets for nonlinear control systems with diminished control authority, given an a priori computed reachable set for the nominal system. The method functions by shrinking a precomputed convex reachable set based on a priori knowledge of the system's trajectory deviation growth dynamics. The trajectory deviation growth dynamics determine an upper bound on the minimal deviation between two trajectories emanating from the same point that are generated by control inputs from the nominal and diminished set of control inputs, respectively. These growth dynamics are a function of a given Hausdorff distance bound between the nominal convex space of admissible controls and the possibly unknown impaired space of admissible controls. Because of its relative computational efficiency compared to direct computation of the off-nominal reachable set, this procedure can be applied to onboard fault-tolerant path planning and failure recovery. We consider the implementation of the approximation procedure by way of numerical integration and a root finding scheme, and we present two illustrative examples, namely an application to a control system with quadratic nonlinearities and aircraft wing rock dynamics.

Quantitative Resilience of Linear Driftless Systems.

This paper introduces the notion of quantitative resilience of a control system. Following prior work, we study linear driftless systems enduring a loss of control authority over some of their actuators. Such a malfunction results in actuators producing possibly undesirable inputs over which the controller has real-time readings but no control. By definition, a system is resilient if it can still reach a target after a partial loss of control authority. However, after a malfunction, a resilient system might be significantly slower to reach a target compared to its initial capabilities. We quantify this loss of performance through the new concept of quantitative resilience. We define such a metric as the maximal ratio of the minimal times required to reach any target for the initial and malfunctioning systems. Naïve computation of quantitative resilience directly from the definition is a complex task as it requires solving four nested, possibly nonlinear, optimization problems. The main technical contribution of this work is to provide an efficient method to compute quantitative resilience. Relying on control theory and on two novel geometric results we reduce the computation of quantitative resilience to a single linear optimization problem. We demonstrate our method on an opinion dynamics scenario.

Fuel in Markov Decision Processes (FiMDP): A Practical Approach to Consumption.

Consumption Markov Decision Processes (CMDPs) are probabilistic decision-making models of resource-constrained systems. We introduce FiMDP, a tool for controller synthesis in CMDPs with LTL objectives expressible by deterministic Büchi automata. The tool implements the recent algorithm for polynomial-time controller synthesis in CMDPs, but extends it with many additional features. On the conceptual level, the tool implements heuristics for improving the expected reachability times of accepting states, and a support for multi-agent task allocation. On the practical level, the tool offers (among other features) a new strategy simulation framework, integration with the Storm model checker, and FiMDPEnv - a new set of CMDPs that model real-world resource-constrained systems. We also present an evaluation of FiMDP on these real-world scenarios.

Safety-Guaranteed, Accelerated Learning in MDPs with Local Side Information.

In environments with uncertain dynamics, synthesis of optimal control policies mandates exploration. The applicability of classical learning algorithms to real-world problems is often limited by the number of time steps required for learning the environment model. Given some local side information about the differences in transition probabilities of the states, potentially obtained from the agent's onboard sensors, we generalize the idea of indirect sampling for accelerated learning to propose an algorithm that balances between exploration and exploitation. We formalize this idea by introducing the notion of the value of information in the context of a Markov decision process with unknown transition probabilities, as a measure of the expected improvement in the agent's current estimate of transition probabilities by taking a particular action. By exploiting available local side information and maximizing the estimated value of learned information at each time step, we accelerate the learning process and subsequent synthesis of the optimal control policy. Further, we define the notion of agent safety, a vital consideration for physical systems, in the context of our problem. Under certain assumptions, we provide guarantees on the safety of an agent exploring with our algorithm that exploits local side information. We illustrate agent safety and the improvement in learning speed using numerical experiments in the setting of a Mars rover, with data from onboard sensors acting as the local side information.

Resilient Reachability for Linear Systems.

A fault-tolerant system is able to reach its goal even when some of its components are malfunctioning. This paper examines tolerance to a specific type of malfunction: the loss of control authority over actuators. Namely, we investigate whether the desired target set for a linear system remains reachable under any undesirable input. Contrary to robust control, we assume that the undesirable inputs can be observed in real time, and subsequently allow the control inputs to depend on these undesirable inputs. Building on previous work on reachability with undesirable inputs, this paper develops a reachability condition for linear systems, and obtains a formula that describes reachability of the goal set for driftless linear systems by computing the minimum of a concave-convex objective function. From this formulation we establish two novel sufficient conditions for resilient reachability.

PROTRIP: Probabilistic Risk-Aware Optimal Transit Planner.

Optimal routing in urban transit networks, where variable congestion levels often lead to stochastic travel times, is usually studied with the least expected travel time (LET) as the performance criteria under the assumption of travel time independence on different road segments. However, a LET path might be subjected to high variability of travel time and therefore might not be desirable to transit users seeking a predictable arrival time. Further, there exists a spatial correlation in urban travel times due to the cascading effect of congestion across the road network. In this work, we propose a methodology and a tool that, given an origin-destination pair, a travel time budget, and a measure of the passenger's tolerance for uncertainty, provide the optimal online route choice in a transit network by balancing the objectives of maximizing on-time arrival probability and minimizing expected travel time. Our framework takes into account the correlation between travel time of different edges along a route and updates downstream distributions by taking advantage of upstream real-time information. We demonstrate the utility and performance of our algorithm with the help of realistic numerical experiments conducted on a fixed-route bus system that serves the residents of the Champaign-Urbana metropolitan area.