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

As previously explained, path planning may be understood as a strategic competence that deals with the long‐term goal of a robot (or a group of robots), that is, depending on the mission to be achieved by the robot different routes or regions must be visited or avoided based on logic or temporal requirements [13, 14, 66, 88, 118]. As [13, 14] explain, this way to define the path planning problem can be solved by following a hierarchical, three‐level process (see Figure 1.6). At the top of this hierarchy is the specification level. Here is exactly where strategies based on cell decomposition play a key role. Recall that cell decomposition is based on partitioning the free configuration space into a finite set of regions that can be safely traversed by the robot. These set of regions can be represented as a graph. After this, the execution level is responsible for generating an optimal path, for example, by minimizing the expected traveled distance and/or accounting for the proximity to obstacles. Finally, the implementation level ensures that the reference trajectory traversing the sequence of cells given by the path previously obtained is followed by the actual robot. The main limitation of this way to formulate the path planning problem is that specifications like “reach cell A, and then cell B, and stay there for all future times” cannot be properly addressed. This is what motivates the use of symbolic approaches for the specification of high‐level path planning missions [13, 66].

Figure 1.6 Path planning levels. Path planning levels of standard navigation problem.

One possible necessity of using high‐level specifications instead of standard navigation problem (reaching a final configuration) is in the factories of the future, where workers and robots will cooperate in fulfilling complex tasks, in order to obtain as soon as possible the products requested by the consumers [55, 179, 189]. The robots should automatically adapt and optimize the usage of these shared frameworks [50, 197], and one of the important aspects is to automatically compute collision‐free trajectories. Since the number of mobile robots could be high, it is important to have computationally attractive techniques to plan trajectories for teams of robots.

There are several formalisms for specifying the high‐level path planning goals explained previously, from which we focus on two: Linear‐time Temporal Logic (LTL) formulas [10] and Boolean‐based formulas [147]. These approaches and their applications will be largely explained in subsequent chapters, as only a brief description of them is given here. Other formalisms, such as Computation Tree Logic (CTL) [10] and generalized reactivity (1) formula (GR(1)) [170], are also employable to capture similar specifications.

Linear‐time temporal logic is a general‐purpose mathematical language for describing linear‐time problems, which was first pointed out by Amir Pnueli in 1977 [171]. In the specific context of mobile robotics, the set of mathematical operators defined by LTL can be used for encoding rules about the sequence of paths that a robot (or a team of robots) should follow. The success of LTL is that high‐level specifications defined in a natural human level can be easily translated into LTL statements. Although LTL formulation has demonstrated a significant contribution to the field of mobile robotics [13, 66, 111], it generally demands a high computation load.

Figure 1.7 shows an example involving a path planning problem that can be solved by using the LTL formulation. Imagine the user wants to use the robot for performing a surveillance activity. As a result, he/she defines the following high‐level mission: “the robot must reach A and then B, once it reaches B, the robot must move from B to A and back constantly”. The first step would be to run a cell‐decomposition‐based algorithm in order to partition the free configuration space into a finite set of regions. After that, the LTL formula and a suitable approach would find the sequence of steps to go from the current position of the robot to A and then to B. Finally, the robot would move from B to A and back constantly. Should the mission required only “the robot must reach A and then B”, a Boolean‐based formalism for capturing it and a corresponding method based on Petri nets could be used, as it will be detailed in subsequent chapters. Notice that at the implementation level, the lowest level, the motion controller should ensure that the robot follows as closely as possible the trajectories generated by the path planning execution level.

Figure 1.7 Expressive tasks. Meaning of expressive tasks.