In this paper, we consider multi-robot path planning problems for high-level tasks with a finite horizon. In many situations, there is a need tocount how many timesa sub-task is satisfied in order to achieve the overall task. However, existing temporal logic languages, such as linear temporal logic, is not efficient in describing such requirements. To address this issue, we propose a new temporal logic language calledCounting Time Temporal Logic(CTTL) that extends linear temporal logic by explicitly counting the number of times that some tasks are satisfied. To solve the CTTL path planning problem, we propose an efficient integer linear programming-based method to encode task satisfaction. We show that our approach is both sound and complete, while achieving higher efficiency than direct encodings of such requirements. Moreover, we study several variants of the problem. To validate our results, we present several numerical experiments to show the scalability of the proposed approach and a simulation case study of a team of autonomous robots to illustrate the feasibility of the synthesis procedure. Finally, to evaluate the real-world feasibility of our method, we conduct a hardware experiment with two Turtlebot3-Burger mobile robots.

We investigate the sampling-based optimal path planning problem for robotics in complex and dynamic environments. Most existing sampling-based algorithms neglect environmental information or the information from previous samples. Yet, these pieces of information are highly informative, as leveraging them can provide better heuristics when sampling the next state. In this paper, we propose a novel sampling-based planning algorithm, called RRT*former, which integrates the standard RRT* algorithm with a Transformer network in a novel way. Specifically, the Transformer is used to extract features from the environment and leverage information from previous samples to better guide the sampling process. Our extensive experiments demonstrate that, compared to existing sampling-based approaches such as RRT*, Neural RRT*, and their variants, our algorithm achieves considerable improvements in both the optimality of the path and sampling efficiency. The code for our implementation is available on https://github.com/fengmingyang666/RRTformer.

In this paper, we investigate a multi-robot task allocation problem where a team of heterogeneous robots operates in a discrete workspace to achieve a set of tasks expressed by linear temporal logic formulas. In contrast to existing works, we further consider inter-task-time-order constraints, which are imposed on the start or end times of each task. Solving such problems generally requires combinatorial search, which is not scalable. Inspired by the efficiency of max-plus algebra in handling time constraints, we propose a novel approach called MaxAuc, which integrates Auction-based task allocation with Max-plus algebra in a novel manner. Specifically, max-plus computations are performed to approximate task priorities in the auction without explicitly solving the constraint optimization problem. Our numerical results demonstrate that MaxAuc is highly scalable with respect to both the number of robots and the number of tasks, while maintaining a tolerable performance trade-off compared to the baseline’s optimal yet exhaustive solution.

Control Barrier Functions (CBFs) have emerged as an effective and non-invasive safety filter for ensuring the safety of autonomous systems in dynamic environments with formal guarantees. However, most existing works on CBF synthesis focus on fully known settings. Synthesizing CBFs online based on perception data in unknown environments poses particular challenges. Specifically, this requires the construction of CBFs from high-dimensional data efficiently in real time. This paper proposes a new approach for online synthesis of CBFs directly from local Occupancy Grid Maps (OGMs). Inspired by steady-state thermal fields, we show that the smoothness requirement of CBFs corresponds to the solution of the steady-state heat conduction equation with suitably chosen boundary conditions. By leveraging the sparsity of the coefficient matrix in Laplace’s equation, our approach allows for efficient computation of safety values for each grid cell in the map. Simulation and real-world experiments demonstrate the effectiveness of our approach. Specifically, the results show that our CBFs can be synthesized in an average of milliseconds on a 200×200 grid map, highlighting its real-time applicability.

Micromanipulation using magnetic microswarms has garnered significant attention in recent years due to their potential in microscale cargo delivery tasks. While existing studies have demonstrated the capabilities of microswarms in basic manipulation tasks, they often lack the autonomy required to handle more complex specifications, particularly temporal logic tasks. In this paper, we propose a novel formal planning strategy for magnetic microswarms that enables cargo delivery in complex environments while satisfying finite linear temporal logic (LTLf) specifications. Our approach consists of two key components. First, we develop a high-level path planner based on a bidirectional temporal logic rapid-explore random tree star (BTL-RRT*) algorithm, which facilitates efficient planning while ensuring compliance with the given task specifications. Second, we employ an automaton to manage the manipulation modes of the microswarm, enabling real-time control over the capture and release of cargoes. In addition, we implement the planning strategy on microswarms actuated by a visual feedback magnetic tweezers system. Extensive simulations and experimental results demonstrate the effectiveness of the proposed planning strategy. The results indicate that, using the proposed approach, microswarms can autonomously select and deliver multiple microbeads to designated regions in both static and dynamic environments, adhering to the LTLfspecifications.

This paper investigates the problem of safe visual servoing control of manipulators using an uncalibrated eye-in-hand camera based on control barrier functions (CBFs). Traditional CBFs are defined in the workspace, corresponding to the global coordinates of the base frame. However, when the camera’s position or orientation is adjusted for a better field of view, it becomes uncalibrated, making it challenging to obtain the precise positions of the robot and obstacles using onboard sensors like a camera. To address this, we propose a novel visual servoing control barrier function (VS-CBF) for manipulators, which depends only on the image and depth data sensed by an RGB-D camera. Given an uncalibrated camera, we develop an adaptive estimator for the unknown camera parameters. Based on this estimator, we also design a kinematic visual servoing control law as a nominal controller, ensuring the convergence of the robotic system. The safe controller is then obtained by solving a quadratic programming problem that incorporates the designed VS-CBF and the nominal controller. Finally, experimental results conducted on a UR3 manipulator are presented to demonstrate the effectiveness of our approach.

Signal Temporal Logic (STL) is a powerful specification language for describing complex temporal behaviors of continuous signals, making it well-suited for high-level robotic task descriptions. However, generating executable plans for STL tasks is challenging, as it requires consideration of the coupling between the task specification and the system dynamics. Existing approaches either follow a model-based setting that explicitly requires knowledge of the system dynamics or adopt a task-oriented data-driven approach to learn plans for specific tasks. In this work, we address the problem of generating executable STL plans for systems with unknown dynamics. We propose a hierarchical planning framework that enables zero-shot generalization to new STL tasks by leveraging only task-agnostic trajectory data during offline training. The framework consists of three key components: (i) decomposing the STL specification into several progresses and time constraints, (ii) searching for timed waypoints that satisfy all progresses under time constraints, and (iii) generating trajectory segments using a pre-trained diffusion model and stitching them into complete trajectories. We formally prove that our method guarantees STL satisfaction, and simulation results demonstrate its effectiveness in generating dynamically feasible trajectories across diverse long-horizon STL tasks. Project Page: https://cps-sjtu.github.io/Zero-Shot-STL/

In this work, we investigate task planning for mobile robots under linear temporal logic (LTL) specifications. This problem is particularly challenging when robots navigate in continuous workspaces due to the high computational complexity involved. Sampling-based methods have emerged as a promising avenue for addressing this challenge by incrementally constructing random trees, thereby sidestepping the need to explicitly explore the entire state-space. However, the performance of this sampling-based approach hinges crucially on the chosen sampling strategy, and a well-informed heuristic can notably enhance sample efficiency. In this work, we propose a novel neural-network guided (NN-guided) sampling strategy tailored for LTL planning. Specifically, we employ a multi-modal neural network capable of extracting features concurrently from both the workspace and the Büchi automaton. This neural network generates predictions that serve as guidance for random tree construction, directing the sampling process toward more optimal directions. Through numerical experiments, we compare our approach with existing methods and demonstrate its superior efficiency, requiring less than 15% of the time of the existing methods to find a feasible solution.

This paper investigates the problem of designing control policies that satisfy high-level specifications described by signal temporal logic (STL) in unknown, stochastic environments. While many existing works concentrate on optimizing the spatial robustness of a system, our work takes a step further by also considering temporal robustness as a critical metric to quantify the tolerance of time uncertainty in STL. To this end, we formulate two relevant control objectives to enhance the temporal robustness of the synthesized policies. The first objective is to maximize the probability of being temporally robust for a given threshold. The second objective is to maximize the worst-case spatial robustness value within a bounded time shift. We use reinforcement learning to solve both control synthesis problems for unknown systems. Specifically, we approximate both control objectives in a way that enables us to apply the standard Q-learning algorithm. Theoretical bounds in terms of the approximations are also derived. We present case studies to demonstrate the feasibility of our approach.

In this work, we consider the problem of Koopman modeling and data-driven predictive control for a class of uncertain nonlinear systems subject to time delays. A robust deep learning-based approach–deep recurrent Koopman operator is proposed. Without requiring the knowledge of system uncertainties or information on the time delays, the proposed deep recurrent Koopman operator method is able to learn the dynamics of the nonlinear systems autonomously. A robust predictive control framework is established based on the deep Koopman operator. Conditions on the stability of the closed-loop system are presented. The proposed approach is applied to a chemical process example. The results confirm the superiority of the proposed framework as compared to baselines.

In this paper, we investigate the problem of reinforcement learning under linear temporal logic (LTL) specifications for Markov decision processes (MDPs) with security constraints. We consider an outside passive intruder (observer) that can observe the external output behavior of the system through an output projection. We assume that the secret of the system is a subset of the initial states. The security constraint requires that the observer can never infer for sure that the agent was initiated from a secret state. Our objective is to learn a control policy that achieves the LTL task while ensuring security. To solve the problem of shaping the reward for reinforcement learning, we propose an approach based on the initial-state estimator and the limit deterministic Büchi automata. We illustrate the proposed approach by a case study of mobile robot example.

Cloud computing is an emerging paradigm to enable computation and data-intensive automotive systems for improved safety and drivability. In this article, we propose a hierarchical, decentralized, and auction-based resource allocation model for cloud-enabled automotive vehicles. In this model, cloud-enabled vehicles bid for resources at a high level, inducing a multiplayer game; at a low level, each vehicle performs an onboard resource optimization to allocate its obtained resources to its cloud-based applications. The Nash equilibrium of the induced game is defined, and we show the existence and uniqueness of the equilibrium. A constrained optimization problem is solved for onboard resource allocation. A distributed update mechanism is considered: asynchronized update where only a subset of vehicles updates their bid at each iteration. This mechanism shares desired features of requiring little communication and being secure. Convergence to Nash equilibrium is proved for the proposed update mechanism. Furthermore, the robustness to stochastic task arrival rate is characterized in terms of total variance distance. Numerical simulations are presented to demonstrate the efficacy of the proposed framework.

Microscopic traffic models describe how cars interact with their neighbors in an uninterrupted traffic flow and are frequently used for reference in advanced vehicle control design. In this paper, we propose a novel mechanical system-inspired microscopic traffic model using a mass-spring-damper-clutch system. This model naturally captures the ego vehicle's resistance to large relative speed and deviation from a (driver- and speed-dependent) desired relative distance when following the lead vehicle. Compared with the existing car-following (CF) models, this model offers physically interpretable insights into the underlying CF dynamics and is able to characterize the impact of the ego vehicle on the lead vehicle, which is neglected in the existing CF models. Thanks to the nonlinear wave propagation analysis techniques for mechanical systems, the proposed model, therefore, has great scalability so that multiple mass-spring-damper-clutch systems can be chained to study the macroscopic traffic flow. We investigate the stability of the proposed model on the system parameters and the time delay using the spectral element method. We also develop a parallel recursive least square with inverse QR decomposition (PRLS-IQR) algorithm to identify the model parameters online. These real-time estimated parameters can be used to predict the driving trajectory that can be incorporated into advanced vehicle longitudinal control systems for improved safety and fuel efficiency. The PRLS-IQR is computationally efficient and numerically stable, and therefore, it is suitable for online implementation. The traffic model and the parameter identification algorithm are validated on both the simulations and naturalistic driving data from multiple drivers. Promising performance is demonstrated.

We investigate the problem of decentralized fault prognosis in the context of discrete-event systems. In this problem, the system is monitored by a set of local agents; each of them sends its local information to a coordinator in order to issue a fault alarm before the occurrence of fault. Two new decentralized protocols are proposed by exploiting the state-estimate of each local agent. For each protocol, a necessary and sufficient condition for its correctness is proposed; they are termed as positive state-estimate-prognosability and negative state-estimate prognosability. Verification algorithms for the necessary and sufficient conditions are also provided. We show that the proposed new protocols are incomparable with any of the existing protocols in the literature. Therefore, they provide new opportunities for correctly predicting the fault when all existing protocols fail.

This paper investigates the problem of driver distraction detection using driving performance indicators from onboard kinematic measurements. First, naturalistic driving data from the integrated vehicle-based safety system program are processed, and cabin camera data are manually inspected to determine the driver's state (i.e., distracted or attentive). Second, existing driving performance metrics, such as steering entropy, steering wheel reversal rate, and lane offset variance, are reviewed against the processed naturalistic driving data. Furthermore, a nonlinear autoregressive exogenous (NARX) driving model is developed to predict vehicle speed based on the range (distance headway), range rate, and speed history. For each driver, the NARX model is then trained on the attentive driving data. We show that the prediction error is correlated with driver distraction. Finally, two features, steering entropy and mean absolute speed prediction error from the NARX model are selected, and a support vector machine is trained to detect driving distraction. Prediction performances are reported.

The objective of drift counteraction optimal control (DCOC) problem is to compute an optimal control law that maximizes the expected time of violating specified system constraints. In this paper, we reformulate the DCOC problem as a reinforcement learning (RL) one, removing the requirements of disturbance measurements and prior knowledge of the disturbance evolution. The optimal control policy for the DCOC is then trained with RL algorithms. As an example, we treat the problem of adaptive cruise control, where the objective is to maintain desired distance headway and time headway from the lead vehicle, while the acceleration and speed of the host vehicle are constrained based on safety, comfort, and fuel economy considerations. An informed approximate Q-learning algorithm is developed with efficient training, fast convergence, and good performance. The control performance is compared with a heuristic driver model in simulation and superior performance is demonstrated.

In this paper, we investigate the partially observed supervisor synthesis problem in the framework of fuzzy discrete-event systems (DESs). The goal is to synthesize a fuzzy supervisor such that the behavior of the closed-loop system is within a given fuzzy language. A new approach for solving this problem is proposed based on the idea of belief evolution. Specifically, we propose an algorithm that can be implemented in an online manner. We show that the proposed algorithm is both sound and complete, i.e., it effectively solves the supervisor synthesis problem. To the best of our knowledge, this is the first algorithm with such a property for fuzzy DESs, as previous works on this topic mostly focus on the supervisor existence condition rather than the supervisor synthesis problem.

We investigate the problem of reliable decentralized fault prognosis of partially-observed discrete-event systems. In this problem, n local prognosers are deployed to send their local prognostic decisions to a coordinator that calculates the final prognostic decision. However, only k (1≤ k ≤ n) local prognostic decisions are guaranteed to be available to the coordinator due to possible failures or communication losses of at most n - k local prognosers. We propose the notion of k-reliable decentralized prognoser in order to address this reliability issue. A necessary and sufficient condition for the existence of a k-reliable decentralized prognoser, which predicts faults prior to their occurrences, is presented. This condition is termed as k-reliable coprognosability. A polynomial-time algorithm for the verification of k-reliable coprognosability is presented. We also demonstrate how to compute the k-reliable reactive bound prior to any occurrence of faults.