COMP4620/8620: Advanced Topics in ML – Intelligent Robotics
Semester-22024–Assignment1
Duedate: Monday,26August202410.00amCanberratime
Graceperiod: 5hoursaftertheduedate
Latesubmission: Notpermitted
Pleasereadthefollowingnotesfirstbeforestartingtoworkontheassignment.
1. Thisisanindividualassignment.
2. Themaximumtotalmarkforthisassignmentis100points
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,
programmingandanalysis. ThemaximumtotalmarkforPartBis70points.
4. SubmissionInstruction:
(a) Youcanwriteyourprograminaprogramminglanguageofyourchoice.
(b) You must submit all of your source codes. If your program consists of multiple files,
you must place all files under a single folder, compress the folder into a single file with
one of the following extensions: .zip or .7z or .tar.gz, and submit this compressed file. If
your program consists of multiple files in multiple folders, your compressed file should
preservethefolderstructure.
(c) In your selection of programming language and in compressing the files, 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
assignmentwithoutmakinganychangestothesourcecode.
(d) Allnon-programmingpartsoftheassignmentmustbewritteninasingle.pdffile.
(e) Thetwofiles(sourcecodesand.pdf)mustbesubmittedviawattlebeforetheduedate.
(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,youwillNOTbeabletosubmityourassignment.
5. Informationaboutthein-persondemowillbeannouncedintheclassforum.
PARTA
The questions in this part aim to explore the relation between
distanceintheC-spaceandintheworkspace.
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 first link is fixed. The origin of the ith
linkfori ∈ [2,K]coincideswiththeextremityofthe(i?1)thlink Figure1: Anillustrationoftheplanar
atajointpoint. Therobotoperatesina2Dworkspacepopulated kinematicchainrobot.
byasetofobstaclesObs.
Page1of3–AdvancedTopicsinML:IntelligentRobotics–COMP4680/8650
Aconfigurationoftheaboverobotcanberepresentedbyq = (θ ,θ ,··· ,θ ),whereθ ∈ [0,2π)isthe
1 2 K i
jointanglethatdefinestheangle(inradian)betweenthebaseandthefirstlinkfori = 1,andbetween
theith and(i?1)th linkfori = [2,K]. TheC-spaceofthisrobotcanberepresentedasthespaceRK.
In addition, let us define the C-space distance between two configurations, q = (θ ,θ ,··· ,θ ) and
1 2 K
q(cid:48) = (θ(cid:48),θ(cid:48),··· ,θ(cid:48) ), as: d (q,q(cid:48)) = max |θ ? θ(cid:48)|. This distance metric is often used in motion
1 2 K C 1≤i≤K i i
planningbecauseitisfastertocompute,comparedtothetypicalEuclideandistance.
Pleaseanswerthefollowingquestions.
1. [20 pts] Given 2 configurations, q = (θ ,θ ,··· ,θ ) and q(cid:48) = (θ(cid:48),θ(cid:48),··· ,θ(cid:48) ), let us assume
1 2 K 1 2 K
the robot moves from q to q(cid:48) along a straight line segment qq(cid:48) 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
α·d (q,q(cid:48)), where α is a constant that can be upper bounded in terms of the link length L and
C
thenumberoflinksK. PleasefindthisupperboundofαandexpressedtheminLandK. Please
provideitsderivation. Hintsareavailableinthelastpage.
2. [10 pts] Now, recall that the workspace distance d (q,Obs) between the configuration q and
W
obstacles Obs in the workspace is defined as the distance between the closest pair of points
on the robot placed at configuration q and Obs. Please find the radius τ of the neighbourhood
Neigh(q) = {q(cid:48) | d (q,q(cid:48)) ≤ τ} that will guarantee the robot can move from configuration q to
C
q(cid:48) (for any q(cid:48) ∈ Neigh(q)) collision-free, following a straight line path qq(cid:48). Please express τ in
termsoftheupperboundαfromA.1. andd (q,Obs).
W
PARTB
The questionsin this part aimto provide hands-onexperience and better understandingof 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 populatedbyobstaclesintheshapeofcubes. And
supposeeachrobotcanonlytranslate. Pleaseanswerthequestionsbelow.
1. [5 pts] Please specify the C-space of the K robots. Assume that the origin of the coordinate
systemofeachrobotisatthecenterofthesphere.
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
otherrobots. PleaseimplementeitherPRMwithanyoneormoresamplingstrategiesdiscussed
in class, EST, or RRT. You can use and extend the collision check methods discussed in the
pasttwoweekstutorials. Notethatanedgeinagraph/treeinSampling-basedMotionPlanning
represents a straight line-segment in the C-space, which in this case represents K (sub-)paths
for K robots. Weassumeallrobotsmoveinsuchawaythattheyspendtheexactsameduration
and use constant velocity to traverse their respective (sub-)paths, though the velocity used by
differentrobotsmaydiffer.
Theinputtoyourprogrammustbeatext(.txt)fileandfollowstheformatbelow.
(a) The file consists of K +|Obs|+2 lines, where K is the number of robots and |Obs| is the
numberofobstaclesintheenvironment.
(b) Thefirstlinecontainstwonumbersseparatedbyasinglewhitespace. Thefirstnumberin
thislineisthenumberofrobots,whilstthesecondnumberisthenumberofobstacles.
(c) The second line consists of K numbers, each separated by a white space. The ith number
inthislineistheradiusofrobot-i.
Page2of3–AdvancedTopicsinML:IntelligentRobotics–COMP4680/8650
(d) Each of line-3 to line K +2 contains 6 numbers, which specifies the initial and goal con-
figurationsoftheith robot,wherei = lineNumber?2. Theformatofeachlineis:
InitialConf X InitialConf Y InitialConf Z ; GoalConf X GoalConf Y GoalConf Z
(e) Each of line K +3 to line K +|Obs|+2 contains 4 numbers separated by a white space,
which specifies the position of the center point and side length of the jth obstacle where
j = lineNumber?(K +2)Theformatofeachoftheselinesis:
CenterPt X CenterPt Y CenterPt Z SideLength
The output to your program must be a text (.txt) file that specifies the collision-free path (a
sequence of line segments) for the robots to move from the given initial to goal configurations.
Theformatoftheoutputfileisasfollows.
(a) Thefileconsistsofn+2lines,wherenisthenumberoflinesegmentsinyourpath
(b) Thefirstlineisthenumberofline-segments
(c) The second line consists of 3K numbers, specifying the initial configuration of each of
the K robots. Each configuration is separated by a semicolon, while each number in a
configurationisseparatedbyawhitespace. Specifically,theformatofline-2is:
ConfRobot-1 X ConfRobot-1 Y ConfRobot-1 Z ; ConfRobot-2 X ConfRobot-2 Y
ConfRobot-2 Z ; ··· ; ConfRobot-K X ConfRobot-K Y ConfRobot-K Z
(d) Thenextnlinesaretheendconfigurationofeachlinesegment. Eachoftheselinesconsists
of3K numbersandusestheformatasspecifiedforline-2oftheoutputfile(aboveitem)
During demonstration, we will test the correctness of your program. For this purpose, we will
providethreeproblemsandgiveyourprogramupto1minutetosolveeachproblem.
3. [12 pts] Please evaluate the required time that your program needs to solve queries (i.e., find
collision free paths) as the number of robots increases. For this purpose, please run your pro-
gram for K = {1,3,5,7} on the same environment of your design. For each value of K, you
should run for at least 10× to gather the average and 95%-confidence interval of the time to
solvequeries. Ifthetimetofindthesolutionistoolong,youcanputalimitontherun-timeand
recordthesuccessrateofsolvingquerieswithinthegiventime,inadditiontothetimetosolve
queries. Please explain your selection of the environment, compare the results for the different
K andexplainyourfindings.
4. [12 pts] Please evaluate the performance of your program as the problem becomes more com-
plex. To this end, please use K = 3 but alter the testing environment systematically, so as to
tease out the complexity of sampling-based motion planning (hint: the concept of (cid:15),α,β could
be useful in this design). For each environment, you should run for at least 10× to gather the
averageand95%-confidenceintervalofthetimetosolvequeries. Ifthetimetofindthesolution
is too long, you can put a limit on the run-time and record the success rate of solving queries
within the given time, in addition to the time to solve queries. Please explain your selection of
theenvironments,comparetheresultsforthedifferentenvironment,andexplainyourfindings.
5. [6pts]WhatdoyouthinkcanbedonetoimprovetheperformanceyougetinB.3andB.4?
oOo That’s all folks oOo
)1+2
K(K =
i1= Ki
(cid:80) ?
r·θsinaidar θelgnalartnecdna rsuidarhtiwelcricafocranA ?
.1.ArewsnaotsalumrofgniwollofehtdeenylekillliwuoY :tniH
Page3of3–AdvancedTopicsinML:IntelligentRobotics–COMP4680/8650
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
