Autonomous Mobile Robots: Planning, Navigation and Simulation

Cover
Autonomous Mobile Robots
Copyright
Acknowledgements
Preface
An introduction to robotics
Introduction
Application areas
Hardware perspectives
Actuators
Vision sensors
Proximity and other sensors
Kinematics
Transformations
TF tree
Manipulators
Mobile robots
Computer vision
Calibration
Pre-processing
Segmentation and detection
Machine learning
Recognition
Pose and depth estimation
Point clouds and depth images
Tracking
Human-robot interface
Questions
References
Localization and mapping
Introduction
AI primer
Localization primer
Localization using motion models
Localization using observation models: Camera
Localization using observation models: Lidar
Mapping primer
Planning
Control
Tracking
Kalman Filters
Extended Kalman Filters
Particle Filters
Localization
Motion model
Motion model for encoders
Measurement model using landmarks and camera
Measurement model using landmarks and Lidar
Measurement model for dense maps
Examples
Mapping
Occupancy maps
Geometric, semantic, and feature maps
Simultaneous Localization and Mapping
Questions
References
Visual SLAM, planning, and control
Introduction
Visual simultaneous localization and mapping
Visual odometry
Bundle adjustment
Loop closure and loop closure detection
Loop closure correction
Configuration space and problem formulation
Planning objectives
Assessment
Complexity
Completeness, optimality, and soundness
Terminologies
Control
PID controller
Mobile robot control
Other control laws
Bug algorithms
Bug 0 algorithm
Bug 1 algorithm
Bug 2 algorithm
Tangent Bug
Practical implementations
Questions
References
Intelligent graph search basics
Introduction
An overview of graphs
Breadth-first search
General graph search working
Algorithm working
Example
State space approach
Uniform cost search
Algorithm
Example
Linear memory complexity searches
A* algorithm
Heuristics
Algorithm
Example
Admissibility and consistency
Heuristic function design
Suboptimal variants
Adversarial search
Game trees
Example
Pruning
Stochastic games
Questions
References
Graph search-based motion planning
Introduction
Motion planning using A* algorithm
Vertices
Edges
Post-processing and smoothing techniques
Planning with robots kinematics
Planning in dynamic environments with the D* algorithm
Using a backward search
Raised and lowered waves
D* algorithm principle
D* algorithm
D* algorithm example
Lifelong planning A*
D* lite
Other variants
Anytime A*
Theta*
Learning heuristics
Learning real-time A*
ALT heuristics
Questions
References
Configuration space and collision checking
Introduction
Configuration and configuration space
Collision detection and proximity query primer
Collision checking with spheres
Collision checking with polygons for a point robot
Collision checking between polygons
Intersection checks with the GJK algorithm
Types of maps
Space partitioning
k-d tree
Oct-trees
Collision checking with oct-trees
Bounding volume hierarchy
Continuous collision detection
Representations
Point and spherical robots
Representation of orientation
Mobile robots
Manipulators
Composite robots and multirobot systems
State spaces
Questions
References
Roadmap and cell decomposition-based motion planning
Introduction
Roadmaps
Visibility graphs
Concepts
Construction
Completeness and optimality
Voronoi
Deformation retracts
Generalized Voronoi diagram
Construction of GVD: Polygon maps
Construction of GVD: Grid maps
Construction of GVD: By a sensor-based robot
Generalized Voronoi graph
Cell decomposition
Single-resolution cell decomposition
Multiresolution decomposition
Quadtree approach
Trapezoids
Construction
Complete coverage
Occupancy grid maps
Other decompositions
Navigation mesh
Homotopy and homology
Questions
References
Probabilistic roadmap
Introduction to sampling-based motion planning
Probabilistic roadmaps
Vertices and edges
Local planner
The algorithm
Completeness and optimality
Sampling techniques
Uniform sampling
Obstacle-based sampling
Gaussian sampling
Bridge test sampling
Maximum clearance sampling
Medial axis sampling
Grid sampling
Toggle PRM
Hybrid sampling
Edge connection strategies
Connecting connected components
Disjoint forest
Expanding roadmap
Generating cycle-free roadmaps
Visibility PRM
Complexity revisited
Lazy PRM
Questions
References
Rapidly-exploring random trees
Introduction
The algorithm
RRT
Goal biased RRT
Parameters and optimality
RRT variants
Bi-directional RRT
RRT-connect
RRT*
Lazy RRT
Anytime RRT
Kinodynamic planning using RRT
Expansive search trees
Kinematic planning by interior-exterior cell exploration (KPIECE)
Sampling-based roadmap of trees
Parallel implementations of RRT
Multi-tree approaches
Local trees
Rapidly-exploring random graphs
CForest
Distance functions
Topological aspects of configuration spaces
Questions
References
Artificial potential field
Introduction
Artificial potential field
Attractive potential modelling
Repulsive potential modelling
Artificial potential field algorithm
Working of artificial potential field in different settings
Artificial potential field with a proximity sensing robot
Artificial potential field with known maps
Problems with potential fields
Navigation functions
Social potential field
Force modelling
Groups
Other modelling techniques
Elastic strip
Environment modelling
Elastic strip
Modelling
Discussions
Adaptive roadmap
Questions
References
Geometric and fuzzy logic-based motion planning
Introduction
Velocity obstacle method
An intuitive example
Velocity obstacles
Reachable velocities
Deciding immediate velocity
Global search
Variants
Vector field histogram
Modelling
Histogram construction
Candidate selection
VFH+
VFH*
Other geometric approaches
Largest gap
Largest distance with nongeometric obstacles
Fuzzy logic
Classic logical rule-based systems
Fuzzy sets
Fuzzy operators
Aggregation
Defuzzification
Designing a fuzzy inference system
Training
Gradient-based optimization
Direct rule estimation
Questions
References
An introduction to machine learning and deep learning
Introduction
Neural network architecture
Perceptron
XOR problem
Activation functions
Multi-layer perceptron
Universal approximator
Learning
Bias-variance dilemma
Back-propagation algorithm
Momentum
Convergence and stopping criterion
Normalization
Batches
Cross-validation
Limited connectivity and shared weight neural networks
Recurrent neural networks
Deep learning
Auto-encoders
Deep convolution neural networks
Convolution
Pooling and subsampling
Training
Long-short term memory networks
Problems with recurrent neural networks
Long-short term memory networks
Adaptive neuro-fuzzy inference system
Questions
References
Learning from demonstrations for robotics
Introduction
Incorporating machine learning in SLAM
Visual place recognition
Sequential and deep learning-based place recognition
Handling multiple domains
Benefiting from semantics
Dealing with dynamic objects
Localization as a machine learning problem
Dealing with a lack of data
Data set creation for supervised learning
Some other concepts and architectures
Robot motion planning with embedded neurons
Robot motion planning using behaviour cloning
Goal seeking using raw sensor inputs
Driving with high level commands
Goal seeking avoiding dynamic obstacles
Generation of data
Augmenting rare data
Dealing with drift
Limitations
Questions
References
Motion planning using reinforcement learning
Introduction
Planning in uncertainty
Problem modelling
Utility and policy
Discounting
Value iteration
Policy iteration
Reinforcement learning
Passive reinforcement learning
Q-learning
Deep reinforcement learning
Deep Q-learning
Policy gradients
Deterministic policy gradients
Soft actor critic
Pretraining using imitation learning from demonstrations
Inverse Reinforcement Learning
Inverse Reinforcement Learning for finite spaces with a known policy
Apprenticeship learning
Maximum entropy feature expectation matching
Generative adversarial neural networks
Generative Adversarial Imitation Learning
Reinforcement learning for motion planning
Navigation of a robot using raw lidar sensor readings
Navigation of a robot amidst moving people in a group
Partially observable Markov decision process
Questions
References
An introduction to evolutionary computation
Introduction
Genetic algorithms
An introduction to genetic algorithms
Real-coded genetic algorithms
Selection
Crossover
Mutation
Other operators and the evolution process
Analysis
Particle swarm optimization
Modelling
Example
Analysis
Topologies
Differential evolution
Mutation
Recombination
Algorithm
Example
Self-adaptive differential evolution
Evolutionary ensembles
Local search
Hill climbing
Simulated annealing
Memetic computing
Questions
References
Evolutionary robot motion planning
Introduction
Diversity preservation
Fitness sharing
Crowding
Other techniques
Multiobjective optimization
Pareto front
Goodness of a Pareto front
NSGA
MOEA/D
Path planning using a fixed size individual
Path planning using a variable sized individual
Fitness function
Multiresolution fitness evaluation
Diversity preservation
Incremental evolution
Genetic operators and evolution
Evolutionary motion planning variants
Evolving smooth trajectories
Adaptive trajectories for dynamic environments
Multiobjective optimization
Optimization in control spaces
Simulation results
Questions
References
Hybrid planning techniques
Introduction
Fusion of deliberative and reactive algorithms
Deliberative planning
Reactive planning
The need for fusion and hybridization
Fusion of deliberative and reactive planning
Behaviours
Fusion of multiple behaviours
Horizontal decomposition
Vertical decomposition
Subsumption architecture
Behavioural finite state machines
Behaviour Trees
Fusion of cell decomposition and fuzzy logic
Fusion with deadlock avoidance
Deadlock avoidance
Modelling behavioural finite state machine
Results
Bi-level genetic algorithm
Coarser genetic algorithm
Finer genetic algorithm
Dynamic obstacle avoidance strategy
Overall algorithm and results
Questions
References
Multi-robot motion planning
Multi-robot systems
Coordination
Centralized and decentralized systems
Applications
Planning in multi-robot systems
Problem definition
Metrics
Coordination
Importance of speeds
Centralized motion planning
Centralized configuration space
Centralized search-based planning
Centralized probabilistic roadmap based planning
Centralized optimization-based planning
Decentralized motion planning
Reactive multi-robot motion planning
Congestion avoidance in decentralized planning
Prioritization
Path velocity decomposition
Repelling robot trajectories
Co-evolutionary approaches
Motivation
Algorithm
Master-slave cooperative evolution
Analysis of co-evolutionary algorithm
Motion planning using co-evolution
Questions
References
Task planning approaches
Task planning in robotics
Representations
Representing states
Representing actions
Backward search
Backward search instead of forward search
Heuristics
GRAPHPLAN
Planning graphs
Mutexes
Planning graphs as a heuristic function
GRAPHPLAN algorithm
Constraint satisfaction
Constraint satisfaction problems
Modelling planning as a CSP
Modelling constraints
Getting a solution
Partial order planning
Concept
Working of the algorithm
Threats
Integration of task and geometric planning
Temporal logic
Model verification
Model verification in robot mission planning
Linear temporal logic
Computational tree logic
Other specification formats
Questions
References
Swarm and evolutionary robotics
Swarm robotics
Characteristics of swarm robotics
Hardware perspectives
Swarm robotics problems
Aggregation
Dispersion
Chaining
Collective movement
Olfaction
Shape formation
Robot sorting
Seeking goal of a robot
Neuro-evolution
Evolution of a fixed architecture neural network
Evolution of a variable architecture neural network
Co-operative evolution of neural networks
Multiobjective neuro-evolution
Evolutionary robotics
Fitness evaluation
Speeding up evolution
Evolution of multiple robots and swarms
Evolution of the goal-seeking behaviour
Simulations with ARGOS
Evolutionary mission planning
Mission planning with Boolean specifications
Mission planning with sequencing and Boolean specifications
Mission planning with generic temporal specifications
Questions
References
Simulation systems and case studies
Introduction
General simulation framework
Graphics and dynamics
Modules and services
Planning and programming
Robot Operating System
Understanding topics
Services and commands
Navigation
Example
Simulation software
Motion planning libraries
Crowd simulation with Menge
Vehicle simulation with Carla
Other simulators
Traffic simulation
Kinematic wave theory
Fundamental diagrams
Kinematic waves
Intelligent Driver Model
Other behaviours and simulation units
Planning humanoids
Footstep planning
Whole-body motion planning
Planning with manifolds
Case studies
Pioneer LX as a service robot
Pioneer LX as a tourist guide
Chaining of Amigobot robots
Pick and place using the Baxter robot
Dancing NaO robots
Questions
References
Index