In-Depth Notes on Path Planning Fundamentals

Mobile robot path planning involves identifying a sequence of actions for a robot to reach a designated goal location. Key representations in this field include the state space, which represents all possible states of the robot and the world; actions, which are the movements or operations the robot can perform; initial and goal states, indicating the starting point and target destination; and the plan, which is a sequence of actions or states leading to the goal.

Fundamental questions in path planning revolve around the domain/application constraints, how a plan is computed and represented, what the plan achieves, and how the quality of a plan is evaluated. The applications of path planning are diverse and include route planning, logistics management, drone deployment, crop coverage, and NPC planning.

World representation is critical in path planning and involves understanding obstacles, which are areas that the robot must avoid; free space, which consists of unoccupied areas where the robot can navigate; and unknown areas, which are spaces with potential obstacles that are not yet identified. In planning, these unknown areas are typically treated as free space to simplify calculations.

Robot representation includes the degrees of freedom (DOF), indicating a robot's ability to move; higher DOF signifies more complexity and adaptability. Wheeled robots are described in terms of mobility (δm), steerability (δs), and maneuverability (δM), where δM is defined as δm + δs. The overall position specification of a robot, including all its joints and parts, constitutes its configuration, and for a differential drive robot, the configuration includes its pose specified by the coordinates (x, y, θ).

The configuration space represents all potential configurations for a robot within a given environment and aids in determining valid paths while avoiding collision by mapping obstacles. The goal of the path planning process is to find a collision-free route from an initial configuration (qinit) to a goal configuration (qgoal), using computational models to traverse through configuration spaces while accounting for obstacles in the environment.

Occupancy grids provide a grid-based representation of environments to facilitate path planning, allowing adjustments to the grid size for optimization while considering the robot's size and shape. Quadtree representation is a hierarchical method to manage space partitioning in path planning, subdividing cells based on obstacles to form an adaptive grid that efficiently tracks free and occupied spaces.

Roadmap algorithms pre-compute pathways (roadmaps) in the environment to reduce computational efforts in real-time, finding paths through these pre-determined roadmaps to navigate from start (qstart) to goal (qgoal) configurations. Visibility graphs concentrate on path planning by focusing on the shortest route that stays close to obstacles, thus enhancing safety but increasing computational complexity. Voronoi diagrams prioritize maximizing distance from obstacles to create safer paths, although this approach may lead to inefficiency and demands higher computational resource due to issues like high dimensionality computations and sensitivity to changes in obstacle positions.

Lastly, optimal search structures leverage traditional search methods, such as A*, for navigating graph structures formed by various planning techniques and employ heuristic evaluations to guide the search process effectively towards the goal.