Читать книгу Path Planning of Cooperative Mobile Robots Using Discrete Event Models - Cristian Mahulea - Страница 16

A fundamental task for any mobile robot is its ability to plan collision‐free trajectories from a start to a goal position or visiting a series of positions, i.e. regions of interest, among a collection of (static) obstacles. This is the robot's cognitive level. Cognition generally represents the purposeful decision‐making and execution that a system utilizes to achieve its highest‐order goals. Given a map and a goal position (or a list of high‐level goals), path planning involves identifying a trajectory that will cause the robot to reach the goal position (a 2D point) or pose (a 2D point and an orientation) when executed [35, 135, 191]. It bears mentioning that position refers to the longitudinal and lateral coordinates in a Cartesian frame. Pose also considers the orientation.

Path planning comprises the highest level within a typical navigation architecture of a mobile robot. As observed in Figure 1.3, there are four big modules or layers. The second layer in this navigation architecture includes the motion controller (or trajectory following strategy), which is responsible for generating the control actions in such a way that the robot follows as accurately as possible the reference trajectory provided by the path planning layer. These control actions will be determined according to the error between the current robot's position and the next desired waypoint. The third layer deals with the low‐level PID controllers that ensure that the control actions generated by the motion controller are reached by the robot actuators, i.e. wheel motors. As explained before, it is crucial for the motion controller to know the current position of the robot; this is calculated by the last layer in the robot's navigation architecture: the localization layer. Here, a set of sensors are employed to get the robot's position as accurately as possible. Another significant observation about this traditional navigation architecture is that the execution time or the sampling time of each layer is different. For example, the time to get a response from the path planning layer is on the order of minutes or seconds, the time for the motion control layer is on the order of seconds or hundreds of milliseconds, and the fastest layer comprises the low‐level controllers that run on the order of milliseconds.

Figure 1.3 Navigation architecture of a mobile robot. Example of a navigation architecture of a mobile robot (University of Almeria's Fitorobot robot) [78].

The history of robot path planning began with the early computer‐controlled robots, i.e. SRI Shakey robot. One of the pioneering references in this field is the book “Robot Motion Planning” authored by Jean‐Claude Latombe in 1980 [132],¹. At that time, the most advanced planners were barely able to compute collision‐free paths for objects moving in planar workspaces. In the 1990s, researchers working in this field faced another challenge: planning motions in the presence of kinematic constraints like non‐holonomic robot systems², e.g. a car that cannot rotate around its axis without also changing its position [133]. At the beginning of the twenty‐first century, robot planners could be applied to robots with many degrees of freedom in complex environments, coordinate multiple robots, and handling dynamic environments. In 2005 and 2006 other key references appeared in the field of mobile robotics: “Principles of Robot Motion: Theory, Algorithms, and Implementations” by Choset et al. [35] and “Planning Algorithms” by Stephen LaValle [135]. These books opened the door to multiple milestones in this field, as roadmaps, cell decomposition methods, and sampling‐based planning algorithms.

Traditional planning algorithms, sometimes called combinatorial or exact algorithms, build discrete representations of a given environment, i.e. a map, without losing any information. Some of them are complete, which means that they must find a solution if one exists; otherwise, they report failure [135]. On the contrary, sampling‐based solutions sparsely sample the world map and conduct discrete searches that utilize these samples. This paradigm sacrifices completeness with the benefit of a faster computation [135].

As Figure 1.4 shows, there are two big areas in the field of path planning in mobile robotics: combinatorial or exact algorithms and sampling‐based planning. This book focuses on the first category, but the second category is also described for completeness purposes. Notice that the area of reactive navigation has also been included here for completeness purposes. Recall that the main difference between path planning approaches and reactive navigation is that in the first case a map of the environment is needed.

The first category, exact algorithms, can be divided into two areas: road map planning and cell decomposition. The road map planning approaches capture the connectivity of the robot's free space in a network of 2D curves or lines, called road maps. Once a road map is constructed, it is used as a network of road segments. At this point, path planning is reduced to connecting the initial and goal position of the robot to the road network and then searching for a series of roads from the initial robot position to its goal position [191]. To this category belong two well‐known methods in the field of mobile robotics: visibility graph and Voronoi diagram.

The visibility graph (or V‐graph), formally described by Lozano‐Perez and Wesley in the 1970s [142], represents a complete and easy to implement algorithm. This algorithm is based on constructing an undirected graph where edges come as close as possible to obstacles, then resulting in minimum‐length paths. An important aspect is that obstacles can be inflated in order to avoid an incident where the robot could pass by too close to them, which could lead to collisions [58]. The main drawbacks of this algorithm are that it can demand a high computation time for getting a trajectory in environments with complicated obstacles, and some points of the path are too close to obstacles if inflation is not used. The fast dynamic visibility graph (DVG) approach proposed in [100] represents an efficient implementation of the traditional V‐graph. The V‐graph has been largely used by the robotics community from Shakey in the 1970s to recent publications like [39], where the V‐graph algorithm is used to find the obstacle‐free path after processing digital images acquired by a camera onboard a mobile robot.

The Voronoi diagram was proposed by G.F. Voronoi at the end of the nineteenth century and since then it has been widely used in many areas such as: mathematics, physics, astronomy, geographical information systems, computer graphics, image processing, and robotics. In contrast to the V‐graph approach, a Voronoi diagram tends to maximize the distance between the robot and obstacles in the map, that is, roads stay as far away as possible from obstacles. Therefore, there is no need to inflate the obstacles. As in the V‐graph after the set of roads are determined, a graph search algorithm is applied to estimate the best route between the desired points. An application of the Voronoi diagram in mobile robotics appears in [79]. Here, this algorithm is used by an agricultural robot to move in a greenhouse. There is also a broad field of research combining the advantages of the visibility graph (shortest routes) with those of the Voronoi diagram (maximum distance from the obstacles); see, for example, [151, 211].

Figure 1.4 Path planning methods. Main categories for path planning in mobile robotics and examples of some well‐known methods for each of them.

The second big category comprising exact planning algorithms is cell decomposition. This strategy is based on partitioning the free configuration space into a finite set of regions that can be safely traversed by a robot. Cell decompositions are often employed in high‐level planning approaches where the robot may visit some regions based on logic or temporal requirements (this feature is extended in Section 1.4 and in subsequent chapters).

It bears mentioning that the exact methods further need graph search algorithms in order to finally obtain the optimal route connecting a series of waypoints. For this aspect, three graph search algorithms that return a minimum cost path are usually employed, namely Dijkstra [53], A* [140, 160, 221], and D* [195]. Dijkstra and A* algorithms are great choices for static graphs with positive known arc weights, with A* additionally requiring a heuristic cost function. The D* algorithm, proposed by Anthony Stentz in 1995 [195], constitutes an extension of the classic A* algorithm for graphs, introduced by Nils J. Nilsson in the 1970s [160]. D* considers the 2D map as a cost map where each weight represents the cost of traversing each cell in the horizontal or vertical direction. For cells corresponding to obstacles we can give a huge cost, so D* finds the path minimizing the total cost of travel. This cost may deal with various aspects such as time to drive across a cell, roughness of the terrain, etc. The key feature of D* is that it supports incremental replanning, that is, the algorithm can replan the initial route while the robot discovers that the world is different from the initial plan. The incremental replanning has a lower computational cost than completely replanning, as would be required by A* [41]. The algorithm D* accounts for many successful applications in mobile robotics. For example, in [84], the D* algorithm is used for generating the optimal route for ground autonomous vehicles. More specifically, the cost function associated with the D* algorithm is configured in such a way that the route connecting two points minimizes the uncertainty associated with the elevation of the 3D points in the maps. This route also avoids points where the robot may experience a high risk of entrapment. After the successful introduction of the D* algorithm, there is a recent and broad body of research dealing with extending the features of this algorithm. Some of those recent algorithms are: D* Lite [125], PHI* [57], and E* [169].

Together with combinatorial or exact planning algorithms, another broad body of research in the field of path planning nowadays is related to sampling‐based planning methods. The first algorithm, called Probabilistic Roadmap (PRM), was proposed by Lydia E. Kavraki and Jean‐Claude Latombe in the 1990s [106]. The advantage of PRM is that relatively few points need to be tested to ascertain that the points and the paths between them are obstacle free [41]. The efficacy of several variations of the PRM algorithm is discussed in [75].

A major drawback of PRM is that it assumes that the robot is a point with omnidirectional capabilities. The Rapidly exploring Random Tree (RRT) algorithm takes into account the model of the robot, e.g. differential‐drive motion [134]. However, the main drawback of RRT is that it does not lead to an optimal path. This aspect is overcome by a variant of RRT called RRT*; this algorithm does guarantee the optimality and can find the optimal trajectory when applied to complex non‐holonomic systems [2, 104, 138]. In recent literature, there are numerous RRT‐based strategies trying to ensure optimality despite uncertainty in the motion of the robot [136, 143].