Search

We analyze best response dynamics for finding a Nash equilibrium of an infinite horizon zero-sum stochastic linear quadratic dynamic game (LQDG) with partial and asymmetric information. We derive explicit expressions for each player's best response within the class of pure linear dynamic output feedback control strategies where the internal state dimension of each control strategy is an integer multiple of the system state dimension. With each best response, the players form increasingly higher-order belief states, leading to infinite-dimensional internal states. However, we observe in extensive numerical experiments that the game's value converges after just a few iterations, suggesting that strategies associated with increasingly higher-order belief states eventually provide no benefit. To help explain this convergence, our numerical analysis reveals rapid decay of the controllability and observability Gramian eigenvalues and Hankel singular values in higher-order belief dynamics, indicating that the higher-order belief dynamics become increasingly difficult for both players to control and observe. Consequently, the higher-order belief dynamics can be closely approximated by low-order belief dynamics with bounded error, and thus feedback strategies with limited internal state dimension can closely approximate a Nash equilibrium.

A new surveillance-evasion differential game is posed and solved in which an agile pursuer (the prying pedestrian) seeks to remain within a given surveillance range of a less agile evader that aims to escape. In contrast to previous surveillance-evasion games, the pursuer is agile in the sense of being able to instantaneously change the direction of its velocity vector, whilst the evader is constrained to have a finite maximum turn rate. Both the game of kind concerned with conditions under which the evader can escape, and the game of degree concerned with the evader seeking to minimize the escape time whilst the pursuer seeks to maximize it, are considered. The game-of-degree solution is surprisingly complex compared to solutions to analogous pursuit-evasion games with an agile pursuer since it exhibits dependence on the ratio of the pursuer's speed to the evader's speed. It is, however, surprisingly simple compared to solutions to classic surveillance-evasion games with a turn-limited pursuer.

We propose a design for a functional programming language for autonomous agents, built off the ideas and motivations of Behavior Trees (BTs). BTs are a popular model for designing agents behavior in robotics and AI. However, as their growth has increased dramatically, the simple model of BTs has come to be limiting. There is a growing push to increase the functionality of BTs, with the end goal of BTs evolving into a programming language in their own right, centred around the defining BT properties of modularity and reactiveness. In this paper, we examine how the BT model must be extended in order to grow into such a language. We identify some fundamental problems which must be solved: implementing `reactive' selection, 'monitoring' safety-critical conditions, and passing data between actions. We provide a variety of small examples which demonstrate that these problems are complex, and that current BT approaches do not handle them in a manner consistent with modularity. We instead provide a simple set of modular programming primitives for handling these use cases, and show how they can be combined to build complex programs. We present a full specification for our BT-inspired language, and give an implementation in the functional programming language Haskell. Finally, we demonstrate our language by translating a large and complex BT into a simple, unambiguous program.

In this paper, we develop an online optimization algorithm for solving a class of nonconvex optimization problems with a linearly varying optimal point. The global convergence of the algorithm is guaranteed using the circle criterion for the class of functions whose gradient is bounded within a sector. Also, we show that the corresponding Lur\'e-type nonlinear system involves a double integrator, which demonstrates its ability to track a linearly varying optimal point with zero steady-state error. The algorithm is applied to solving a time-of-arrival based localization problem with constant velocity and the results show that the algorithm is able to estimate the source location with zero steady-state error., Comment: 8 pages, 7 figures, submitted to 2025 American Control Conference

In this paper, we quantify voltage and current phasor-based measurement requirements for the unique identification of the electric grid topology and admittance parameters. Our approach is underpinned by the concept of a rigidity matrix that has been extensively studied in graph rigidity theory. Specifically, we show that the rank of the rigidity matrix is the same as that of a voltage coefficient matrix in a corresponding electric power system. Accordingly, we show that there is a minimum number of measurements required to uniquely identify the admittance matrix and corresponding grid topology. By means of a numerical example on the IEEE 4-node radial network, we demonstrate that our approach is suitable for applications in electric power grids.

Visual Place Recognition (VPR) systems often have imperfect performance, affecting the `integrity' of position estimates and subsequent robot navigation decisions. Previously, SVM classifiers have been used to monitor VPR integrity. This research introduces a novel Multi-Layer Perceptron (MLP) integrity monitor which demonstrates improved performance and generalizability, removing per-environment training and reducing manual tuning requirements. We test our proposed system in extensive real-world experiments, presenting two real-time integrity-based VPR verification methods: a single-query rejection method for robot navigation to a goal zone (Experiment 1); and a history-of-queries method that takes a best, verified, match from its recent trajectory and uses an odometer to extrapolate a current position estimate (Experiment 2). Noteworthy results for Experiment 1 include a decrease in aggregate mean along-track goal error from ~9.8m to ~3.1m, and an increase in the aggregate rate of successful mission completion from ~41% to ~55%. Experiment 2 showed a decrease in aggregate mean along-track localization error from ~2.0m to ~0.5m, and an increase in the aggregate localization precision from ~97% to ~99%. Overall, our results demonstrate the practical usefulness of a VPR integrity monitor in real-world robotics to improve VPR localization and consequent navigation performance., Comment: Author Accepted Preprint for Robotics and Automation Letters

Recent research has shown that quasar-convexity can be found in applications such as identification of linear dynamical systems and generalized linear models. Such observations have in turn spurred exciting developments in design and analysis algorithms that exploit quasar-convexity. In this work, we study the online stochastic quasar-convex optimization problems in a dynamic environment. We establish regret bounds of online gradient descent in terms of cumulative path variation and cumulative gradient variance for losses satisfying quasar-convexity and strong quasar-convexity. We then apply the results to generalized linear models (GLM) when the underlying parameter is time-varying. We establish regret bounds of online gradient descent when applying to GLMs with leaky ReLU activation function, logistic activation function, and ReLU activation function. Numerical results are presented to corroborate our findings.

The application of a zeroth-order scheme for minimising Polyak-\L{}ojasewicz (PL) functions is considered. The framework is based on exploiting a random oracle to estimate the function gradient. The convergence of the algorithm to a global minimum in the unconstrained case and to a neighbourhood of the global minimum in the constrained case along with their corresponding complexity bounds are presented. The theoretical results are demonstrated via numerical examples.

We formulate a mathematical framework for designing a self-tuning network control architecture, and propose a computationally-feasible greedy algorithm for online architecture optimization. In this setting, the locations of active sensors and actuators in the network, as well as the feedback control policy are jointly adapted using all available information about the network states and dynamics to optimize a performance criterion. We show that the case with full-state feedback can be solved with dynamic programming, and in the linear-quadratic setting, the optimal cost functions and policies are piecewise quadratic and piecewise linear, respectively. Our framework is extended for joint sensor and actuator selection for dynamic output feedback control with both control performance and architecture costs. For large networks where exhaustive architecture search is prohibitive, we describe a greedy heuristic for actuator selection and propose a greedy swapping algorithm for joint sensor and actuator selection. Via numerical experiments, we demonstrate a dramatic performance improvement of greedy self-tuning architectures over fixed architectures. Our general formulation provides an extremely rich and challenging problem space with opportunities to apply a wide variety of approximation methods from stochastic control, system identification, reinforcement learning, and static architecture design for practical model-based control., Comment: 12 pages, submitted to IEEE-TCNS. arXiv admin note: text overlap with arXiv:2301.06699

This paper addresses the problem of nonconvex nonsmooth decentralised optimisation in multi-agent networks with undirected connected communication graphs. Our contribution lies in introducing an algorithmic framework designed for the distributed minimisation of the sum of a smooth (possibly nonconvex and non-separable) function and a convex (possibly nonsmooth and non-separable) regulariser. The proposed algorithm can be seen as a modified version of the ADMM algorithm where, at each step, an "inner loop" needs to be iterated for a number of iterations. The role of the inner loop is to aggregate and disseminate information across the network. We observe that a naive decentralised approach (one iteration of the inner loop) may not converge. We establish the asymptotic convergence of the proposed algorithm to the set of stationary points of the nonconvex problem where the number of iterations of the inner loop increases logarithmically with the step count of the ADMM algorithm. We present numerical results demonstrating the proposed method's correctness and performance., Comment: 6 pages, 1 Figure

In this work, we consider a sequence of stochastic optimization problems following a time-varying distribution via the lens of online optimization. Assuming that the loss function satisfies the Polyak-{\L}ojasiewicz condition, we apply online stochastic gradient descent and establish its dynamic regret bound that is composed of cumulative distribution drifts and cumulative gradient biases caused by stochasticity. The distribution metric we adopt here is Wasserstein distance, which is well-defined without the absolute continuity assumption or with a time-varying support set. We also establish a regret bound of online stochastic proximal gradient descent when the objective function is regularized. Moreover, we show that the above framework can be applied to the Conditional Value-at-Risk (CVaR) learning problem. Particularly, we improve an existing proof on the discovery of the PL condition of the CVaR problem, resulting in a regret bound of online stochastic gradient descent.

An important challenge in the online convex optimization (OCO) setting is to incorporate generalized inequalities and time-varying constraints. The inclusion of constraints in OCO widens the applicability of such algorithms to dynamic and safety-critical settings such as the online optimal power flow (OPF) problem. In this work, we propose the first projection-free OCO algorithm admitting time-varying linear constraints and convex generalized inequalities: the online interior-point method for time-varying equality constraints (OIPM-TEC). We derive simultaneous sublinear dynamic regret and constraint violation bounds for OIPM-TEC under standard assumptions. For applications where a given tolerance around optima is accepted, we employ an alternative OCO performance metric -- the epsilon-regret -- and a more computationally efficient algorithm, the epsilon-OIPM-TEC, that possesses sublinear bounds under this metric. Finally, we showcase the performance of these two algorithms on an online OPF problem and compare them to another OCO algorithm from the literature.

This paper presents a Visual Inertial Odometry Landmark-based Simultaneous Localisation and Mapping algorithm based on a distributed block coordinate nonlinear Moving Horizon Estimation scheme. The main advantage of the proposed method is that the updates on the position of the landmarks are based on a Bundle Adjustment technique that can be parallelised over the landmarks. The performance of the method is demonstrated in simulations in different environments and with different types of robot trajectory. Circular and wiggling patterns in the trajectory lead to better estimation performance than straight ones, confirming what is expected from recent nonlinear observability theory.

This paper proposes an algorithm that combines Fast Moving Horizon Parameter Estimation and Model Predictive Control subject to an observability constraint designed to ensure a lower bound on the performance of the parameter estimator. Output-feedback stability is proved through input-to-state stability of the state/error system under a small noise and initial error assumption. Numerical experiments have been carried out in the case of Active Simultaneous Localisation and Mapping (SLAM).

In this paper, we propose and analyze a new method for online linear quadratic regulator (LQR) control with a priori unknown time-varying cost matrices. The cost matrices are revealed sequentially with the potential for future values to be previewed over a short window. Our novel method involves using the available cost matrices to predict the optimal trajectory, and a tracking controller to drive the system towards it. We adopted the notion of dynamic regret to measure the performance of this proposed online LQR control method, with our main result being that the (dynamic) regret of our method is upper bounded by a constant. Moreover, the regret upper bound decays exponentially with the preview window length, and is extendable to systems with disturbances. We show in simulations that our proposed method offers improved performance compared to other previously proposed online LQR methods., Comment: Submitted to L4DC2023

In this paper we characterise the long-run behaviour of the replicator dynamic in zero-sum games (symmetric or non-symmetric). Specifically, we prove that every zero-sum game possesses a unique global replicator attractor, which we then characterise. Most surprisingly, this attractor depends only on each player's preference order over their own strategies and not on the cardinal payoff values, defined by a finite directed graph we call the game's preference graph. When the game is symmetric, this graph is a tournament whose nodes are strategies; when the game is not symmetric, this graph is the game's response graph. We discuss the consequences of our results on chain recurrence and Nash equilibria., Comment: 17 pages, 2 figures. Accepted version, to appear at ALT 2024

We formulate a general mathematical framework for self-tuning network control architecture design. This problem involves jointly adapting the locations of active sensors and actuators in the network and the feedback control policy to all available information about the time-varying network state and dynamics to optimize a performance criterion. We propose a general solution structure analogous to the classical self-tuning regulator from adaptive control. We show that a special case with full-state feedback can be solved in principle with dynamic programming, and in the linear quadratic setting the optimal cost functions and policies are piecewise quadratic and piecewise linear, respectively. For large networks where exhaustive architecture search is prohibitive, we describe a greedy heuristic for joint architecture-policy design. We demonstrate in numerical experiments that self-tuning architectures can provide dramatically improved performance over fixed architectures. Our general formulation provides an extremely rich and challenging problem space with opportunities to apply a wide variety of approximation methods from stochastic control, system identification, reinforcement learning, and static architecture design., Comment: 6 pages, 5 figures

The success of deep learning over the past decade mainly relies on gradient-based optimisation and backpropagation. This paper focuses on analysing the performance of first-order gradient-based optimisation algorithms, gradient descent and proximal gradient, with time-varying non-convex cost function under (proximal) Polyak-{\L}ojasiewicz condition. Specifically, we focus on using the forward mode of automatic differentiation to compute gradients in the fast-changing problems where calculating gradients using the backpropagation algorithm is either impossible or inefficient. Upper bounds for tracking and asymptotic errors are derived for various cases, showing the linear convergence to a solution or a neighbourhood of an optimal solution, where the convergence rate decreases with the increase in the dimension of the problem. We show that for a solver with constraints on computing resources, the number of forward gradient iterations at each step can be a design parameter that trades off between the tracking performance and computing constraints., Comment: 18 pages, 1 figure

We investigate the problem of finding paths that enable a robot modeled as a Dubins car (i.e., a constant-speed finite-turn-rate unicycle) to escape from a circular region of space in minimum time. This minimum-time escape problem arises in marine, aerial, and ground robotics in situations where a safety region has been violated and must be exited before a potential negative consequence occurs (e.g., a collision). Using the tools of nonlinear optimal control theory, we show that a surprisingly simple closed-form feedback control law solves this minimum-time escape problem, and that the minimum-time paths have an elegant geometric interpretation., Comment: 7 pages, 5 figures, accepted for 12th IFAC Symposium on Nonlinear Control Systems (NOLCOS)

In this paper we examine the relationship between the flow of the replicator dynamic, the continuum limit of Multiplicative Weights Update, and a game's response graph. We settle an open problem establishing that under the replicator, sink chain components -- a topological notion of long-run outcome of a dynamical system -- always exist and are approximated by the sink connected components of the game's response graph. More specifically, each sink chain component contains a sink connected component of the response graph, as well as all mixed strategy profiles whose support consists of pure profiles in the same connected component, a set we call the content of the connected component. As a corollary, all profiles are chain recurrent in games with strongly connected response graphs. In any two-player game sharing a response graph with a zero-sum game, the sink chain component is unique. In two-player zero-sum and potential games the sink chain components and sink connected components are in a one-to-one correspondence, and we conjecture that this holds in all games., Comment: 22 pages, 2 figures. Accepted version. To appear in Algorithmic Learning Theory 2023

In this paper we analyse two-player games by their response graphs. The response graph has nodes which are strategy profiles, with an arc between profiles if they differ in the strategy of a single player, with the direction of the arc indicating the preferred option for that player. Response graphs, and particularly their sink strongly connected components, play an important role in modern techniques in evolutionary game theory and multi-agent learning. We show that the response graph is a simple and well-motivated model of strategic interaction which captures many non-trivial properties of a game, despite not depending on cardinal payoffs. We characterise the games which share a response graph with a zero-sum or potential game respectively, and demonstrate a duality between these sets. This allows us to understand the influence of these properties on the response graph. The response graphs of Matching Pennies and Coordination are shown to play a key role in all two-player games: every non-iteratively-dominated strategy takes part in a subgame with these graph structures. As a corollary, any game sharing a response graph with both a zero-sum game and potential game must be dominance-solvable. Finally, we demonstrate our results on some larger games., Comment: 16 pages, 11 figures

In this letter, we consider the problem of field estimation using binary measurements. Previous work has formulated the problem as a parameter estimation problem, with the parameter estimation carried out in an online manner using sequential Monte Carlo techniques. In the current work, we consider an alternative approach to the parameter estimation based on online logistic regression. The developed algorithm is less computationally intensive than the sequential Monte Carlo approach, while having more reliable estimation performance.

We propose a robust data-driven output feedback control algorithm that explicitly incorporates inherent finite-sample model estimate uncertainties into the control design. The algorithm has three components: (1) a subspace identification nominal model estimator; (2) a bootstrap resampling method that quantifies non-asymptotic variance of the nominal model estimate; and (3) a non-conventional robust control design method comprising a coupled optimal dynamic output feedback filter and controller with multiplicative noise. A key advantage of the proposed approach is that the system identification and robust control design procedures both use stochastic uncertainty representations, so that the actual inherent statistical estimation uncertainty directly aligns with the uncertainty the robust controller is being designed against. Moreover, the control design method accommodates a highly structured uncertainty representation that can capture uncertainty shape more effectively than existing approaches. We show through numerical experiments that the proposed robust data-driven output feedback controller can significantly outperform a certainty equivalent controller on various measures of sample complexity and stability robustness.

A Metric Interval Temporal Logic (MITL) verification algorithm is presented. It verifies continuous-time signals without relying on high frequency sampling. Instead, it is assumed that collections of over- and under-approximating intervals are available for the times at which the individual atomic propositions hold true for a given signal. These are combined inductively to generate corresponding over- and under-approximations for the specified MITL formula. The gap between the over- and under-approximations reflects timing uncertainty with respect to the signal being verified, thereby providing a quantitative measure of the conservativeness of the algorithm. The verification is exact when the over-approximations for the atomic propositions coincide with the under-approximations. Numerical examples are provided to illustrate., Comment: To appear in proceedings of FORMATS 2022

Motivated by the recent interest in risk-aware control, we study a continuous-time control synthesis problem to bound the risk that a stochastic linear system violates a given specification. We use risk signal temporal logic as a specification formalism in which distributionally robust risk predicates are considered and equipped with the usual Boolean and temporal operators. Our control approach relies on reformulating these risk predicates as deterministic predicates over mean and covariance states of the system. We then obtain a timed sequence of sets of mean and covariance states from the timed automata representation of the specification. To avoid an explosion in the number of automata states, we propose heuristics to find candidate sequences effectively. To execute and check dynamic feasibility of these sequences, we present a sampled-data control technique based on time discretization and constraint tightening that allows to perform timed transitions while satisfying the continuous-time constraints., Comment: 8 pages, 4 figures, contributed paper at the 2022 American Control Conference (ACC) in Atlanta, GA

With advances in image processing and machine learning, it is now feasible to incorporate semantic information into the problem of simultaneous localisation and mapping (SLAM). Previously, SLAM was carried out using lower level geometric features (points, lines, and planes) which are often view-point dependent and error prone in visually repetitive environments. Semantic information can improve the ability to recognise previously visited locations, as well as maintain sparser maps for long term SLAM applications. However, SLAM in repetitive environments has the critical problem of assigning measurements to the landmarks which generated them. In this paper, we use k-best assignment enumeration to compute marginal assignment probabilities for each measurement landmark pair, in real time. We present numerical studies on the KITTI dataset to demonstrate the effectiveness and speed of the proposed framework., Comment: 6 Pages, 3 figures, submitted to Robotics and Automation Letters and the IROS 2020 conference

In this letter we revisit the famous heavy ball method and study its global convergence for a class of non-convex problems with sector-bounded gradient. We characterize the parameters that render the method globally convergent and yield the best $R$-convergence factor. We show that for this family of functions, this convergence factor is superior to the factor obtained from the triple momentum method., Comment: 6 pages, 4 figures, to appear in CSS Letters

This paper considers the problem of online optimization where the objective function is time-varying. In particular, we extend coordinate descent type algorithms to the online case, where the objective function varies after a finite number of iterations of the algorithm. Instead of solving the problem exactly at each time step, we only apply a finite number of iterations at each time step. Commonly used notions of regret are used to measure the performance of the online algorithm. Moreover, coordinate descent algorithms with different updating rules are considered, including both deterministic and stochastic rules that are developed in the literature of classical offline optimization. A thorough regret analysis is given for each case. Finally, numerical simulations are provided to illustrate the theoretical results., Comment: Accepted for publication in Automatica

Robust autonomy stacks require tight integration of perception, motion planning, and control layers, but these layers often inadequately incorporate inherent perception and prediction uncertainties, either ignoring them altogether or making questionable assumptions of Gaussianity. Robots with nonlinear dynamics and complex sensing modalities operating in an uncertain environment demand more careful consideration of how uncertainties propagate across stack layers. We propose a framework to integrate perception, motion planning, and control by explicitly incorporating perception and prediction uncertainties into planning so that risks of constraint violation can be mitigated. Specifically, we use a nonlinear model predictive control based steering law coupled with a decorrelation scheme based Unscented Kalman Filter for state and environment estimation to propagate the robot state and environment uncertainties. Subsequently, we use distributionally robust risk constraints to limit the risk in the presence of these uncertainties. Finally, we present a layered autonomy stack consisting of a nonlinear steering-based distributionally robust motion planning module and a reference trajectory tracking module. Our numerical experiments with nonlinear robot models and an urban driving simulator show the effectiveness of our proposed approaches., Comment: arXiv admin note: text overlap with arXiv:2002.02928

In this paper, we consider the optimisation of a time varying scalar field by a network of agents with no gradient information. We propose a composite control law, blending extremum seeking with formation control in order to converge to the extrema faster by minimising the gradient estimation error. By formalising the relationship between the formation and the gradient estimation error, we provide a novel analysis to prove the convergence of the network to a bounded neighbourhood of the field's time varying extrema. We assume the time-varying field satisfies the Polyak Lojasiewicz inequality and the gradient is Lipschitz continuous at each iteration. Numerical studies and comparisons are provided to support the theoretical results., Comment: 13 pages, 6 figures, submitted to Automatica

In this paper we develop an analogue of the graph-theoretic `modular decomposition' in automata theory. This decomposition allows us to identify hierarchical finite state machines (HFSMs) equivalent to a given finite state machine (FSM). We first define a module of an FSM, which is a collection of nodes which can be treated as a nested FSM. We then identify a natural subset of FSM modules called thin modules, which are algebraically well-behaved. We construct a linear-space directed graph, which uniquely represents every thin module, and hence every equivalent (thin) HFSM. We call this graph the modular decomposition. The modular decomposition makes clear the significant common structure underlying equivalent HFSMs, and allows us to efficiently construct equivalent HFSMs. Finally, we provide an $O(n^2k)$ algorithm for constructing the modular decomposition of an $n$-state $k$-symbol FSM., Comment: 28 pages, 5 figures. This version shortens and restructures the paper

A learning-based safety filter is developed for discrete-time linear time-invariant systems with unknown models subject to Gaussian noises with unknown covariance. Safety is characterized using polytopic constraints on the states and control inputs. The empirically learned model and process noise covariance with their confidence bounds are used to construct a robust optimization problem for minimally modifying nominal control actions to ensure safety with high probability. The optimization problem relies on tightening the original safety constraints. The magnitude of the tightening is larger at the beginning since there is little information to construct reliable models, but shrinks with time as more data becomes available.

Recent studies on encrypted control using homomorphic encryption allow secure operation by directly performing computations on encrypted data without decryption. Implementing dynamic controllers on encrypted data presents unique challenges due to limitations on the number of operations on an encrypted message. Hence, it may not be possible to perform the recursive operations for an infinite time horizon. In this note, we demonstrate that it is possible to run a dynamic controller over encrypted data for an infinite time horizon if the output of the controller can be represented as a function of a fixed number of previous inputs and outputs. The presented implementation requires encryption at both input and output of the plant. We identify a class of nonlinear systems that can accommodate the proposed implementation. The closed-loop performance can be guaranteed using the proposed encrypted controller by ensuring that quantization error is made arbitrarily small with appropriate choice of parameters. We show that the proposed method is amenable to linear systems (as a subset of the said nonlinear systems) with performance guarantees., Comment: 3 pages, previously presented at the 21st IFAC World Congress, 2020

This paper provides a zeroth-order optimisation framework for non-smooth and possibly non-convex cost functions with matrix parameters that are real and symmetric. We provide complexity bounds on the number of iterations required to ensure a given accuracy level for both the convex and non-convex case. The derived complexity bounds for the convex case are less conservative than available bounds in the literature since we exploit the symmetric structure of the underlying matrix space. Moreover, the non-convex complexity bounds are novel for the class of optimisation problems we consider. The utility of the framework is evident in the suite of applications that use symmetric matrices as tuning parameters. Of primary interest here is the challenge of tuning the gain matrices in model predictive controllers, as this is a challenge known to be inhibiting industrial implementation of these architectures. To demonstrate the framework we consider the problem of MIMO diesel air-path control, and consider implementing the framework iteratively ``in-the-loop'' to reduce tracking error on the output channels. Both simulations and experimental results are included to illustrate the effectiveness of the proposed framework over different engine drive cycles., Comment: 27 pages, 11 figures

Reusable decoys offer a cost-effective alternative to the single-use hardware commonly applied to protect surface assets from threats. Such decoys portray fake assets to lure threats away from the true asset. To deceive a threat, a decoy first has to position itself such that it can break the radar lock. Considering multiple simultaneous threats, this paper introduces an approach for controlling multiple decoys to minimise the time required to break the locks of all the threats. The method includes the optimal allocation of one decoy to every threat with an assignment procedure that provides local position constraints to guarantee collision avoidance and thereby decouples the control of the decoys. A crude model of a decoy with uncertainty is considered for motion planning. The task of a decoy reaching a state in which the lock of the assigned threat can be broken is formulated as a temporal logic specification. To this end, the requirements to complete the task are modelled as time-varying set-membership constraints. The temporal and logical combination of the constraints is encoded in a mixed-integer optimisation problem. To demonstrate the results a simulated case study is provided.

We study the success probability for a variant of the secretary problem, with noisy observations and multiple offline selection. Our formulation emulates, and is motivated by, problems involving noisy selection arising in the disciplines of stochastic simulation and simulation-based optimisation. In addition, we employ the philosophy of ordinal optimisation - involving an ordinal selection rule, and a percentile notion of goal softening for the success probability. As a result, it is shown that the success probability only depends on the underlying copula of the problem. Other general properties for the success probability are also presented. Specialising to the case of Gaussian copulas, we also derive an analytic lower bound for the success probability, which may then be inverted to find sufficiently large sample sizes that guarantee a high success probability arbitrarily close to one., Comment: 10 pages plus 9 pages of appendices

In this paper, we study spline trajectory generation via the solution of two optimisation problems: (i) a quadratic program (QP) with linear equality constraints and (ii) a nonlinear and nonconvex optimisation program. We propose an efficient algorithm to solve (i), which we then leverage to use in an iterative algorithm to solve (ii). Both the first algorithm and each iteration of the second algorithm have linear computational complexity in the number of spline segments. The scaling of each algorithm is such that we are able to solve the two problems faster than state-of-the-art methods and in times amenable to real-time trajectory generation requirements. The trajectories we generate are applicable to differentially flat systems, a broad class of mechanical systems, which we demonstrate by planning trajectories for a quadrotor., Comment: 11 pages, 5 figures, to be submitted to IEEE Transactions on Robotics

This paper formalises the concepts of weakly and weakly regularly persistent input trajectory as well as their link to the Observability Grammian and the existence and uniqueness of solutions of Moving Horizon Estimation (MHE) problems. Additionally, thanks to a new time-uniform Implicit Function Theorem, these notions are proved to imply the stability of MHE solutions with respect to small additive perturbation in the measurements and in the dynamics, both uniformly and non-uniformly in time. Finally, examples and counter-examples of weakly persistent and weakly regularly persistent input trajectories are given in the case of 2D bearing-only navigation.

This paper concerns the verification of continuous-time polynomial spline trajectories against linear temporal logic specifications (LTL without 'next'). Each atomic proposition is assumed to represent a state space region described by a multivariate polynomial inequality. The proposed approach samples a trajectory strategically, to capture every one of its region transitions. This yields a discrete word called a trace, which is amenable to established formal methods for path checking. The original continuous-time trajectory is shown to satisfy the specification if and only if its trace does. General topological conditions on the sample points are derived that ensure a trace is recorded for arbitrary continuous paths, given arbitrary region descriptions. Using techniques from computer algebra, a trace generation algorithm is developed to satisfy these conditions when the path and region boundaries are defined by polynomials. The proposed PolyTrace algorithm has polynomial complexity in the number of atomic propositions, and is guaranteed to produce a trace of any polynomial path. Its performance is demonstrated via numerical examples and a case study from robotics., Comment: Published in Theoretical Computer Science. Definition 7 and Remark 4 have been updated to correct an oversight in the published version

In this paper we provide a formal framework for comparing the expressive power of Behavior Trees (BTs) to other action selection architectures. Taking inspiration from the analogous comparisons of structural programming methodologies, we formalise the concept of `expressiveness'. This leads us to an expressiveness hierarchy of control architectures, which includes BTs, Decision Trees (DTs), Teleo-reactive Programs (TRs) and Finite State Machines (FSMs). By distinguishing between BTs with auxiliary variables and those without, we demonstrate the existence of a trade-off in BT design between readability and expressiveness. We discuss what this means for BTs in practice., Comment: 8 pages, 2 figures. Accepted to IEEE Robotics and Automation Letters

In assignment problems, decision makers are often interested in not only the optimal assignment, but also the sensitivity of the optimal assignment to perturbations in the assignment weights. Typically, only perturbations to individual assignment weights are considered. We present a novel extension of the traditional sensitivity analysis by allowing for simultaneous variations in all assignment weights. Focusing on the bottleneck assignment problem, we provide two different methods of quantifying the sensitivity of the optimal assignment, and present algorithms for each. Numerical examples as well as a discussion of the complexity for all algorithms are provided., Comment: 28 pages

In many learning based control methodologies, learning the unknown dynamic model precedes the control phase, while the aim is to control the system such that it remains in some safe region of the state space. In this work, our aim is to guarantee safety while learning and control proceed simultaneously. Specifically, we consider the problem of safe learning in nonlinear control-affine systems subject to unknown additive uncertainty. We first model the uncertainty as a Gaussian noise and use state measurements to learn its mean and covariance. We provide rigorous time-varying bounds on the mean and covariance of the uncertainty and employ them to modify the control input via an optimization program with potentially time-varying safety constraints. We show that with an arbitrarily large probability we can guarantee that the state will remain in the safe set, while learning and control are carried out simultaneously, provided that a feasible solution exists for the optimization problem. We provide a secondary formulation of this optimization that is computationally more efficient. This is based on tightening the safety constraints to counter the uncertainty about the learned mean and covariance. The magnitude of the tightening can be decreased as our confidence in the learned mean and covariance increases (i.e., as we gather more measurements about the environment). Extensions of the method are provided for non-Gaussian process noise with unknown mean and covariance as well as Gaussian uncertainties with state-dependent mean and covariance to accommodate more general environments.

We introduce a sequential learning algorithm to address a robust controller tuning problem, which in effect, finds (with high probability) a candidate solution satisfying the internal performance constraint to a chance-constrained program which has black-box functions. The algorithm leverages ideas from the areas of randomised algorithms and ordinal optimisation, and also draws comparisons with the scenario approach; these have all been previously applied to finding approximate solutions for difficult design problems. By exploiting statistical correlations through black-box sampling, we formally prove that our algorithm yields a controller meeting the prescribed probabilistic performance specification. Additionally, we characterise the computational requirement of the algorithm with a probabilistic lower bound on the algorithm's stopping time. To validate our work, the algorithm is then demonstrated for tuning model predictive controllers on a diesel engine air-path across a fleet of vehicles. The algorithm successfully tuned a single controller to meet a desired tracking error performance, even in the presence of the plant uncertainty inherent across the fleet. Moreover, the algorithm was shown to exhibit a sample complexity comparable to the scenario approach., Comment: 17 pages including appendices and references

We study the problem of minimizing the sum of potentially non-differentiable convex cost functions with partially overlapping dependences in an asynchronous manner, where communication in the network is not coordinated. We study the behavior of an asynchronous algorithm based on dual decomposition and block coordinate subgradient methods under assumptions weaker than those used in the literature. At the same time, we allow different agents to use local stepsizes with no global coordination. Sufficient conditions are provided for almost sure convergence to the solution of the optimization problem. Under additional assumptions, we establish a sublinear convergence rate that in turn can be strengthened to linear convergence rate if the problem is strongly convex and has Lipschitz gradients. We also extend available results in the literature by allowing multiple and potentially overlapping blocks to be updated at the same time with non-uniform and potentially time varying probabilities assigned to different blocks. A numerical example is provided to illustrate the effectiveness of the algorithm.

The motivation for this work stems from the problem of scheduling requests for flow at supply points along an automated network of open-water channels. The off-take flows are rigid-profile inputs to the system dynamics. In particular, the channel operator can only shift orders in time to satisfy constraints on the automatic response to changes in the load. This leads to a non-convex semi-infinite programming problem, with sum-separable cost that encodes the collective sensitivity of end users to scheduling delays. The constraints encode the linear time-invariant continuous-time dynamics and limits on the state across a \al{continuous} scheduling horizon. Discretization is used to arrive at a more manageable approximation of the semi-infinite program. A method for parsimoniously refining the discretization is applied to ensure continuous-time feasibility for solutions of the approximate problem. It is then shown how to improve cost without loss of feasibility. Supporting analysis is provided, along with simulation results for a realistic irrigation channel setup to illustrate the approach.

We present a midpoint policy iteration algorithm to solve linear quadratic optimal control problems in both model-based and model-free settings. The algorithm is a variation of Newton's method, and we show that in the model-based setting it achieves cubic convergence, which is superior to standard policy iteration and policy gradient algorithms that achieve quadratic and linear convergence, respectively. We also demonstrate that the algorithm can be approximately implemented without knowledge of the dynamics model by using least-squares estimates of the state-action value function from trajectory data, from which policy improvements can be obtained. With sufficient trajectory data, the policy iterates converge cubically to approximately optimal policies, and this occurs with the same available sample budget as the approximate standard policy iteration. Numerical experiments demonstrate effectiveness of the proposed algorithms.

We develop an algorithm to solve the Bottleneck Assignment Problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one component in particular, i.e., the function to search for an augmenting path. An augmenting path is a common tool used in most BAP algorithms and poses a particular challenge for this distributed approach. Given this significance, we compare two different methods to search for an augmenting path in a bipartite graph. We also exploit properties of the augmenting paths to formalise conditions for which the solution from subsets of the sets of agents and tasks can be used to solve the BAP with the full sets of agents and tasks. In the end, we evaluate and compare the derived approaches with a numerical analysis.

We study numerical optimisation algorithms that use zeroth-order information to minimise time-varying geodesically-convex cost functions on Riemannian manifolds. In the Euclidean setting, zeroth-order algorithms have received a lot of attention in both the time-varying and time-invariant cases. However, the extension to Riemannian manifolds is much less developed. We focus on Hadamard manifolds, which are a special class of Riemannian manifolds with global nonpositive curvature that offer convenient grounds for the generalisation of convexity notions. Specifically, we derive bounds on the expected instantaneous tracking error, and we provide algorithm parameter values that minimise the algorithm's performance. Our results illustrate how the manifold geometry in terms of the sectional curvature affects these bounds. Additionally, we provide dynamic regret bounds for this online optimisation setting. To the best of our knowledge, these are the first regret bounds even for the Euclidean version of the problem. Lastly, via numerical simulations, we demonstrate the applicability of our algorithm on an online Karcher mean problem., Comment: 27 pages, 2 figures

In this paper, the problem of simultaneous cyber attack and fault detection and isolation (CAFDI) in cyber-physical systems (CPS) is studied. The proposed solution methodology consists of two filters on the plant and the command and control (C\&C) sides of the CPS and an unknown input observer (UIO) based detector on the plant side. Conditions under which the proposed methodology can detect deception attacks, such as covert attacks, zero dynamics attacks, and replay attacks are characterized. An advantage of the proposed methodology is that one does not require a fully secured communication link which implies that the communication link can be compromised by the adversary while it is used to transmit the C\&C side observer estimates. Also, it is assumed that adversaries have access to parameters of the system, filters, and the UIO-based detector, however, they do not have access to all the communication link channels. Conditions under which, using the communication link cyber attacks, the adversary cannot eliminate the impact of actuator and sensor cyber attacks are investigated. To illustrate the capabilities and effectiveness of the proposed CAFDI methodologies, simulation case studies are provided and comparisons with detection methods that are available in the literature are included to demonstrate the advantages and benefits of our proposed solutions.

This paper aims at investigating a novel type of cyber attack that is injected to multi-agent systems (MAS) having an underlying directed graph. The cyber attack, which is designated as the controllability attack, is injected by the malicious adversary into the communication links among the agents. The adversary, leveraging the compromised communication links disguises the cyber attack signals and attempts to take control over the entire network of MAS. The adversary aims at achieving this by directly attacking only a subset of the multi-agents. Conditions under which the malicious hacker has control over the entire MAS network are provided. Two notions of security controllability indices are proposed and developed. These notions are utilized as metrics to evaluate the controllability that each agent provides to the adversary for executing the malicious cyber attack. Furthermore, the possibility of introducing zero dynamics cyber attacks on the MAS through compromising the communication links is also investigated. Finally, an illustrative numerical example is provided to demonstrate the effectiveness of our proposed methods.