Autonomous Mobile Robots

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