Introduction

1.1 Collision-free navigation of wheeled robots among moving and steady obstacles

Autonomous navigation of unmanned vehicles is a classic research area in robotics, which gives rise to a whole variety of approaches well documented in literature. Both single and multiple coordinated mobile robots offer great perspectives in many applications, such as industrial, office, and agricultural automation; search and rescue; and surveillance and inspection (we refer the reader to [1, 2] for a more comprehensive list of potential applications). For example, because of lightweights, inexpensive components, and low power consumptions, unmanned aerial and ground vehicles have been used greatly for plenary surveillance and for a variety of applications in hazardous and complex environments to mitigate the risk for humans; see, e.g., [3–6] and references therein. Such applications often involve limitations on communications that require the robotic vehicle to operate autonomously for extended periods of time and distances. In such situations, unmanned vehicles should be equipped with an automatic navigation system by which they can move autonomously and safely operate in populated environments. In all these cases, navigation involves a series of common problems, with collision avoidance in some form being almost universally required.

Moreover, the capacity of safely operating in dynamic and a priori unknown environments is a key issue for most real-life applications of mobile robotics. Despite extensive research, this fundamental problem still represents a real challenge, mostly because of the numerous uncertainties inherent in typical scenarios. This challenge can be much enhanced by deficiency in perception abilities and computational power of the robot, as well as by restrictions on its mobility due to nonholonomic kinematic constraints, limited control range, and under-actuation.

In order to operate in a cluttered environment, an autonomous unmanned vehicle should be able to detect and avoid the enroute obstacles. Typical objectives include, but are not limited to, overall movement in a given direction or reaching a target point through the obstacle-free part of the environment [7]. This may involve bypassing an obstacle, especially a long one, in close range within a safety margin [8]. This maneuver is similar to border patrolling, which mission is of self-interest for many applications. Substantial effort has been made in robotics research for solution of these problems. The rich variety of available relevant algorithms will be specifically surveyed in a special Chapter 3. With a focus on the planning horizon, they can be very broadly classified into global and local planners [9].

Global sensor-based planners use both a priori and sensory information to build a comprehensive model of the environment and then try to find a completed and best possible navigation solution on the basis of this model [7, 10–16]. In effect, this means the environment is assumed to be known to a substantial extent prior to the solution of a navigation task. Within this framework, a variety of techniques has been developed. Their general survey is postponed until Chapter 3 but can also be found in, e.g., [17, 18]; some samples intended to handle dynamic scenes are given by velocity obstacles [17, 19], nonholonomic planners [20], and state-time space [21–23] approaches. Global planners can often be accompanied with guarantees of not only collision avoidance but also achieving a global navigation objective provided that certain general assumptions about the scene are satisfied. On the negative side, global planners are, by and large, computationally expensive and hardly suit real-time implementation. NP-hardness, the mathematical seal for intractability, was established for even the simplest problems of dynamic motion planning [24]. A partial remedy was offered in the form of randomized architectures [25, 26]. At the same time, all global planners are hardly troubled, up to failure in path generation, by unpredictability of the scene, as well as by data incompleteness and erroneousness typical for onboard perception. These disadvantages are shared by hybrid approaches that use global planning as a backbone of navigation [15, 20, 27–30].

Conversely, local planners use onboard sensory data about only a nearest fraction of an unknown environment for iterative re-computation of a short-horizon path [9, 31–33]. This reduces the computational burden toward implementability in real time but makes the ultimate result of iterations an open issue. A detailed overview of the respective obstacle avoidance techniques will be given in Chapter 3. Many of them, e.g., the dynamic window [34, 35], curvature velocity [36], lane curvature [37], boundary following [32, 33], and tangent graph based [16] approaches, treat the obstacles as static. This is a particular case of predictably moving obstacles, which are assumed by methods like velocity obstacles [17, 19], collision cones [38], or inevitable collision states [39, 40]. These methods tend to be computationally expensive, are based on access to the obstacles’ full velocities, and assume a modest or minor rate of their change. However, velocity estimation remains a challenging task in practice, and predictability of the scene ranges from full to none in the real world [41]. A medium level of predictability is that with uncertainty, where non-conservative estimates of future obstacle positions can be put in place of exact prognosis [17, 42]. However, these and other approaches [19, 38–40] take in effect excessive precautions against collisions with obstacles. As a result, they may be stuck in cluttered scenes and tend toward bypassing dense clusters of obstacles as a whole, even if a better and sometimes the only option is a permeating route. In hardly predictable complex environments, safety typically concerns only a nearest future, and its propagation until the end of the experiment is not guaranteed [42]. Some local planners, such as Virtual Force Field [43], Potential Field [44, 45], Vector Field Histogram [46], Certainty Grid [47], Nearness Diagram [48] methods, use elements of global modeling by assuming awareness about the scene above the level given by the current sensory data. A common problem with local methods is that many of them are heuristic and not based on mathematical models such as kinematic equations of the vehicles and nonholonomic constraints on their motion, which is a severe limitation in practice. For dynamic environments, fully actuated robots were mostly studied up to now.

Because of inevitable failure scenarios, a common deficiency of the previous research on local planners is the lack of global convergence results that guarantee achieving the primary objective in dynamic environments [49]. At best, rigorous analysis examined an isolated bypass of an obstacle during which the other obstacles were neglected until the bypass end, with an idea that thereafter, the robot focuses on the main goal. However, in cluttered dynamic scenes, bypasses may be systematically intervened by companion obstacles so that no bypass is completed, whereas the robot almost constantly performs obstacle avoidance. Ultimate goal was left, by and large, beyond the scope of theoretical analysis, especially for cluttered unpredictable environments, like a dense crowd of people. However, it is in these cases that rigorous quantitative delineation between failure and success scenarios is highly important since by its own right, any experimentation is not convincing enough due to horizonless diversity of feasible scenarios. Another deficiency is that moving obstacles were viewed as rigid bodies undergoing only translational motions and often of the simplest shapes (e.g., discs [45, 50–52] or polygons [53, 54]). Finally, assumed awareness of the obstacles often meant access to their possibly “invisible” parts (in order to determine, e.g., the disc center [45, 50, 51] or angularly most distant polygon vertex [54]) or full velocity [45, 51, 54].

The basic strong and weak points of local planners attain apotheosis at reactive controllers. For them, the planning horizon collapses into a point so that the controller directly converts the current observation into the current control. Purely reactive approaches are exemplified by [51, 55–59], as well as by biologically inspired methods [32, 33, 52, 60, 61]. Examples concerning nonholonomic robots include artificial potential approach, combined with sliding mode control for gradient climbing [50, 53], and kinematic control based on polar coordinates and...