Safe autonomous navigation in a priori unknown environments is an essential skill for mobile robots to reliably and adaptively perform diverse tasks (e.g., delivery, inspection, and interaction) in unstructured cluttered environments. Hybrid metric-topological maps, constructed as a pose graph of local submaps, offer a computationally efficient world representation for adaptive mapping, planning, and control at the regional level. In this paper, we consider a pose graph of locally sensed star-convex scan regions as a metric-topological map, with star convexity enabling simple yet effective local navigation strategies. We design a new family of safe local scan navigation policies and present a perception-driven feedback motion planning method through the sequential composition of local scan navigation policies, enabling provably correct and safe robot navigation over the union of local scan regions. We introduce a new concept of bridging and frontier scans for automated key scan selection and exploration for integrated mapping and navigation in unknown environments. We demonstrate the effectiveness of our key-scan-based navigation and mapping framework using a mobile robot equipped with a 360° laser range scanner in 2D cluttered environments through numerical ROS-Gazebo simulations and real hardware experiments.

As a simple and robust mobile robot base, differential drive robots that can be modelled as a kinematic unicycle find significant applications in logistics and service robotics in both industrial and domestic settings. Safe robot navigation around obstacles is an essential skill for such unicycle robots to perform diverse useful tasks in complex cluttered environments, especially around people and other robots. Fast and accurate safety assessment plays a key role in reactive and safe robot motion design. In this paper, as a more accurate and still simple alternative to the standard circular Lyapunov level sets, we introduce novel conic feedback motion prediction methods for bounding the close-loop motion trajectory of the kinematic unicycle robot model under a standard unicycle motion control approach. We present an application of unicycle feedback motion prediction for safe robot navigation around obstacles using reference governors, where the safety of a unicycle robot is continuously monitored based on the predicted future robot motion. We investigate the role of motion prediction on robot behaviour in numerical simulations and conclude that fast and accurate feedback motion prediction is key for fast, reactive, and safe robot navigation around obstacles.

As a parametric polynomial curve family, Bézier curves are widely used in safe and smooth motion design of intelligent robotic systems from flying drones to autonomous vehicles to robotic manipulators. In such motion planning settings, the critical features of high-order Bézier curves such as curve length, distance-to-collision, maximum curvature/velocity/acceleration are either numerically computed at a high computational cost or inexactly approximated by discrete samples. To address these issues, in this article we present a novel computationally efficient approach for adaptive approximation of high-order Bézier curves by multiple low-order Bézier segments at any desired level of accuracy that is specified in terms of a Bézier metric. Accordingly, we introduce a new Bézier degree reduction method, calledparameterwise matching reduction, which approximates Bézier curves more accurately compared to the standard least squares and Taylor reduction methods. We also propose a new Bézier metric, called themaximum control-point distance, that can be computed analytically, has a strong equivalence relation with other existing Bézier metrics, and defines a geometric relative bound between Bézier curves. We provide extensive numerical evidence to demonstrate the effectiveness of our proposed Bézier approximation approach. As a rule of thumb, based on the degree-one matching reduction error, we conclude that an$ n^{\rm{th}} $-order Bézier curve can be accurately approximated by$3(n-1)$quadratic and$6(n-1)$linear Bézier segments, which is fundamental for Bézier discretization.

This paper considers the problem of fast and safe autonomous navigation in partially known environments. Our main contribution is a control policy design based on ellipsoidal trajectory bounds obtained from a quadratic state-dependent distance metric. The ellipsoidal bounds are used to embed directional preference in the control design, leading to system behavior that is adapted to local environment geometry, carefully considering medial obstacles while paying less attention to lateral ones. We use a virtual reference governor system to adaptively follow a desired navigation path, slowing down when system safety may be violated and speeding up otherwise. The resulting controller is able to navigate complex environments faster than common Euclidean-norm and Lyapunov-function-based designs, while retaining stability and collision avoidance guarantees.

A fundamental challenge of mobile sensor networks is automated active reconfiguration of sensors in response to environmental stimuli in order to maximize their total sensing quality (or minimize their total sensing cost) of events occurring over an environment. In this paper, given an event distribution over a convex environment, we consider mobile isotropic sensors with adjustable sensing range and propose a new family of provably correct reactive coverage control algorithms for both continuous- and discrete-time sensor dynamics. The proposed coverage control algorithms constantly (re)configure sensor positions and sensing ranges in order to minimize a statistical distance, in particular, an$f$-divergence, between the event distribution over the environment and the overall event detection probability of sensors. We show that the standard Voronoi-based coverage control law of homogeneous mobile sensor networks is a special case of our framework where the event detection probability of each sensor has a Gaussian form, the statistical distance is set to be the Kullback–Leibler (KL) divergence and sensor allocation is performed based on Voronoi diagrams. To increase the practicality of our framework, we also present its integration with a Voronoi-based collision avoidance strategy for disk-shaped sensor bodies and its extension to differential drive sensor dynamics, while retaining the stability properties.

A challenge of pan/tilt/zoom (PTZ) camera networks for efficient and flexible visual monitoring is automated active network reconfiguration in response to environmental stimuli. In this paper, given an event/activity distribution over a convex environment, we propose a new provably correct reactive coverage control algorithm for PTZ camera networks that continuously (re) configures camera orientations and zoom levels (i.e., angles of view) in order to locally maximize their total coverage quality. Our construction is based on careful modeling of visual sensing quality that is consistent with the physical nature of cameras, and we introduce a new notion of conic Voronoi diagrams, based on our sensing quality measures, to solve the camera network allocation problem: that is, to determine where each camera should focus in its field of view given all the other cameras' configurations. Accordingly, we design simple greedy gradient algorithms for both continuous-and discrete-time first-order PTZ camera dynamics that asymptotically converge a locally optimal coverage configuration. Finally, we provide numerical and experimental evidence demonstrating the effectiveness of the proposed coverage algorithms.

The efficiency of sampling-based motion planning algorithms is dependent on how well a steering procedure is capable of capturing both system dynamics and configuration space geometry to connect sample configurations. This paper considers how metrics describing local system dynamics may be combined with convex subsets of the free space to describe the local behavior of a steering function for sampling-based planners. Subsequently, a framework for using these subsets to extend the steering procedure to incorporate this information is introduced. To demonstrate our framework, three specific metrics are considered: the LQR cost-to-go function, a Gram matrix derived from system linearization, and the Mahalanobis distance of a linear-Gaussian system. Finally, numerical tests are conducted for a second-order linear system, a kinematic unicycle, and a linear-Gaussian system to demonstrate that our framework increases the connectivity of sampling-based planners and allows them to better explore the free space.

This paper considers the problem of completing assemblies of passive objects in nonconvex environments, cluttered with convex obstacles of unknown position, shape and size that satisfy a specific separation assumption. A differential drive robot equipped with a gripper and a LIDAR sensor, capable of perceiving its environment only locally, is used to position the passive objects in a desired configuration. The method combines the virtues of a deliberative planner generating high-level, symbolic commands, with the formal guarantees of convergence and obstacle avoidance of a reactive planner that requires little onboard computation and is used online. The validity of the proposed method is verified both with formal proofs and numerical simulations.

In robotics, it is often practically and theoretically convenient to design motion planners for approximate low-order (e.g., position-or velocity-controlled) robot models first, and then adapt such reference planners to more accurate high-order (e.g., force/torque-controlled) robot models. In this paper, we introduce a novel provably correct approach to extend the applicability of low-order feedback motion planners to high-order robot models, while retaining stability and collision avoidance properties, as well as enforcing additional constraints that are specific to the high-order models. Our smooth extension framework leverages the idea of reference governors to separate the issues of stability and constraint satisfaction, affording a bidirectionally coupled robot-governor system where the robot ensures stability with respect to the governor and the governor enforces state (e.g., collision avoidance) and control (e.g., actuator limits) constraints. We demonstrate example applications of our framework for augmenting path planners and vector field planners to the second-order robot dynamics.

Sampling-based algorithms offer computationally efficient, practical solutions to the path finding problem in high-dimensional complex configuration spaces by approximately capturing the connectivity of the underlying space through a (dense) collection of sample configurations joined by simple local planners. In this paper, we address a long-standing bottleneck associated with the difficulty of finding paths through narrow passages. Whereas most prior work considers the narrow passage problem as a sampling issue (and the literature abounds with heuristic sampling strategies) very little attention has been paid to the design of new effective local planners. Here, we propose a novel sensory steering algorithm for sampling-based motion planning that can “feel” a configuration space locally and significantly improve the path planning performance near difficult regions such as narrow passages. We provide computational evidence for the effectiveness of the proposed local planner through a variety of simulations which suggest that our proposed sensory steering algorithm outperforms the standard straight-line planner by significantly increasing the connectivity of random motion planning graphs.

We reconsider the problem of reactive navigation in sphere worlds, i.e., the construction of a vector field over a compact, convex Euclidean subset punctured by Euclidean disks, whose flow brings a Euclidean disk robot from all but a zero measure set of initial conditions to a designated point destination, with the guarantee of no collisions along the way. We use power diagrams, generalized Voronoi diagrams with additive weights, to identify the robot's collision free convex neighborhood, and to generate the value of our proposed candidate solution vector field at any free configuration via evaluation of an associated convex optimization problem. We prove that this scheme generates a continuous flow with the specified properties. We also propose its practical extension to the nonholonomically constrained kinematics of the standard differential drive vehicle.

In distributed mobile sensing applications, networks of agents that are heterogeneous, respecting both actuation as well as body and sensory footprint, are often modelled by recourse to power diagrams - generalized Voronoi diagrams with additive weights. In this paper, we adapt the body power diagram to introduce its “free subdiagram,” generating a vector field planner that solves the combined sensory coverage and collision avoidance problem via continuous evaluation of an associated constrained optimization problem. We propose practical extensions (a heuristic congestion manager that speeds convergence and a lift of the point particle controller to the more practical differential drive kinematics) that maintain the convergence and collision guarantees.

We introduce the use of hierarchical clustering for relaxed deterministic coordination and control of multiple robots. Traditionally, an unsupervised learning method, hierarchical clustering offers a formalism for identifying and representing spatially cohesive and segregated robot groups at different resolutions by relating the continuous space of configurations to the combinatorial space of trees. We formalize and exploit this relation, developing computationally effective reactive algorithms for navigating through the combinatorial space in concert with geometric realizations for a particular choice of the hierarchical clustering method. These constructions yield computationally effective vector field planners for both hierarchically invariant as well as transitional navigation in the configuration space. We apply these methods to the centralized coordination and control of n perfectly sensed and actuated Euclidean spheres in a d-dimensional ambient space (for arbitrary n and d). Given a desired configuration supporting a desired hierarchy, we construct a hybrid controller that is quadratic in n and algebraic in d and prove that its execution brings all but a measure zero set of initial configurations to the desired goal, with the guarantee of no collisions along the way.

An important motivation for work on legged robots has always been their potential for high-performance locomotion on rough terrain. Nevertheless, most existing control algorithms for such robots either make rigid assumptions about their environments or rely on kinematic planning at low speeds. Moreover, the traditional separation of planning from control often has negative impact on the robustness of the system. In this paper, we introduce a new method for dynamic, fully reactive footstep planning for a planar spring–mass hopper, based on a careful characterization of the model dynamics and the design of an associated deadbeat controller, used within a sequential composition framework. This yields a purely reactive controller with a large domain of attraction that requires no explicit replanning during execution. We show in simulation that plans constructed for a simplified dynamic model can successfully control locomotion of a more complete model across rough terrain. We also characterize the performance of the planner over rough terrain and show that it is robust against both model uncertainty and measurement noise without replanning.

The Spring-Loaded Inverted Pendulum (SLIP) model has long been established as an effective and accurate descriptive model for running animals of widely differing sizes and morphologies, while also serving as a basis for several hopping robot designs. Further research on this model led to the discovery of several analytic approximations to its normally nonintegrable dynamics. However, these approximations mostly focus on steady-state running with symmetric trajectories due to their linearization of gravitational effects, an assumption that is quickly violated for locomotion on more complex terrain wherein transient, non-symmetric trajectories dominate. In this paper, we introduce a novel gravity correction scheme that extends on one of the more recent analytic approximations to the SLIP dynamics and achieves good accuracy even for highly non-symmetric trajectories. Our approach is based on incorporating the total effect of gravity on the angular momentum throughout a single stance phase and allows us to preserve the analytic simplicity of the approximation to support our longer term research on reactive footstep planning for dynamic legged locomotion. We compare the performance of our method in simulation to two other existing analytic approximations and show that it outperforms them for most physically realistic non-symmetric SLIP trajectories while maintaining the same accuracy for symmetric trajectories.

The main driving force behind research on legged robots has always been their potential for high performance locomotion on rough terrain and the outdoors. Nevertheless, most existing control algorithms for such robots either make rigid assumptions about their environments (e.g flat ground), or rely on kinematic planning at low speeds. Moreover, the traditional separation of planning from control often has negative impact on the robustness of the system against model uncertainty and environment noise. In this paper, we introduce a new method for dynamic, fully reactive footstep planning for a simplified planar spring-mass hopper, a frequently used model for running behaviors. Our approach is based on a careful characterization of the model dynamics and an associated deadbeat controller, used within a sequential composition framework. This yields a purely reactive controller with a very large, nearly global domain of attraction that requires no explicit replanning during execution. Finally, we use a simplified hopper in simulation to illustrate the performance of the planner under different rough terrain scenarios and show that it is extremely robust to both model uncertainty and measurement noise.