Autonomous Mobile Robots
Planning, Navigation and Simulation
- 1st Edition - September 1, 2023
- Imprint: Academic Press
- Author: Rahul Kala
- Language: English
- Paperback ISBN:9 7 8 - 0 - 4 4 3 - 1 8 9 0 8 - 1
- eBook ISBN:9 7 8 - 0 - 4 4 3 - 1 8 9 0 9 - 8
Autonomous Mobile Robots: Planning, Navigation, and Simulation presents detailed coverage of the domain of robotics in motion planning and associated topics in navigatio… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteAutonomous Mobile Robots: Planning, Navigation, and Simulation presents detailed coverage of the domain of robotics in motion planning and associated topics in navigation. This book covers numerous base planning methods from diverse schools of learning, including deliberative planning methods, reactive planning methods, task planning methods, fusion of different methods, and cognitive architectures. It is a good resource for doing initial project work in robotics, providing an overview, methods and simulation software in one resource. For more advanced readers, it presents a variety of planning algorithms to choose from, presenting the tradeoffs between the algorithms to ascertain a good choice.
Finally, the book presents fusion mechanisms to design hybrid algorithms.
- Presents intuitive and practical coverage of all sub-problems of mobile robotics to enable easy comprehension of sophisticated modern-day robots
- Covers a wide variety of motion planning algorithms, giving a near-exhaustive treatment of the domain with thought provoking comparisons between algorithms
- Dives into detailed discussions on robot operating systems and other simulators to get hands-on knowledge without the need of in-house robots
Graduate students learning robotics and senior undergraduate robotics students.
1. An Introduction to Robotics
1.1. Introduction
1.2. Application areas
1.3. Hardware Perspectives
1.3.1 Actuators
1.3.2 Vision Sensors
1.3.3 Proximity and Other Sensors
1.4 Kinematics
1.4.1 Transformations
1.4.2 TF Tree
1.4.3 Manipulators, Forward and Inverse Kinematics
1.4.4 Mobile Robots
1.5. Computer Vision
1.5.1 Calibration
1.5.2 Pre-processing
1.5.3 Segmentation and Detection
1.5.4 Machine Learning
1.5.5 Recognition
1.5.6 Pose and Depth Estimation
1.5.7 Point Clouds and Depth Images
1.5.8 Tracking
1.5.9 Human-Robot Interface
1.6 Grasping
Questions
2. Localization, Mapping, and Control
2.1 Introduction
2.1.1 AI Primer
2.1.2 Localization
2.1.3 Mapping
2.1.4 Planning
2.1.5 Control
2.2 Tracking
2.2.1 Kalman Filters
2.2.2 Extended Kalman Filters
2.2.3 Particle Filters
2.3 Localization
2.3.1 Motion Models
2.3.2 Measurement Model
2.4 Mapping
2.5 Simultaneous Localization and Mapping
2.5.1 EKF-SLAM and Fast-SLAM
2.5.2 Visual Odometry
2.5.3 Bundle Adjustment
2.5.4 Loop Closure
2.5.5 Place Recognition
2.5.6 Dealing with Dynamic Objects
2.5.7 Benefiting from Semantics
2.5.8 Other Approaches
2.6 Control
2.6.1 PID Controller
2.6.2 Mobile Robot Control
2.6.3 Predictive and Optimal Control
2.6.4 Other Control Laws
Questions
3. An Introduction to Motion Planning with Bug Algorithms
3.1. Introduction
3.2. Configuration Space and Problem Formulation
3.3. Objectives
3.4. Assessment
3.4.1 Complexity
3.4.2. Completeness, Optimality and Soundness
3.5. Terminologies
3.6. Bug-0
3.7. Bug-1
3.8. Bug-2
3.9. Tangent Bug
3.10. Practical Implementations
Questions
4. Intelligent Graph Search Basics
4.1. Introduction
4.2 An Overview of Graphs
4.3. Breadth First Search
4.3.1. General Graph Search Working
4.3.2. Algorithm Working
4.3.3. Example
4.4. State Space Approach
4.5. Uniform Cost Search
4.5.1. Algorithm
4.5.2. Example
4.6. A* Algorithm
4.6.1. Heuristics
4.6.2. Algorithm
4.6.3. Example
4.6.4. Admissibility and Consistency
4.6.5 Heuristic Function Design
4.6.6 Sub-Optimal Variants
Questions
5. Graph Search based Motion Planning
5.1. Introduction
5.2. Motion Planning using A* Algorithm
5.2.1. Vertices
5.2.2. Edges
5.2.3. Post-processing and smoothing techniques
5.3. Planning with robot's kinematics
5.4. Planning in dynamic environments with the D* algorithm
5.4.1. D* Algorithm Principles
5.4.2. D* Algorithm
5.4.3. D* Algorithm Example
5.5. Lifelong Planning A*
5.6. D* Lite
5.7. Other Variants
5.7.1. Anytime A*
5.7.2. Theta A*
5.7.3. Learning Heuristics
5.7.4 Learning Real Time A*
5.7.5 ALT heuristics
Questions
6. Configuration Space and Collision Checking
6.1. Introduction
6.2. Configuration and Configuration Space
6.3 Collision Detection and Proximity Query Primer
6.3.1 Collision checking with spheres
6.3.2 Collision checking with polygons for a point robot
6.3.3 Collision checking between polygons
6.3.4 Intersection checks with the GJK Algorithm
6.4 Space Partitioning
6.4.1 k-d tree
6.4.2 Oct-Trees
6.5 Bounding Volume Hierarchy
6.6 Continuous Collision Detection
6.7 Types of maps
6.8 Representations
6.8.1 Point and Spherical Robots
6.8.2 Representation of orientation
6.8.3 Mobile Robots
6.8.4 Manipulators
6.8.5 Composite robots and Multi-Robot Systems
6.9 Distance Functions
6.10 State Spaces
6.11 Topological Aspects
Questions
7. Roadmap and Cell Decomposition based Motion Planning
7.1. Introduction
7.2 Roadmaps
7.3 Visibility graphs
7.3.1 Concepts
7.3.2 Construction
7.3.3 Completeness and Optimality
7.4 Voronoi
7.4.1 Deformation Retracts
7.4.2 Generalized Voronoi Diagram
7.4.3 Construction of GVD: Polygon Maps
7.4.4 Construction of GVD: Grid Maps
7.4.5 Construction of GVD: By a Sensor based Robot
7.4.6 Generalized Voronoi Graph
7.5 Cell Decomposition
7.5.1 Single-Resolution Cell Decomposition
7.5.2 Multi-Resolution Decomposition
7.5.3 Quad-tree approach
7.6 Trapezoids
7.6.1 Construction
7.6.2 Complete Coverage
7.6.3 Non-Polygon Maps
7.7 Other Decompositions
7.8 Navigation Mesh
7.9 Homotopy and Homology
Questions
8. Probabilistic Roadmap
8.1 Introduction to sampling-based motion planning
8.2 Probabilistic Roadmaps
8.2.1 Vertices and Edges
8.2.2 Local Planner
8.2.3 The Algorithm
8.2.4 Completeness and Optimality
8.3 Sampling Techniques
8.3.1 Uniform Sampling
8.3.2 Obstacle-based Sampling
8.3.3 Gaussian Sampling
8.3.4 Bridge Test Sampling
8.3.5 Maximum Clearance Sampling
8.3.6 Medial Axis Sampling
8.3.7 Grid Sampling
8.3.8 Toggle PRM
8.3.9 Hybrid Sampling
8.4 Edge Connection Strategies
8.4.1 Connecting connected components
8.4.2 Disjoint Forest
8.4.3 Expanding Roadmap
8.4.4 Generating Cycle-free roadmaps
8.4.5 Visibility PRM
8.5 Lazy PRM
Questions
9. Rapidly-exploring Random Trees
9.1 Introduction
9.2 The Algorithm
9.2.1 RRT
9.2.2 Goal Biased RRT
9.2.3 Parameters and Optimality
9.3 RRT Variants
9.3.1 Bidirectional RRT
9.3.2 RRT-Connect
9.3.3 RRT*
9.3.4 Lazy RRT
9.3.5 Anytime RRT
9.3.6 Kinodynamic Planning using RRT
9.3.7 Expansive Search Trees
9.3.8 Kinematic Planning by Interior-Exterior Cell Exploration (KPIECE)
9.4 Sampling based Roadmap of Trees
9.5 Parallel implementations of RRT
9.6 Multi-tree Approaches
9.6.1 Local Trees
9.6.2 Rapidly-exploring Random Graphs
9.6.3 CForest
Questions
10. Artificial Potential Field
10.1 Introduction
10.2 Artificial Potential Field
10.2.1 Attractive Potential Modelling
10.2.2 Repulsive Potential Modelling
10.2.3 Artificial Potential Field Algorithm
10.3 Working of Artificial Potential Field in different settings
10.3.1 Artificial Potential Field with a Proximity Sensing Robot
10.3.2 Artificial Potential Field with known maps
10.4 Problems with Potential Fields
10.5 Navigation Functions
10.6 Social Potential Field
10.6.1 Force Modelling
10.6.2 Groups
10.6.3 Other Modelling Techniques
10.7 Elastic Strip
10.7.1 Environment Modelling
10.7.2 Elastic Strip
10.7.3 Modelling
10.7.4 Discussions
10.7.5 Adaptive Roadmap
Questions
11. Geometric and Fuzzy-Logic based Motion Planning
11.1 Introduction
11.2 Velocity Obstacle Method
11.2.1 An intuitive example
11.2.2 Velocity Obstacles
11.2.3 Reachable Velocities
11.2.4 Deciding immediate velocity
11.2.5 Global Search
11.2.6 Variants
11.3 Vector Field Histogram
11.3.1 Modelling
11.3.2 Histogram Construction
11.3.3 Candidate Selection
11.3.4 VFH+
11.3.5 VFH*
11.4 Other Geometric Approaches
11.4.1 Largest Gap
11.4.2 Largest Distance with Non-Geometric Obstacles
11.5 Fuzzy Logic
11.5.1 Classic Logical Rule-based systems
11.5.2 Fuzzy Sets
11.5.3 Fuzzy Operators
11.5.4 Aggregation
11.5.5 Defuzzification
11.5.6 Designing a Fuzzy Inference System
11.6 Training
11.6.1 Gradient-Based Optimization
11.6.2 Direct Rule Estimation
11.6.3 Adaptive Neuro-Fuzzy Inference System
Questions
12. An Introduction to Machine Learning and Neural Networks
12.1 Introduction
12.2 Architecture
12.2.1 Perceptron
12.2.2 Classification Problem
12.2.3 XOR Problem
12.2.4 Activation Functions
12.2.5 Multi-Layer Perceptron
12.2.6 Universal Approximator
12.3 Learning
12.3.1 Bias-Variance Dilemma
12.3.2 Back Propagation Algorithm
12.3.3 Momentum
12.3.4 Convergence and Stopping Criterion
12.3.5 Normalization
12.3.6 Batches
12.3.7 Cross-Validation
12.3.8 Problem Solving with Neural Nets
12.4 Limited Connectivity and Shared Weight Neural Networks
12.5 Recurrent Neural Networks
12.6 Adaptive Neuro-Fuzzy Inference System
Questions
13. Learning-based Robot Motion Planning
13.1 Introduction
13.2. Dataset Creation for Supervised Learning
13.3 Deep Learning
13.4 Auto-Encoders
13.4.1 Auto-Encoders
13.4.2 Stacked Auto-Encoders
13.4.3 De-noising and Sparsity
13.5 Deep Convolution Neural Networks
13.5.1 Convolution
13.5.2 Pooling and Subsampling
13.5.3 Training
13.6 Long-Short Term Memory Networks
13.6.1 Problems with Recurrent Neural Networks
13.6.2 Long-Short Term Memory Networks
13.7 Dealing with a Lack of Data
13.8 Robot Motion Planning with Embedded Neurons
13.9 Robot Motion Planning using Imitation Learning
13.10 Limitations of Imitation Learning
Questions
14. An Introduction to Evolutionary Computation
14.1 Introduction
14.2. Genetic Algorithms
14.2.1. An Introduction to Genetic Algorithms
14.2.2. Real Coded Genetic Algorithms
14.2.3. Selection
14.2.4. Crossover
14.2.5. Mutation
14.2.6. Other Operators and the Evolution Process
14.2.7. Analysis
14.3. Particle Swarm Optimization
14.3.1 Modelling
14.3.2 Example
14.3.3 Analysis
14.4. Topologies
14.5. Differential Evolution
14.5.1 Mutation
14.5.2 Recombination
14.5.3 Algorithm
14.5.4 Example
14.5.5 Self-Adaptive Differential Evolution
14.5.6 Evolutionary Ensembles
14.6 Local Search
14.6.1 Hill Climbing
14.6.2 Simulated Annealing
14.7. Memetic Computing
Questions
15. Evolutionary Robot Motion Planning
15.1 Introduction
15.2. Diversity Preservation
15.2.1. Fitness Sharing
15.2.2. Crowding
15.2.3. Other techniques
15.3. Multi-Objective Optimization
15.3.1. Pareto Front
15.3.2. Goodness of a Pareto Front
15.3.3. NSGA
15.3.4. MOEA/D
15.4. Path Planning using a Fixed Size Individual
15.5. Path planning using a Variable Sized Individual
15.5.1 Fitness Function
15.5.2 Multi-Resolution Fitness Evaluation
15.5.3 Diversity Preservation
15.5.4 Incremental Evolution
15.5.5 Genetic Operators and Evolution
15.6 Evolutionary Motion Planning Variants
15.6.1 Evolving Smooth Trajectories
15.6.2 Adaptive Trajectories for Dynamic Environments
15.6.3 Multi-Objective Optimization
15.6.4 Optimization in Control Spaces
15.7 Simulation Results
Questions
16. Hybrid Planning Techniques
16.1 Introduction
16.2 Fusion of Deliberative and Reactive Algorithms
16.2.1 Deliberative Planning
16.2.2 Reactive Planning
16.2.3 The need for fusion and hybridization
16.3. Fusion of Deliberative and Reactive Planning
16.4 Behaviours
16.5. Fusion of Multiple Behaviours
16.5.1 Horizontal Decomposition
16.5.2 Vertical Decomposition
16.5.3 Subsumption Architecture
16.6. Behavioural Finite State Machines
16.7. Fusion of Cell Decomposition and Fuzzy Logic
16.8. Fusion with Deadlock Avoidance
16.8.1 Deadlock Avoidance
16.8.2 Modelling Behavioural Finite State Machine
16.8.3 Results
16.9. Bi-level Genetic Algorithm
16.9.1 Coarser Genetic Algorithm
16.9.2 Finer Genetic Algorithm
16.9.3 Dynamic Obstacle avoidance Strategy
16.9.4 Overall Algorithm and Results
Questions
17. Multi-Robot Motion Planning
17.1. Multi-Robot Systems
17.1.1 Coordination
17.1.2 Centralized and Decentralized Systems
17.1.3 Applications
17.2. Planning in Multi-Robot Systems
17.2.1 Problem Definition
17.2.2 Metrics
17.2.3 Coordination
17.2.4 Importance of Speeds
17.3. Centralized Motion Planning
17.3.1. Centralized Configuration Space
17.3.2. Centralized search-based planning
17.3.3. Centralized Probabilistic Roadmap based planning
17.3.4. Centralized optimization-based planning
17.4. Decentralized Motion Planning
17.4.1 Reactive Multi-Robot Motion Planning
17.4.2 Congestion Avoidance in Decentralized Planning
17.4.3 Prioritization
17.5. Path Velocity Decomposition
17.6 Repelling Robot Trajectories
17.7. Co-evolutionary Approaches
17.7.1. Motivation
17.7.2. Algorithm
17.7.3. Master-slave cooperative evolution
17.7.4. Analysis of co-evolutionary algorithm
17.7.5. Motion Planning using co-evolution
Questions
18. Task Planning Approaches
18.1. Task Planning in Robotics
18.2. Representations
18.2.1 Representing States
18.2.2 Representing Actions
18.3. Backward Search
18.3.1 Backward Search instead of Forward Search
18.3.2 Heuristics
18.4. GRAPHPLAN
18.4.1 Planning Graphs
18.4.2 Mutexes
18.4.3 Planning Graphs as a heuristic function
18.4.4 GRAPHPLAN Algorithm
18.5. Constraint Satisfaction
18.5.1 Constraint Satisfaction Problems
18.5.2 Modelling Planning as a CSP
18.5.3 Modelling Constraints
18.5.4 Getting a solution
18.6. Partial Order Planning
18.6.1 Concept
18.6.2 Working of the algorithm
18.6.3 Threats
18.7. Integration of Task and Geometric Planning
18.8. Temporal Logic
18.8.1. Model Verification
18.8.2. Model Verification in Robot Mission Planning
18.8.3. Linear Temporal Logic
18.8.4. Computational Tree Logic
18.8.5. Other specification formats
18.9. Evolutionary Mission Planning
18.9.1 Mission Planning with Boolean Specifications
18.9.2 Mission Planning with Sequencing and Boolean Specifications
18.9.3 Mission Planning with Generic Temporal Specifications
Questions
19. Motion Planning in Uncertainties and Reinforcement Learning
19.1. Introduction
19.2. Adversarial Search
19.2.1 Game Trees
19.2.2 Example
19.2.3 Pruning
19.2.4 Stochastic Games
19.3. Planning in uncertainty
19.3.1. Problem modelling
19.3.2. Utility and Policy
19.3.3. Discounting
19.3.4. Value Iteration
19.3.5. Policy Iteration
19.4. Reinforcement Learning
19.4.1 Passive Reinforcement Learning
19.4.2 Q-Learning
19.5. Deep Reinforcement Learning
19.5.1 Deep Q-Learning
19.5.2 Policy Gradients
19.6 Multi-Agent Reinforcement Learning
19.7 Inverse Reinforcement Learning
19.8 Reinforcement Learning for Motion Planning
19.8.1 Motion Planning using Reinforcement Learning
19.8.2 Speeding up learning using imitation learning
19.8.3 Getting a reward function using Inverse Reinforcement Learning
19.8.4 Learning group behaviours
19.8.5 Simulation to Real
19.9. Partially Observable Markov Decision Process
Questions
20. Swarm and Evolutionary Robotics
20.1. Swarm Robotics
20.1.1. Characteristics of Swarm Robotics
20.1.2. Hardware Perspectives
20.2. Swarm Robotics Problems
20.2.1. Aggregation
20.2.2. Dispersion
20.2.3. Chaining
20.2.4. Collective Movement
20.2.5. Olfaction
20.2.6. Shape Formation
20.2.7. Robot Sorting
20.2.8. Seeking Goal of a Robot
20.3. Neuro-evolution
20.3.1. Evolution of a fixed architecture neural network
20.3.2. Evolution of a variable architecture neural network
20.3.3. Co-operative evolution of neural networks
20.3.4. Multi-objective Neuro-Evolution
20.4. Evolutionary Robotics
20.4.1 Fitness Evaluation
20.4.2 Speeding up evolution and adapting for Simulation to Real
20.4.3. Evolution of Multiple Robots and Swarms
20.4.4. Evolution of the Goal Seeking Behaviour
20.5. Simulations with ARGOS
Questions
21. Simulation Systems and Case Studies
21.1. Introduction
21.2. General Simulation Framework
21.2.1 Graphics and Dynamics
21.2.2 Modules and Services
21.2.3 Planning and Programming
21.3. Robot Operating System (ROS)
21.3.1 Understanding Topics
21.3.2 Services and Commands
21.3.3 Navigation
21.3.4 Example with a single robot
21.3.5 Example with multiple robots
21.3.6 Writing Planners using OMPL and MoveIt
21.4. Simulation Software
21.4.1 Motion Planning Libraries
21.4.2 Crowd Simulation with Menge
21.4.3 Vehicle Simulation with Carla
21.4.4. Simulation using VREP
21.4.5. Simulation using Webots
21.4.6. Other Simulators
21.5. Traffic Simulation
21.5.1 Kinematic Wave Theory
21.5.2 Fundamental Diagrams
21.5.3 Kinematic Waves
21.5.4 Intelligent Driver Model
21.5.5 Other Behaviours and Simulation Units
21.5.6 Simulation using SUMO
21.6. Planning Humanoids
21.6.1 Footstep Planning
21.6.2 Whole-Body Motion Planning
21.6.3 Planning with Manifolds
21.7 Case Studies
21.7.1 Pioneer LX as a service robot
21.7.2 Chaining of Amigobot Robots
21.7.3 Pick and Place using the Baxter robot
21.7.4 Playing with the NaO Robots
Questions
- Edition: 1
- Published: September 1, 2023
- No. of pages (Paperback): 1088
- Imprint: Academic Press
- Language: English
- Paperback ISBN: 9780443189081
- eBook ISBN: 9780443189098
RK
Rahul Kala
Rahul Kala is an assistant professor at the Centre of Intelligent Robotics, Indian Institute of Information Technology, Allahabad, India, where he received his B.Tech. and M.Tech. degrees in information technology. He received his Ph.D. degree in cybernetics from the University of Reading, UK in 2013. Dr. Kala has authored four books, 100 scientific papers, and is an active reviewer of leading journals of the domain. He has received numerous scholarships and grants from the Government of India, and is a recipient of the Best PhD Dissertation award from the IEEE Intelligent Transportation Systems Society.
Affiliations and expertise
Assistant Professor, Robotics and Artificial Intelligence Laboratory, Indian Institute of Information Technology, Allahabad, IndiaRead Autonomous Mobile Robots on ScienceDirect