Notes - Artificial Intelligence MT24, Robots
Flashcards
What’s the difference between a manipulator and a mobile robot?
- Manipulators: Attached to their workplace
- Mobile robots: Can move about
What assumptions do we make when dealing with the problem of moving a robot to a desired location?
- Robot movement is deterministic and not subject to errors
- The environment is static and does not change while we think
Why is not a reasonable assumption that robots are not points in 2D or 3D space?
They may have an extent or an orientation.
@Define a configuration space (C-space) of a robot.
The feasible values of parameters describing a configuration of the robot.
Why will the configuration space for a robot on a 2D plane likely be 3D?
You also need to account for the orientation.
What is the difference between the configuration space and the workspace?
- Configuration space: Feasible values of robot parameters
- Workspace: Actual geometry of environment
@Define kinematic transformation.
Converting a point in the configuration space of a robot to the workspace coordinates.
@Define inverse kinematic transformation.
Determining the point in configuration space required for a robot to be at certain workspace coordinates.
@Define a nonholonomic robot and give an @example.
- A robot that has fewer controllable parameters than the total number of parameters
- Example: A simple model of a car has three parameters, $(x, y, \theta)$, but can only be controlled by velocity and steering direction.
@Define the idea of skeletonization in the context of robots and configuration spaces.
Precompute a roadmap/graph of the environment, such that staying along the roads means you won’t enter points not in the configuration space.
What’s the high-level idea behind visibility graphs in the context of skeletonization?
Compute a graph of vertices of configuration space obstacles, and link two nodes if it’s possible to travel between them without obstructions.
The high-level idea behind visibility graphs in the context of skeletonization is to compute a graph of vertices of configuration space obstacles, and link two nodes if it’s possible to travel between them without obstructions.

One algorithm for determining this graph is known as the sweep algorithm. Describe two @algorithms for this:
- One which runs in $O(N^3)$, and
- One that runs in $O(N^2 \log N)$
where $N$ is the number of vertices.

- Algorithm 1:
- Fix a point and sweep a 360 degree angle to link to every other vertex.
- Connect two vertices if there is no object in between.
- Do this for every point.
- This takes $O(N^3)$ since for each of the $N^2$ pairs of points, you need to check the $N$ edges (any polygon with $N$ vertices has $N$ edges).
- Algorithm 2:
- Fix a point and sweep a 360 degree angle to link to every other vertex.
- Sort the vertices by the angle that was required to hit that vertex. (If there’s a tie, order the closer nodes first)
- Sweep around again; and add an edge into the “active list” when we reach the first vertex of this edge
- Remove an edge when we reach the second vertex of that edge.
- Store the active list as a binary search tree, in “visibility order”. This can be maintained in $O(\log n)$ time since the this binary search tree will contain at most $n$ nodes.
- Only add a vertex to the visibility graph if it comes first in the visibility order.
- Sorting the vertices by the angle takes $O(n \log n)$ time, and sweeping around once more takes $O(n \cdot \log n)$ time.
- Since this needs to be done for each of the $n$ vertices, overall it takes $O(n^2 \log n)$ time.
Why are visibility graphs not typically used for path-planning?
This approach means that the robots are right up against the edge of configuration space, and so might “scrape corners”.
What’s the high level idea behind generalised Voronoi diagrams for skeletonization?
Compute a Voronoi diagram for the configuration space, and then travel along straight lines in the Voronoi diagram.
What are the four disadvantages of generalised Voronoi diagrams for skeletonization?
- GVDs are difficult to compute in high dimensions
- They might be inefficient and lead to longer paths
- Not very stable
- Localisation (finding out where you are in the environment) is hard if you stay away from surfaces
What’s the high level idea behind probabilistic roadmaps in the context of skeletonization?
Generate random points in configuration space and connect them with straight lines.
What’s the high level idea behind region decomposition in the context of skeletonization?
Divide the configuration space into small cells and connect adjacent regions.
Region decomposition is an approach to skeletonization which divides the configuration space into small cells and then connects adjacent regions. However, this can lead to completeness problems if the decomposition is not fine enough.
How can this be overcome?
Subdivide cells intersection with obstacles.
What’s the high level idea behind using potential fields in the context of finding paths through configuration space?
Pretend that the starting position and the obstacles have a negative charge and the goal has a positive charge.