China
Africa
Explore chapters and articles related to this topic
Orienteering and Coverage
Published in Yasmina Bestaoui Sebbane, Multi-UAV Planning and Task Allocation, 2020
The Boustrophedon cellular decomposition (BCD) algorithm is an extension to the seed spreader algorithm, which guaranteed complete coverage of bounded environments, with a variety of control Morse functions. Other typical patterns include inward and outward spirals, random walks and wall following or contour following. Unfortunately, these planners need absolute localization or not taking UAV kinematics into account and not dealing efficiently with obstacles. In terms of tasks, the UAV motion is not the primary one, but it is a necessity to perform the main coverage task. When multiple UAVs are used, a previous decomposition of the field to cover is required. Two approaches are commonly used: exact cell decompositions and approximate cell decomposition. After this task, the path for every vehicle to cover the area assigned is computed.
A* Search and Some Admissible Heuristics for It
Published in Don Potter, Manton Matthews, Moonis Ali, Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 2020
Antti Autere, Johannes Lehtinen
Cell decomposition approaches are based on decomposing (either exactly or approximately) the set of free configurations into simple non-overlapping regions called cells, e.g. [ea86] and [Lat91]. The adjacency of these cells is then represented in a connectivity graph that is searched for a path. The drawback is that all the cells must be constructed before a path can be found. However, recently a hierarchical method to do this has been reported in [BH93] and [BH95]. Roadmap or skeleton approaches attempt to retract or map the set of feasible motions onto a network of one-dimensional lines, called the roadmap, skeleton, visibility graph or subgoal network. The path planner tries to connect the start and goal configurations to this network and then search it to find the (optimum) path. The roadmap is usually generated by preprocessing (sampling) the robot’s configuration space. There are many ways to do this. Examples of this approach are found in [Cla90], [Lat91], [KL94b] and [KL94a] to mention a few.
Optimal motion planning using navigation measure
Published in International Journal of Control, 2018
The cell decomposition method relies on partition of the configuration space into a finite number of cells in each a collision-free path. The global path is then obtained by connecting the local collision-free path between adjacent cells (Lozano-Pérez, 1981). The artificial potential field method was introduced to robotics research in thesis research by Khatib (1986). In the artificial potential field method, a collision-free trajectory is generated by the robot moving locally, according to forces defined by the negative gradient of an artificial potential function. This function is designed to provide attractive forces that push toward goal and repulsive forces, which push the robot away from the obstacles. The control law using artificial potential field methods is feedback in nature because the control action is computed at each instant of time, depending upon the current state (Barraquand, Langlois, & Latombe, 1992; Hwang & Ahuja, 1992). These approaches, using cell-decomposition and roadmaps, are open loop in nature. The problem with artificial potential field methods is the possible existence of local minima, where a robot might become trapped. Potential functions for motion planning are refined in the work (Rimon & Koditschek, 1992). In particular, potential functions, which do not have a local minima, are defined as navigation functions. Navigation functions have only one minimum at the desired goal configuration. The problem with the navigation functions is no systematic procedure to construct one exists.
Density-aware decentralised multi-agent exploration with energy constraint based on optimal transport theory
Published in International Journal of Systems Science, 2022
Kooktae Lee, Rabiul Hasan Kabir
Coverage Path Planning (CPP) refers to a method to synthesise a robot path for passing over all points of an area or volume of interest. Many different approaches have been developed to solve the multi-agent CPP problem, which is further divided into several sub-areas. The cell decomposition method transforms the obstacle-free space into simple, non-overlapping regions called cells. The union of all the cells can be swept by a robot using simple motions. A lawnmower path is an example of such a simple motion through a zigzag pattern as in the literature (Azpúrua et al., 2018). The general cell decomposition technique is applied to the multi-agent case (Avellar et al., 2015; Xu et al., 2014), where the generated graph is utilised to divide the sweeps among the team of robots by solving a vehicle routing problem. The broadly used geometric-based method in the multi-agent CPP, which is based on visibility graphs that includes a set of points and obstacles, is the Voronoi Diagrams (Adaldo et al., 2017; Yazici et al., 2013). Incremental random planners refer to sampling-based methods such as Rapidly exploring Random Trees (RRT) and Probabilistic Road Map (PRM). These methods have been widely investigated with many variations including ant colony robot motion planning (Mohamad et al., 2005), exploration of implicit roadmaps in multi-agent motion planning (Solovey et al., 2015), mutual information-based multiple autonomous underwater vehicles path planning (Cui et al., 2015), a multi-agent system for vacuum cleaning (Nikitenko et al., 2014), to list a few. Unfortunately, most of these methods have only focused on the entire coverage of the given domain without considering priority or importance. Although little works and limited researches (Li et al., 2019a; Yehoshua et al., 2016) have been done in the multi-agent CPP reflecting priority or hazardous fields, these methods have not utilised or provided any metrics to quantify how the robot trajectories obtained by their methods well represent the given priority. Thus, no quantitative measure is available.