Book chapter 8: Planning a route (graph search, sampling, optimization and learning) #203

Part of #165 (Phase 1).

Problem

The path_planning page of the book only lists the sections and the simulations. The book needs the explanation of finding a route from the start to the goal on a map. This is the largest chapter: one page per section, and the algorithms within a section are read in the order below.

Expected change

Write these sections:

• 8.1 Graph search on a grid: Dijkstra, then A*, then bidirectional A* (dijkstra_path_planning, astar_path_planning, astar_bidirectional_path_planning): cost-to-come, heuristics and admissibility
• 8.2 Search with the vehicle's motion: Hybrid A* (astar_hybrid_path_planning): continuous states and motion primitives from the model of Chapter 3
• 8.3 Replanning: D* (dstar_path_planning): reusing the previous search when the map changes
• 8.4 Sampling-based planning: PRM, RRT, RRT*, bidirectional RRT*, Informed RRT* (prm_path_planning, rrt_path_planning, rrt_star_path_planning, rrt_star_bidirectional_path_planning, informed_rrt_star_path_planning): probabilistic completeness and asymptotic optimality
• 8.5 Optimization and smoothing: gradient descent, elastic bands (gradient_path_planning, elastic_bands_path_planning)
• 8.6 Nature-inspired and learning-based planning: GA, PSO, ACO, Q-learning (ga_path_planning, pso_path_planning, aco_path_planning, q_learning_path_planning)

Inputs: #102 (the A* heuristic and its weight explained in the code, PR #139).

How to contribute

• Each section can be a separate pull request. Comment here with the section you want to write, so two people don't write the same one
• Follow the writing guide and use the symbols of Notation and Units. The Stanley chapter is an example
• Write the theory layer only: problem and intuition, theory, algorithm, limits and references, with figures drawn by figure scripts. The code layer (where the equations live in the code, experiments, exercises) waits for the code roadmap (Roadmap: toward a full navigation simulator for learning #131)
• Put each section on its own page in the chapter folder, and list it on the chapter page

Done when

Every section above is a page of doc/path_planning/, listed on the chapter page, and the book builds without warnings.