Synthesis method of strategy for multi-robot systems from local automatons under probabilistic model checking

Through innovatively introducing the receding horizon into probabilistic model checking, an online strategy synthesis method for multi-robot systems from local automatons is proposed to complete complex tasks that are assigned to each robot. Firstly, each robot is modeled as a Markov decision process which models both probabilistic and nondeterministic behavior. Secondly, the task specification of each robot is expressed as a linear temporal logic formula. For some tasks that robots cannot complete by themselves, the collaboration requirements take the form of atomic proposition into the LTL specifications. And the LTL specifications are transformed to deterministic rabin automatons over which a task progression metric is defined to determine the local goal states in the finite-horizon product systems. Thirdly, two horizons are set to determine the running steps in automatons and MDPs. By dynamically building local finite-horizon product systems, the collaboration strategies are synthesized iteratively for each robot to satisfy the task specifications with maximum probability. Finally, through simulation experiments in an indoor environment, the results show that the method can synthesize correct strategies online for multi-robot systems which has no restriction on the LTL operators and reduce the computational burden brought by the automaton-based approach.

Reactive sampling-based path planning with temporal logic specifications

We develop a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The mission specification has two parts: (1) a global specification given as a linear temporal logic (LTL) formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. The proposed computational framework consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula; and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. The off-line algorithm has four main features. First, it is incremental, in the sense that the procedure for finding a satisfying path at each iteration scales only with the number of new samples generated at that iteration. Second, the underlying graph is sparse, which implies low complexity for the overall method. Third, it is probabilistically complete. Fourth, under some mild assumptions, it has the best possible complexity bound. The on-line algorithm leverages ideas from LTL monitoring and potential functions to ensure progress towards the satisfaction of the global specification while servicing locally sensed requests. Examples and experimental trials illustrating the usefulness and the performance of the framework are included.

STyLuS*: A Temporal Logic Optimal Control Synthesis Algorithm for Large-Scale Multi-Robot Systems

This article proposes a new highly scalable and asymptotically optimal control synthesis algorithm from linear temporal logic specifications, called [Formula: see text] for large-Scale optimal Temporal Logic Synthesis, that is designed to solve complex temporal planning problems in large-scale multi-robot systems. Existing planning approaches with temporal logic specifications rely on graph search techniques applied to a product automaton constructed among the robots. In our previous work, we have proposed a more tractable sampling-based algorithm that builds incrementally trees that approximate the state space and transitions of the synchronous product automaton and does not require sophisticated graph search techniques. Here, we extend our previous work by introducing bias in the sampling process that is guided by transitions in the Büchi automaton that belong to the shortest path to the accepting states. This allows us to synthesize optimal motion plans from product automata with hundreds of orders of magnitude more states than those that existing optimal control synthesis methods or off-the-shelf model checkers can manipulate. We show that [Formula: see text] is probabilistically complete and asymptotically optimal and has exponential convergence rate. This is the first time that convergence rate results are provided for sampling-based optimal control synthesis methods. We provide simulation results that show that [Formula: see text] can synthesize optimal motion plans for very large multi-robot systems, which is impossible using state-of-the-art methods.

Trust-Based Multi-Robot Symbolic Motion Planning with a Human-in-the-Loop

Symbolic motion planning for robots is the process of specifying and planning robot tasks in a discrete space, then carrying them out in a continuous space in a manner that preserves the discrete-level task specifications. Despite progress in symbolic motion planning, many challenges remain, including addressing scalability for multi-robot systems and improving solutions by incorporating human intelligence. In this article, distributed symbolic motion planning for multi-robot systems is developed to address scalability. More specifically, compositional reasoning approaches are developed to decompose the global planning problem, and atomic propositions for observation, communication, and control are proposed to address inter-robot collision avoidance. To improve solution quality and adaptability, a hypothetical dynamic, quantitative, and probabilistic human-to-robot trust model is developed to aid this decomposition. Furthermore, a trust-based real-time switching framework is proposed to switch between autonomous and manual motion planning for tradeoffs between task safety and efficiency. Deadlock- and livelock-free algorithms are designed to guarantee reachability of goals with a human-in-the-loop. A set of nontrivial multi-robot simulations with direct human inputs and trust evaluation is provided, demonstrating the successful implementation of the trust-based multi-robot symbolic motion planning methods.

An incremental constraint-based framework for task and motion planning

We present a new constraint-based framework for task and motion planning (TMP). Our approach is extensible, probabilistically complete, and offers improved performance and generality compared with a similar, state-of-the-art planner. The key idea is to leverage incremental constraint solving to efficiently incorporate geometric information at the task level. Using motion feasibility information to guide task planning improves scalability of the overall planner. Our key abstractions address the requirements of manipulation and object rearrangement. We validate our approach on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared with the benchmark planner and improved scalability from additional geometric guidance. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.

Systems view on spatial planning and perception based on invariants in agent-environment dynamics

Modeling agile and versatile spatial behavior remains a challenging task, due to the intricate coupling of planning, control, and perceptual processes. Previous results have shown that humans plan and organize their guidance behavior by exploiting patterns in the interactions between agent or organism and the environment. These patterns, described under the concept of Interaction Patterns (IPs), capture invariants arising from equivalences and symmetries in the interaction with the environment, as well as effects arising from intrinsic properties of human control and guidance processes, such as perceptual guidance mechanisms. The paper takes a systems' perspective, considering the IP as a unit of organization, and builds on its properties to present a hierarchical model that delineates the planning, control, and perceptual processes and their integration. The model's planning process is further elaborated by showing that the IP can be abstracted, using spatial time-to-go functions. The perceptual processes are elaborated from the hierarchical model. The paper provides experimental support for the model's ability to predict the spatial organization of behavior and the perceptual processes.

Multi-agent plan reconfiguration under local LTL specifications

We propose a cooperative motion and task planning scheme for multi-agent systems where the agents have independently assigned local tasks, specified as linear temporal logic formulas. These tasks contain hard and soft sub-specifications. A least-violating initial plan is synthesized first for the potentially infeasible task and the partially-known workspace. This discrete plan is then implemented by the potential-field-based navigation controllers. While the system runs, each agent updates its knowledge about the workspace via its sensing capability and shares this knowledge with its neighbouring agents. Based on the knowledge update, each agent verifies and revises its motion plan in real time. It is ensured that the hard specification is always fulfilled for safety and the satisfaction for the soft specification is improved gradually. The design is distributed as only local interactions are assumed. The overall framework is demonstrated by a case study and an experiment.

Receding horizon temporal logic control in dynamic environments

We present a receding horizon method for controlling an autonomous vehicle that must satisfy a rich mission specification over service requests occurring at the regions of a partitioned environment. The overall mission specification consists of a temporal logic statement over a set of static, a priori known requests, a regular expression over a set of dynamic requests that can be sensed only locally, and a servicing priority order over these dynamic requests. Our approach is based on two main steps. First, we construct an abstraction for the motion of the vehicle in the environment by using input–output linearization and assignment of vector fields to the regions in the partition. Second, a receding horizon controller computes local plans within the sensing range of the vehicle such that both local and global mission specifications are satisfied. We implement and evaluate our method through experiments and simulations consisting of a quadrotor performing a persistent surveillance task over a planar grid environment.

Integrated motion planning and control for graceful balancing mobile robots

This paper presents an integrated motion planning and control framework that enables balancing mobile robots to gracefully navigate human environments. A palette of controllers called motion policies is designed such that balancing mobile robots can achieve fast, graceful motions in small, collision-free domains of the position space. The domains determine the validity of a motion policy at any point in the robot’s position state space. An automatic instantiation procedure that generates a motion policy library by deploying motion policies from a palette on a map of the environment is presented. A gracefully prepares relationship that guarantees valid compositions of motion policies to produce overall graceful motion is introduced. A directed graph called the gracefully prepares graph is used to represent all valid compositions of motion policies in the motion policy library. The navigation tasks are achieved by planning in the space of these gracefully composable motion policies. In this work, Dijsktra’s algorithm is used to generate a single-goal optimal motion policy tree, and its variant is used to rapidly replan the optimal motion policy tree in the presence of dynamic obstacles. A hybrid controller is used as a supervisory controller to ensure successful execution of motion policies and also successful switching between them. The integrated motion planning and control framework presented in this paper was experimentally tested on the ballbot, a human-sized dynamically stable mobile robot that balances on a single ball. The results of successful experimental testing of two navigation tasks, namely, point-point and surveillance motions are presented. Additional experimental results that validate the framework’s capability to handle disturbances and rapidly replan in the presence of dynamic obstacles are also presented.

Coordinability and consistency in accident causation and prevention: formal system theoretic concepts for safety in multilevel systems

Although a "system approach" to accidents in sociotechnical systems has been frequently advocated, formal system theoretic concepts remain absent in the literature on accident analysis and system safety. To address this gap, we introduce the notions of coordinability and consistency from the hierarchical and multilevel systems theory literature. We then investigate the applicability and the importance of these concepts to accident causation and safety. Using illustrative examples, including the worst disaster in aviation history, and recent incidents in the United States of aircraft clipping each other on the tarmac, we propose that the lack of coordinability is a fundamental failure mechanism causing or contributing to accidents in multilevel systems. We make a similar case for the lack of consistency. Coordinability and consistency become ingredients for accident prevention, and their absence fundamental failure mechanisms that can lead to system accidents. Finally, using the concepts introduced in this work, we identify several venues for further research, including the development of a theory of coordination in multilevel systems, the investigation of potential synergies between coordinability, consistency, and the high reliability organizations paradigm, and the possibility of reframing the view that "sloppy management is the root cause of many industrial accidents" as one of lack of coordinability and/or consistency between management and operations. By introducing and expanding on the concepts of coordinability and consistency, we hope to contribute to the thinking about, and the to language of, accident causation, and prevention and to add to the intellectual toolkit of safety professionals and academics.

Optimal path planning for surveillance with temporal-logic constraints

In this paper we present a method for automatically generating optimal robot paths satisfying high-level mission specifications. The motion of the robot in the environment is modeled as a weighted transition system. The mission is specified by an arbitrary linear temporal-logic (LTL) formula over propositions satisfied at the regions of a partitioned environment. The mission specification contains an optimizing proposition, which must be repeatedly satisfied. The cost function that we seek to minimize is the maximum time between satisfying instances of the optimizing proposition. For every environment model, and for every formula, our method computes a robot path that minimizes the cost function. The problem is motivated by applications in robotic monitoring and data-gathering. In this setting, the optimizing proposition is satisfied at all locations where data can be uploaded, and the LTL formula specifies a complex data-collection mission. Our method utilizes Büchi automata to produce an automaton (which can be thought of as a graph) whose runs satisfy the temporal-logic specification. We then present a graph algorithm that computes a run corresponding to the optimal robot path. We present an implementation for a robot performing data collection in a road-network platform.

Robot Navigation in Multi-terrain Outdoor Environments

This paper presents a methodology for motion planning in outdoor environments that takes into account specific characteristics of the terrain. Instead of decomposing the robot configuration space into “free” and “occupied”, we consider the existence of several regions with different navigation costs. In this paper, costs are determined experimentally by navigating the robot through the regions and measuring the influence of the terrain on its motion. We measure the robot's vertical acceleration, which reflects the terrain roughness. The paper presents a hybrid (discrete—continuous) approach to guide and control the robot. After decomposing the map into triangular cells, a path planning algorithm is used to determine a discrete sequence of cells that minimizes the navigation cost. Robot control is accomplished by a fully continuous vector field that drives the robot through the sequence of triangular cells. This vector field allows smooth robot trajectories from any position inside the sequence to the goal, even for a small number of large cells. Moreover, the vector field is terrain dependent in the sense it changes the robot velocity according to the characteristics of the terrain. Experimental results with a differential driven, all-terrain mobile robot illustrate the proposed approach.

Simple and Efficient Algorithms for Computing Smooth, Collision-free Feedback Laws Over Given Cell Decompositions

This paper presents a novel approach to computing feedback laws in the presence of obstacles. Instead of computing a trajectory between a pair of initial and goal states, our algorithms compute a vector field over the entire state space; all trajectories obtained from following this vector field are guaranteed to asymptotically reach the goal state. As a result, the vector field globally solves the navigation problem and provides robustness to disturbances in sensing and control. The vector field's integral curves (system trajectories) are guaranteed to avoid obstacles and are C∞ smooth. We construct a vector field with these properties by partitioning the space into simple cells, defining local vector fields for each cell, and smoothly interpolating between them to obtain a global vector field. We present an algorithm that computes these feedback controls for a kinematic point robot in an arbitrary dimensional space with piecewise linear boundary; the algorithm requires minimal preprocessing of the environment and is extremely fast during execution. For many practical applications in two-dimensional environments, full computation can be done in milliseconds. We also present an algorithm for computing feedback laws over cylindrical algebraic decompositions, thereby solving a smooth feedback version of the generalized piano movers' problem.