We describe a new approach for constructing finite horizon invariant, viable and discriminating sets for systems with discrete time affine dynamics. The sets are compactly represented as zonotopes whose generators are scaled through a convex optimization to ensure the desired invariance. The algorithm also constructs a set of feasible control inputs for each state.

Constructing a smart wheelchair on a commercially available powered wheelchair (PWC) platform avoids a host of seating, mechanical design and reliability issues but requires methods of predicting and controlling the motion of a device never intended for robotics. Analog joystick inputs are subject to black-box transformations which may produce intuitive and adaptable motion control for human operators, but complicate robotic control approaches; furthermore, installation of standard axle mounted odometers on a commercial PWC is difficult. In this work, we present an integrated hardware and software system for predicting the motion of a commercial PWC platform that does not require any physical or electronic modification of the chair beyond plugging into an industry standard auxiliary input port. This system uses an RGB-D camera and an Arduino interface board to capture motion data, including visual odometry and joystick signals, via ROS communication. Future motion is predicted using an autoregressive sparse Gaussian process model. We evaluate the proposed system on real-world short-term path prediction experiments. Experimental results demonstrate the system's efficacy when compared to a baseline neural network model.

Robots are increasingly operating in indoor environments designed for and shared with people. However, robots working safely and autonomously in uneven and unstructured environments still face great challenges. Many modern indoor environments are designed with wheelchair accessibility in mind. This presents an opportunity for wheeled robots to navigate through sloped areas while avoiding staircases. In this paper, we present an integrated software and hardware system for autonomous mobile robot navigation in uneven and unstructured indoor environments. This modular and reusable software framework incorporates capabilities of perception and navigation. Our robot first builds a 3D OctoMap representation for the uneven environment with the 3D mapping using wheel odometry, 2D laser and RGB-D data. Then we project multilayer 2D occupancy maps from OctoMap to generate the the traversable map based on layer differences. The safe traversable map serves as the input for efficient autonomous navigation. Furthermore, we employ a variable step size Rapidly Exploring Random Trees that could adjust the step size automatically, eliminating tuning step sizes according to environments. We conduct extensive experiments in simulation and real-world, demonstrating the efficacy and efficiency of our system. (Supplemented video link: https://youtu.be/6XJWcsH1fk0).

The papers included in this special section were presented at the Sixth Annual ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS 2015) that was held on April 14-16, 2015 in Seattle, WA, USA, as part of the Eighth Annual Cyber-Physical Systems Week. ICCPS is the premier single-track conference for reporting advances in all aspects of cyber-physical systems, including theory, tools, applications, systems, testbeds, and field deployments. Its focus includes the core science and technology for developing fundamental principles that underpin the integration of cyber and physical elements, with application domains that include transportation, energy, water, agriculture, ecology, supply-chains, medical and assistive technology, sensor and social networks, and robotics.

A sampled data model falls somewhere between continuous and discrete time models: The plant evolves in continuous time, but the controller receives feedback and can modify its control input(s) only at periodic points in time. In previous work we have demonstrated how to compute the discriminating kernel (also called the maximal robust control invariant set) for sampled data systems and how this kernel can be used to analyze and even synthesize safe feedback controllers for systems with state space safety constraints; however, the algorithm for computing the kernel was conservative. In this paper we provide an improved abstract algorithm whose computations are tight to the sampled data discriminating kernel. The improved algorithm can also take sample time jitter into account. A level set implementation is used to demonstrate that the new algorithm is tight and a conservative ellipsoidal implementation is used to demonstrate its practical benefits on a nonlinear quadrotor model.

Smart powered wheelchairs offer the possibility of enhanced mobility to a large and growing population-most notably older adults-and a key feature of such a chair is collision avoidance. Sensors are required to detect nearby obstacles; however, complete sensor coverage of the immediate neighbourhood is challenging for reasons including financial, computational, aesthetic, user identity and sensor reliability. It is also desirable to predict the future motion of the wheelchair based on potential input signals; however, direct modeling and control of commercial wheelchairs is not possible because of proprietary internals and interfaces. In this paper we design a dynamic egocentric occupancy map which maintains information about local obstacles even when they are outside the field of view of the sensor system, and we construct a neural network model of the mapping between joystick inputs and wheelchair motion. Using this map and model infrastructure, we can evaluate a variety of risk assessment metrics for collaborative control of a smart wheelchair. One such metric is demonstrated on a wheelchair with a single RGB-D camera in two scenarios: a doorway traversal where the near edge of the doorframe is no longer visible to the camera as the chair makes its turn, and a longer navigation through a typical cluttered office environment.

We present a connection between the viability kernel and maximal reachable sets. Current numerical schemes that compute the viability kernel suffer from a complexity that is exponential in the dimension of the state space. In contrast, extremely efficient and scalable techniques are available that compute maximal reachable sets. We show that under certain conditions these techniques can be used to conservatively approximate the viability kernel for possibly high-dimensional systems. We demonstrate the results on two practical examples, one of which is a seven-dimensional problem of safety in anesthesia.

The solution of a particular Hamilton-Jacobi (HJ) partial differential equation (PDE) provides an implicit representation of reach sets and tubes for continuous systems with nonlinear dynamics and can treat inputs in either worst-case or best-case fashion; however, it can rarely be determined analytically and its numerical approximation typically requires computational resources that grow exponentially with the state space dimension. In this paper we describe a new formulation - also based on HJ PDEs - for reach sets and tubes of systems where some states are terminal integrators: states whose evolution can be written as an integration over time of the other states. The key contribution of this new mixed implicit explicit (MIE) scheme is that its computational cost is linear in the number of terminal integrators, although still exponential in the dimension of the rest of the state space. Application of the new scheme to four examples of varying dimension provides empirical evidence of its considerable improvement in computational speed.

Optimal path planning under full state and map knowledge is often accomplished using some variant of Dijkstra's algorithm, despite the fact that it represents the path domain as a discrete graph rather than as a continuous space. In this paper we compare Dijkstra's discrete algorithm with a variant (often called the fast marching method) which more accurately treats the underlying continuous space. Analytically, both generate a value function free of local minima, so that optimal path generation merely requires gradient descent. We also investigate the use of optimality metrics other than Euclidean distance for both algorithms. These different norms better represent optimal paths for some types of problems, as demonstrated by planning optimal collision-free paths for a multiple robot scenario. When considering approximations consistent with the underlying state space, our conclusion is that fast marching places fewer constraints upon grid connectivity, and that it achieves better accuracy than Dijkstra's discrete algorithm in many but not all cases

Hybrid system theory lies at the intersection of the fields of engineering control theory and computer science verification. It is defined as the modeling, analysis, and control of systems that involve the interaction of both discrete state systems, represented by finite automata, and continuous state dynamics, represented by differential equations. The embedded autopilot of a modern commercial jet is a prime example of a hybrid system: the autopilot modes correspond to the application of different control laws, and the logic of mode switching is determined by the continuous state dynamics of the aircraft, as well as through interaction with the pilot. To understand the behavior of hybrid systems, to simulate, and to control these systems, theoretical advances, analyses, and numerical tools are needed. In this paper, we first present a general model for a hybrid system along with an overview of methods for verifying continuous and hybrid systems. We describe a particular verification technique for hybrid systems, based on two-person zero-sum game theory for automata and continuous dynamical systems. We then outline a numerical implementation of this technique using level set methods, and we demonstrate its use in the design and analysis of aircraft collision avoidance protocols and in verification of autopilot logic.

We address the problem of generating provably-safe conflict resolution maneuvers for aircraft in uncertain environments. We assume that a maneuver is composed of a sequence of flight modes, which are segments of constant heading, of constant bank angle, or of constant airspeed. Each of these flight modes has associated to it the kinematics of the aircraft, and hence the maneuver is a hybrid system. While the flight modes are defined ahead of time, their sequencing and parameter values do not necessarily have to be. We present an algorithm for generating provably safe maneuvers, which is based on a general procedure for designing controllers for hybrid systems. The result is a maneuver, proven to be safe within the limits of the models used, which is a familiar sequence of commands easily executable by the flight management systems. The maneuvers may be viewed as protocols, or "rules of the road", and are well-defined for each conflict scenario. We present results for two example maneuvers.