Description
Consider a mobile robot operating in a 2D world. The robot is modeled as a rigid body
with a circular base of radius r. The robot can move in two ways:
• Translation T(d): The robot can move along the direction specified by its current
orientation, where d ∈ R is the distance parameter. A positive distance d > 0
indicates forward movement, while a negative distance d < 0 indicates backward
movement.
• Rotation R(θ): The robot can rotate in place by an angle θ around its center,
where θ ∈ R is the rotation parameter.
1. (10 points for COM S 4760, 7 points for COM S 5760) Configuration Space:
(a) Define the placement of the robot’s body frame and use it to derive a semialgebraic model of the robot.
(b) Suppose the robot starts with its center at position (xi
, yi) ∈ R
2
in the world
frame, with orientation θi ∈ [0, 2π), measured with respect to the world
frame. It then rotates counterclockwise by an angle θ using R(θ) and moves
forward along the resulting orientation by distance d using T(d). Determine
the region in the world occupied by the robot after this transformation.
(c) Suppose the robot starts with its center at position (xi
, yi) ∈ R
2
in the world
frame, with orientation θi ∈ [0, 2π), measured with respect to the world
frame. Now, suppose we want to move the robot so that its center is at
(xg, yg) ∈ R
2 with an orientation θg ∈ [0, 2π) relative to the world frame.
Describe a sequence of transformations T(d) and R(θ) that the robot can
perform to achieve this, determining the values for the parameters d and θ
in terms of xi
, yi
, θi
, xg, yg, θg for each translation and rotation. Note that
multiple translations and/or rotations may be required.
(d) Describe the configuration space C of the robot and identify the mathematical
structure (group) associated with C. Describe how each configuration is represented, i.e., identify the key parameters that uniquely define a configuration
of the robot.
2. (10 points for COM S 4760, 7 points for COM S 5760) C-Space Obstacles:
The workspace, where the robot operates, is a rectangular area defined by the set
[0, Xmax] × [0, Ymax], with the bottom-left corner at (0, 0) and the top-right corner
at (Xmax, Ymax). The world contains a set O of circular obstacles, each defined by
a tuple o = (xo, yo, ro) ∈ R
2 × R>0, where (xo, yo) is the position of the obstacle’s
center and ro is its radius.
(a) Describe the configuration space obstacle Cobs,o corresponding to each circular
obstacle o = (xo, yo, ro) by identifying a closed form expression for a function
f : C × R
2 × R>0 → R such that Cobs,o can be expressed as
Cobs,o = {q ∈ C | f(q, xo, yo, ro) ≤ 0}.
(b) Consider the area outside the workspace boundaries as an obstacle. Determine the complete configuration space obstacle Cobs, incorporating both the
workspace boundaries and the circular obstacles within the workspace.
3. (COM S 5760 only, 6 points) Discretized Workspace: Suppose Xmax and Ymax are
natural numbers, and the workspace is discretized into a finite number of grid
points, defined as
W = {(x, y) | x ∈ {0, 1, . . . , Xmax}, y ∈ {0, 1, . . . , Ymax}}.
The robot’s initial position and goal are always located at one of these grid points.
Furthermore, the robot can only move between these points, transitioning only
to directly neighboring points in the grid—either horizontally or vertically (but
not diagonally)–using a combination of translation T(d) and rotation R(θ), where
d, θ ∈ R.
For example, suppose the robot is located at (1, 1) with orientation 0 (i.e., its
heading aligns with the x-axis), it can move to (2, 1) or (1, 2), using the sequence
of transformations derived in Problem 1c.
For simplicity, when computing the configuration space C and the configuration
space obstacle Cobs, consider only the configurations of the robot when its center is
at a grid point.
Although the robot moves continuously between these points, we
will disregard its intermediate configurations and assume that collisions—whether
with the workspace boundaries or circular obstacles—can only occur when the
robot’s center is precisely at a grid point.
(a) Assume that the robot is considered to have reached the goal as soon as its
center is located at the goal grid point, regardless of its orientation. Given
the described setup, is it possible to formulate a discrete motion planning
problem for the robot? If so, describe the resulting state space X, the set
of actions U, the action space U(x) for each state x ∈ X, and the state
transition function f : X × U → X.
(b) Given the following parameters:
• Workspace dimensions: Xmax = 6 and Ymax = 5.
• Robot radius: r = 0.5.
• Set of circular obstacles: O = {o1, o2}, where
– o1 = (3.0, 1.5, 1.12) represents an obstacle centered at (3.0, 1.5) with
a radius of 1.12.
– o2 = (2.5, 3.0, 0.5) represents an obstacle centered at (2.5, 3.0) with
a radius of 0.5.
List all the grid points in the workspace that the robot can safely occupy without causing a collision with either the workspace boundaries or
circular obstacles.
(c) Consider the same setup as in part (b). The robot’s initial position is (1, 1)
with an orientation of π
(i.e., 45 degree relative to the x-axis).
Write a script main.py to compute a sequence of grid points for the robot
to reach the goal located at (5, 3). You should be able to run the script with
the following command:
python main.py
This should print out the sequence of grid points visited by the robot, starting
at (1, 1) and ending at (5, 3).