COMP4620/8620: Advanced Topics in ML – Intelligent Robotics
Please read the following notes ?rst before starting to work on the assignment.
1. This is an individual assignment.
2. The maximum total mark for this assignment is 100 points
3. This assignment consists of two parts: Part A and Part B. Part A contains conceptual questions only. The maximum total mark for Part A is 30 points. Part B contains conceptual questions, programming and analysis. The maximum total mark for Part B is 70 points.
4. Submission Instruction:
(a) You can write your program in a programming language of your choice.
(b) You must submit all of your source codes. If your program consists of multiple ?les, you must place all ?les under a single folder, compress the folder into a single ?le with one of the following extensions: .zip or .7z or .tar.gz, and submit this compressed ?le. If your program consists of multiple ?les in multiple folders, your compressed ?le should preserve the folder structure.
(c) In your selection of programming language and in compressing the ?les, you must con- sider that during the demo, you will need to download your submission, extract your source codes, compile (if needed), and run the program in front of the tutor marking your assignment without making any changes to the source code.
(d) All non-programming parts of the assignment must be written in a single .pdf ?le.
(e) The two ?les (source codes and .pdf) must be submitted via wattle before the due date.
(f) Late submission is NOT permitted. However, we provide a 5 hours grace period. Within the grace period, you can still submit your assignment. However, after the grace period ends, you will NOT be able to submit your assignment.
5. Information about the in-person demo will be announced in the class forum.
PART A
The questions in this part aim to explore the relation between distance in the C-space and in the workspace.
To achieve the above objective, consider a planar kinematic chain robot as illustrated in Figure 1. It has a static base, K ro- tational joints and K links. Each joint is represented as a point. Each link is a straight line segment with length L. It has two end-points, called the origin and the extremity points. The po- sition of the origin of the ?rst link is ?xed. The origin of the ith link for i ∈ [2; K] coincides with the extremity of the (i-1)th link at a joint point. The robot operates in a 2D workspace populated by a set of obstacles Obs.
Figure 1: An illustration of the planar kinematic chain robot.
A con?guration of the above robot can be represented by q = (θ1 ; θ2 ; · · · ; θK ), where θi ∈ [0; 2π) is the joint angle that de?nes the angle (in radian) between the base and the ?rst link for i = 1,and between the ith and (i ? 1)th link for i = [2; K]. The C-space of this robot can be represented as the space RK .
In addition, let us de?ne the C-space distance between two con?gurations, q = (θ1 ; θ2 ; · · · ; θK ) and q/ = (θ1(/); θ2(/) ; · · · ; θK(/)), as: dC (q; q/) = max1≤i≤K jθi ? θi(/)j. This distance metric is often used in motion planning because it is faster to compute, compared to the typical Euclidean distance. Please answer the following questions.
1. [20 pts] Given 2 con?gurations, q = (θ1 ; θ2 ; · · · ; θK ) and q/ = (θ1(/); θ2(/) ; · · · ; θK(/)), let us assume
the robot moves from q to q/ along a straight line segment qq/ in the C-space. It is known that during such a movement, all points on the robot traces a path of length less than or equal to α · dC (q; q/), where α is a constant that can be upper bounded in terms of the link length L and the number of links K. Please ?nd this upper bound of α and expressed them in L and K. Please provide its derivation. Hints are available in the last page.
2. [10 pts] Now, recall that the workspace distance dW (q; Obs) between the con?guration q and obstacles Obs in the workspace is de?ned as the distance between the closest pair of points on the robot placed at con?guration q and Obs. Please ?nd the radius τ of the neighbourhood Neigh(q) = {q/ j dC (q; q/) ≤ τ} that will guarantee the robot can move from con?guration q to q/ (for any q/ ∈ Neigh(q)) collision-free, following a straight line path qq/. Please express τ in terms of the upper bound α from A.1. and dW (q; Obs).
PART B
The questions in this part aim to provide hands-on experience and better understanding of Sampling- based Motion Planning. To this end, let’s consider K rigid-body sphere robots are navigating a 3D workspace [?50; 50] × [?50; 50] × [?50; 50] ? R3 populated by obstacles in the shape of cubes. And suppose each robot can only translate. Please answer the questions below.
1. [5 pts] Please specify the C-space of the K robots. Assume that the origin of the coordinate system of each robot is at the center of the sphere.
2. [35 pts] Please write a sampling-based motion planning program for centralised planning of the robots. A collision-free path here means the robot will not collide with the obstacles and other robots. Please implement either PRM with any one or more sampling strategies discussed in class, EST, or RRT. You can use and extend the collision check methods discussed in the past two weeks tutorials. Note that an edge in a graph/tree in Sampling-based Motion Planning represents a straight line-segment in the C-space, which in this case represents K (sub-)paths for K robots. We assume all robots move in such a way that they spend the exact same duration and use constant velocity to traverse theirrespective (sub-)paths, though the velocity used by diferent robots may difer.