This paper proposes a mechanism to fine-tune convex approximations of probabilistic reachable sets (PRS) of uncertain dynamic systems. We consider the case of unbounded uncertainties, for which it may be impossible to find a bounded reachable set of the system. Instead, we turn to find a PRS that bounds system states with high confidence. Our data-driven approach builds on a kernel density estimator (KDE) accelerated by a fast Fourier transform (FFT), which is customized to model the uncertainties and obtain the PRS efficiently. However, the non-convex shape of the PRS can make it impractical for subsequent optimal designs. Motivated by this, we formulate a mixed integer nonlinear programming (MINLP) problem whose solution result is an optimal$n$sided convex polygon that approximates the PRS. Leveraging this formulation, we propose a heuristic algorithm to find this convex set efficiently while ensuring accuracy. The algorithm is tested on comprehensive case studies that demonstrate its near-optimality, accuracy, efficiency, and robustness. The benefits of this work pave the way for promising applications to safety-critical, real-time motion planning of uncertain dynamic systems.Note to Practitioners—This study is motivated by the realization of safety-critical real-time motion planning for a dynamic system under uncertainties. A popular method used to guarantee the safe operation of uncertain dynamic systems is reachability analysis. However, this method may not work well in the face of the following challenges: unbounded uncertainties, unknown distributions, generality, convexity, and efficiency. To address these issues, we first present a data-driven approach to model arbitrary unknown uncertainties and obtain a set encompassing the system states with high confidence; Then we propose an algorithm to efficiently find a tight convex polygon approximation for the set. This clearly benefits real motion planning. When considering collision avoidance in motion planning, a tight convex approximation allows a larger feasible search area which may provide a better-planned trajectory. Also, the efficiency of the algorithm ensures that the motion planning can be realized in real-time.

No abstract available.

We consider the problem of cooperative localization (CL) via interrobot measurements for a team of networked robots with limited on-board resources. We propose a novel algorithm in which each robot localizes itself in a global coordinate frame by local dead reckoning, and opportunistically corrects its pose estimate whenever it receives a relative measurement update message from a server. The computation and storage cost per robot in terms of the size of the team is of order $O(1)$, and the robots are only transmitting information when they are involved in a relative measurement. The server also only needs to compute and transmit update messages when it receives an interrobot measurement. Under perfect communication, our algorithm is an alternative implementation of a joint CL for the team via an extended Kalman filter. However, perfect communication is not a hard constraint. We show that our algorithm is robust to communication failures, with formal guarantees that the updated estimates of the robots receiving the update message are of minimum variance in a first-order approximate sense at that given timestep. We demonstrate the performance of our algorithm in simulation and experiments.

For a team of mobile robots with limited onboard resources, we propose a partially decentralized implementation of an extended Kalman filter for cooperative localization. In the proposed algorithm, unlike a fully centralized scheme that requires, at each timestep, information from the entire team to be gathered together and be processed by a single device, we only require that the robots communicate with a central command unit at the time of a measurement update. In addition, the computational and storage cost per robot in terms of the size of the team is reduced to O(1). Moreover, the algorithm is robust to occasional in-network communication link failures while the estimation update of the robots receiving the update message is of minimum variance. We demonstrate the performance of the algorithm in simulations.

We present a novel decentralized cooperative localization algorithm for mobile robots. The proposed algorithm is a decentralized implementation of a centralized Extended Kalman Filter for cooperative localization. In this algorithm, instead of propagating cross-covariance terms, each robot propagates new intermediate local variables that can be used in an update stage to create the required propagated cross-covariance terms. Whenever there is a relative measurement in the network, the algorithm declares the robot making this measurement as the interim master. By acquiring information from the interim landmark, the robot the relative measurement is taken from, the interim master can calculate and broadcast a set of intermediate variables which each robot can then use to update its estimates to match that of a centralized Extended Kalman Filter for cooperative localization. Once an update is done, no further communication is needed until the next relative measurement. The communication graph can be a time-varying directed graph with the only requirement that it should have a spanning tree rooted at the interim master.

Data association mistakes, estimation and measurement errors are some of the factors that can contribute to incorrect observations in robotic sensor networks. In order to act reliably, a robotic network must be able to fuse and correct its perception of the world by discarding any outlier information. This is a difficult task if the network is to be deployed remotely and the robots do not have access to ground-truth sites or manual calibration. In this paper, we present a novel, distributed scheme for robust data fusion in autonomous robotic networks. The proposed method adapts the RANSAC algorithm to exploit measurement redundancy, and enables robots determine an inlier observation with local communications. Different hypotheses are generated and voted for using a dynamic consensus algorithm. As the hypotheses are computed, the robots can change their opinion making the voting process dynamic. Assuming that at least one hypothesis is initialized with only inliers, we show that the method converges to the maximum likelihood of all the inlier observations in a general instance. Several simulations exhibit the good performance of the algorithm, which also gives acceptable results in situations where the conditions to guarantee convergence do not hold.

This paper presents coverage algorithms for mobile sensor networks in which agents have limited power to move. Rather than making use of a constrained optimization technique, our approach accounts for power constraints by assigning non-homogeneously time-varying regions to each robot. This leads to a novel partition of the environment into limited-range, generalized Voronoi regions. The motion control algorithms are then designed to ascend the gradient of several types of locational optimization functions. In particular, the objective functions reflect the global energy available to the group and different coverage criteria. As we discuss in the paper, this has an effect on limiting each agent's velocity to save energy and balance its expenditure across the network.

This work studies optimal sensor placement and motion coordination strategies for mobile sensor networks. For a target tracking application with range sensors, we investigate the determinant of the Cramer Rao Lower Bound and compute it in the 2D and 3D cases, characterizing the global minima in the 2D case. We propose motion coordination algorithms that steer the mobile sensor network to an optimal deployment and that are amenable to a decentralized implementation. Finally, our numerical simulations illustrate how the proposed algorithms lead to improved performance of an extended Kalman filter in a target tracking scenario.

This paper presents control and coordination algorithms for groups of vehicles. The focus is on autonomous vehicle networks performing distributed sensing tasks, where each vehicle plays the role of a mobile tunable sensor. The paper proposes gradient descent algorithms for a class of utility functions which encode optimal coverage and sensing policies. The resulting closed-loop behavior is adaptive, distributed, asynchronous, and verifiably correct.

This paper presents motion planning algorithms for underactuated systems evolving on rigid rotation and displacement groups. Motion planning is transcribed into (low-dimensional) combinatorial selection and inverse-kinematics problems. We present a catalog of solutions for all underactuated systems on SE(2), SO(3) and SE(2) /spl times/ /spl Ropf/ classified according to their controllability properties.

This paper describes decentralized control laws for the coordination of multiple vehicles performing spatially distributed tasks. The control laws are based on a gradient descent scheme applied to a class of decentralized utility functions that encode optimal coverage and sensing policies. These utility functions are studied in geographical optimization problems and they arise naturally in vector quantization and in sensor allocation tasks. The approach exploits the computational geometry of spatial structures such as Voronoi diagrams.