Recent Advances in Robot Path Planning Algorithms: A Review of Theory and Experiment

Description

The dominant theme of this book is to introduce the different path planning methods and present some of the most appropriate ones for robotic routing; methods that are capable of running on a variety of robots and are resistant to disturbances; being real-time, being autonomous, and the ability to identify high-risk areas and risk management are the other features that will be mentioned in the introduction of the methods. The introduction of the profound significance of the robots and delineation of the navigation and routing theme is provided in the first chapter of the book. The second chapter is concerned with the subject of routing in unknown environments. In the first part of this chapter, the family of bug algorithms including are described. In the following, several conventional methods are submitted. The last part of this chapter is dedicated to the introduction of two recently developed routing methods. In Chapter 3, routing is reviewed in the known environment in which the robot either utilizes the created maps by extraneous sources or makes use of the sensor in order to prepare the maps from the local environment. The robot path planning relying on the robot vision sensors and applicable computing hardware are concentrated in the fourth chapter. The first part of this chapter deals with routing methods supported mapping capabilities. The second part manages the routing dependent on the vision sensor, typically known as the best sensor, within the routing subject. The movement of two-dimensional robots with two or three degrees of freedom is analyzed within the third part of this chapter. In Chapter 5, the performance of a few of the foremost important routing methods initiating from the second to fourth chapters is conferred regarding the implementation in various environments. The first part of this chapter is engaged in the implementation of the algorithms Bug1, Bug2, and Distbug on the pioneering robot. In the second part, a theoretical technique is planned to boost the robot's performance in line with obstacle collision avoidance. This method, underlying the tangential escape, seeks to proceed with the robot through various obstacles with curved corners. In the third and fourth parts of this chapter, path planning in different environments is preceded in the absence and the presence of danger space. Accordingly, four approaches, named artificial fuzzy potential field, linguistic technique, Markov decision making processes, and fuzzy Markov decision making have been proposed in two following parts and enforced on the Nao humanoid robot. Contents Preface Chapter 1 Introduction and Overview Routing, an Ongoing Challenge in Robot Guidance Chapter 2 Path Planning in Unknown Environments Introduction Bug Algorithms Family Indication and Terminology of Bug Algorithms Bug 1 Algorithm Bug 2 Algorithm ALG1 Algorithm ALG2 Algorithm DistBug Algorithm The TangBug Algorithm Surround Tangential Chart Local Tangent Graph Local Minimum Other Bug Algorithms HD-I Algorithm Ave Algorithm VisBug 21 and 22 Algorithms WedgeBug Algorithm CautiousBug Algorithm Three-Dimensional Bug (3DBug) Algorithm Axis-Angle Algorithm Opitm-Bug Algorithm Unknown Bug Algorithm SensBug Algorithm D* Algorithm D* Algorithm Performance without Barriers Case of Taking Obstacles in D* Algorithm into Account Com Algorithm Class 1 Algorithm Rev 1 and Rev 2 Algorithms Two Chosen Methodologies for Routing in Unknown Environments Histograms of Vector Fields Calculation of Each Vector Calculation of Sectors Histogram Calculation How to Use Histogram Designing Path Based on Multi-Strategy Approach Concepts and Definitions Used in the Proposed Multi Strategic Method Building an Environmental Representation Matrix Path Design Methods Based on Multi Strategic Approaches Minimal Method Median Approach Full Method Output of Proposed Multiple Strategy Approach Static Environments Full Dynamic Environment Partial Dynamic Environment Multi Strategic in Action Chapter 3 Path Planning in Known Environments Introduction Feature-Based Guidance Preparing Feature Maps Storing Feature Maps Coinciding Edges Adding Bridges Graph-Based Guidance towards the Target Guidance in Potential Field Calculating Potential Field Vectors at Target and Reference Points Calculating Potential Field Vectors of Barriers Combining Potential Vectors Path Planning Based on Combinational Potential Field Vectors Local Minimum Chapter 4 Path Planning and Robot’s Hardware Introduction Path Planning Based on Mapping Capabilities Mapping Obstacle Maps Using Polygonal and Gridding Methods Hierarchical Maps Topological Maps Feature Maps Robot Path Planning Using Vision Sensors Robot Path Planning Using Rasterizing Configuration Space Method Definition of Configuration Space Making c-Space Equivalent with Physical Space Rasterizing Methods in c-Space Potential Field Methods Vector Presentation in Potential Field Method Bitmap Representation in Potential Field Method Combinational Algorithm Creating Configuration Space Representation Calculating Navigation Function Path Design How to Display Hardware Utilization Testing Algorithms Example 1: Two-Dimensional Robot Motion in R2×S1 Space Example 2: Three-Dimensional Robot Motion (Piano) in R2×S1 Space Chapter 5 Implementation of Path Planning Algorithms Introduction Comparisons among Bug Family Algorithms Implementation Tests and Results An Analytical Method to Avoid Collision of Mobile Robot with Obstacles Target Searching at Open Spaces Kinematic Model of the Robot Position Control in Open Space Rotation Control at Target Stability in Switching Control System Suggested Method Facing Corner-Shaped Obstacles Facing Concave Obstacles Using the Stored Information of the Observed Obstacles Simulation and Laboratory Results Robot Path Planning Using Vision Sensors The Color Models Low-Pass Filter Segmentation and Mode Filter Expansion Schematic Structure of Vision System Path Planning in the Absence of Danger Space Synthetic Potential Field Method The Rectifier Result of Synthetic Potential Field Method Linguistic Method Simplification Result of Linguistic Method Markov Decision Processes Path Planning Results of Markov Decision Processes Fuzzy Markov Decision Processes Result of Fuzzy Markov Decision Processes in the Absence of Danger Space Path Planning in the Presence of Danger Space Disadvantages of Reward Calculation by Linear Relations Reward Calculation by the Fuzzy Inference System Schematic Structure of Fuzzy Markov Decision Processes Results of Fuzzy Markov Decision Processes in the Presence of Danger Space References About the Authors Index Blank Page