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

Generating graphs

Visibility graphs

Visibility graph generates nodes from points on obstacles, current position and goal. generate graph.

Use A* to solve

That algorithm is called VGRAPH

Robots with volume

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.

Rotation of robots

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

Voronoi path planning

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.

Probabilistic Roadmap Planner

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


Potential fields

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