Robot exists in some configuration space By cartesian coordinates, angles and lengths.
There are legal and illegal positions
Path planning is difficult
There are many degrees of freedom for complex robots
Higher dimension space makes solutions more difficult
Visibility graph generates nodes from points on obstacles, current position and goal. generate graph.
Use A* to solve
That algorithm is called VGRAPH
What if robot takes up space?
Expand each obstacle by size of robot
How to grow each obstacle? draw shape of robot around each obstacle. shape is relative to point, so the growth is asymmetric if you choose a point for the robot which is not in the middle. eg a vertex.
What about rotation? grow robot by shape of all rotations. but this is overly conservative. will miss paths
Can do vgraph for each rotation, and switch between rotations. can choose 2 or 3 rotations
Find paths as far as way from obstacles as possible
Divide plane in cells, with a cell around each obstacle
Within a cell, all points are closest to that obstacle
We move along the lines between cells
Overly conservative
Hard to compute in 3d
Small environmental changes can significantly change the graph.
Generate random configuration of robot in space.
Find n positions which are legal
Link them using k nearest neighbours
Risk: graph not fully connected.
If so, can add extra nodes between breaks
Attracted to goal, repelled from obstacle.
Goal has 0 potential energy
Can use gradient descent to get to goal
Problem of local minimums
If in a local minimum, can pertube by walking in a random direction to get out of it.
Can use laser, sonar, to detect obstacles and get potential