基本概念

构型(Configuration)：构型是机器人上所有点的完整描述。它提供了机器人在特定时刻状态的简洁表示。
构型空间(Configuration Space)：也称为C-Space，指的是机器人可以到达的所有可能构型的集合。它考虑了空间限制范围和机器人的物理约束。
构型空间的维数是与机器人的自由度(degree of freedom)相同的。
以下展示了部分场景下的configuration space。

motion planning in configuration space

visiblity graph

连接所有端点（起点、终点、障碍多边形端点）以及部分边界点形成的图。
随后就可以用Dijkstra’s Algorithm，找连接
缺点是距离障碍物太近了

Trapezoidal Decomposition

区域分割后，形成三角形、四边形、梯形等凸的多边形，随后在每个区域内找点规划。

Collision Detection and Freespace Sampling Methods

给出一个碰撞检测函数，检测障碍物上是否存在一个分割线或者超平面使得机器人能够和障碍物分隔开。