Assignment1-FIT5222Planningandautomatedreasoning

Assignment1:FlatlandChallenge

Inthisassignmentyourjobistoscheduleasetoftrainsthrougharailwaynetwork.

Youneedtocoordinateeverytrainfromitsstartingstationtoitsdestinationasquicklyas

possible.Astherecanbemanytrainsmovingatthesametimeyouneedtoguaranteethat

eachpathiscollision-free.

Theassignmenthasthreesections,inincreasingorderofdifficulty.Theamountofpoints

relativetoeachquestionisstatedinthequestionheading.Apassinggradeis50%.

BesuretowatchtheintroductoryvideoonMoodleandtoreadtheIntroductionto

Flatlanddocumentationwhichwehavepreparedforyou.Bothareavailablefrom

Moodle.

Youmustupdateyourflatlandcodeandinstallationbeforestartingtheassignment:

●Underflatlandfolder

●gitpull

●pythonsetup.pyinstall

●Now,runcommandpython-mpiplist,youshouldseeflatland-rlversionis

updatedto2.2.4

●(Hint,usepython3insteadofpythonifpython3pointstotherightoneonyour

machine)

Instructionstogetcodebase(inassignment1_2024branchofpigletrepo)for

assignmentisintheIntroductiontoFlatlanddocumentation.

Whenthecontestserverisready,youwillseeyourfscoreuponsubmission.

QUESTION1:Warmup(15points)

Youaregivenstartandtargetlocations,oneatatime.Yourjobistorouteeachtrain

independentlyfromalltherest.Inthisquestioncollisionsarenotpossibleandthereisno

timedimension.

Forthisquestion,youneedtoimplementasuccessorfunctionfortheFlatlanddomain.You

alsoneedtochooseanalgorithmtohelpyoufindpaths.Youarefreetouseanyofthe

techniqueswehavediscussedinthelectures,thatyouhavereadaboutintheliteratureor

canwriteyourownnewapproach.

Yoursolutionwillbeevaluatedon40evaluationinstances(onlystaffhavetheseinstances)

with2hourstimelimitandeachinstancehas1agent.Wewillcompareyoursumof

individualcost(SIC,foragentsdidnotarrivegoallocation,itscostwillbe

Assignment1-FIT5222Planningandautomatedreasoning

ofthemap)andsuccessratetoanoptimalsolution

푇

푚푎푥

=8*(푤푖푑푡ℎ+ℎ푒푖푔ℎ푡)

implementedbyteachingteamandcalculateyourscoreusingfollowingmethod:

푝

푠푐표푟푒

= ( 푐표푚푝푙푒푡푒푑_푎푔푒푛푡푠_푆퐼퐶+ 푇

푚푎푥

*푓푎푖푙푒푑_푎푔푒푛푡푠)/푡표푡푎푙_푎푔푒푛푡푠

푓

푠푐표푟푒

=푝

푠푡푎푓푓

/푝

푠푐표푟푒

whereisthepscoreofstaffimplementation.Generally,agoodsolutionhassmall

푝

푠푡푎푓푓

푝

scoreandlargescore.

푓

Yourfinalscorewillbe(sincethereare15pointsavailableforthisquestion).

푓

푠푐표푟푒

×15

QUESTION2:Easymode(25points)

Youaregivenstartandtargetlocations,oneatatime,aswellasasetofexistingpathsfor

trainsthatarealreadymoving.Yourjobistorouteeachtrainindividuallywhileavoiding

collisionswithalltherest.Youarefreetouseanyofthetechniqueswehavediscussedin

thelectures,thatyouhavereadaboutintheliteratureorcanwriteyourownnewapproach.

Forthisquestion,youneedtomodifyyoursuccessorfunctiontoaccountfortime.In

addition,theremightbethesituationthatthesearchalgorithmfailedtofindafeasible

solutionasdynamicobstaclesblockallpossiblepaths.Justreturnanemptylistinthiscase.

Furthermore,eachactionandeachlocationforeverycomputedplanneedtobe

collision-free.

Yoursolutionwillbestillevaluatedon56instanceswitha2hourstimelimitandyourscorein

thisquestionwillagainbecomputedasthesumofindividualpathcosts(SIC)andcompared

tothebestsolutionfromstudents(andstaff)!

YourwillbecomputedinthesamewayasforQuestion1.Buttherearesome

푓

푠푐표푟푒

differences:

●Herewecomputeforeachinstance.

푓

푠푐표푟푒

●Eachinstancecontainsmultipleagents.

●Yourfinalpointswillbe,whereisinstanceid.

푖

푛

∑푓

푠푐표푟푒

푖

÷56×25푖

Thereareupto25pointsavailableforthisquestion.

Assignment1-FIT5222Planningandautomatedreasoning

QUESTION3:Challenge(60points)

Youaregivensetsofstartandtargetlocationsatthesametime.Yourjobistorouteallthe

trainssimultaneouslyinawaythatiscollision-free.But,eachagenthasanexpected

arrivaltime,latearrivalwillresultinapenalty.

Youarefreetouseanyofthetechniqueswehavediscussedinthelectures,thatyouhave

readaboutintheliteratureorcanwriteyourownnewapproach.

Now,asallagentsareunderyourcontrol,youneedtomakeallagentsreachtheirgoal

locations.

Inthisquestionagentsmayrunintomalfunctionsduringexecution.Theevaluatorwillcall

thereplanfunctionwhenanewmalfunctionoccurs.Implementthereplanfunctionto

properlyhandlemalfunction.Refertothe“IntroductiontoFlatland”documentfordetails

aboutmalfunctionandreplanfunction.

Yoursolutionwillbestillevaluatedon56instanceswithdifferentdifficultylevelsin2hours

andyourscoreinthisquestionwillagainbecomputedasthesumofindividualpathcosts

(SIC)andcomparedtothebestsolutionfromstudents(andstaff)!

YourcomputationissimilartoQuestion1.Buttherearesomedifferences:

푓

푠푐표푟푒

●

푝

푠푐표푟푒

= ( 푐표푚푝푙푒푡푒푑_푎푔푒푛푡푠_푆퐼퐶+푝푒푛푎푙푡푦+ 푇

푚푎푥

*푓푎푖푙푒푑_푎푔푒푛푡푠)/푡표푡푎푙_푎푔푒푛푡푠

●Theis.

푝푒푛푎푙푡푦2* 푡표푡푎푙_푑푒푙푎푦푒푑_푡푖푚푒푠푡푒푝푠

●Eachinstancecontainsmultipleagents.

●Eachinstance’swillrefertoabaselineimplementationandanadvanced

푓

푠푐표푟푒

푝

푏푎푠푒

implementation(orbeststudentsolutionwhicheverisbetter):

푝

푎푑푣

푓

푠푐표푟푒

=푚푖푛(0.5 *

푝

푏푎푠푒

푝

푠푐표푟푒

, 0.5)+푚푎푥(0.5*

푝

푏푎푠푒

−푝

푠푐표푟푒

푝

푏푎푠푒

−푝

푎푑푣

,0)

●,whereisinstanceid.

푖

푛

∑푓

푠푐표푟푒

푖

÷56×60푖

Thereareupto60pointsavailableforthisquestion.

Report(50points)

Youneedtocreateareportthatdescribesyourapproachtoeachofthequestions.This

includesatextualdescriptionofyourapproaches,whyyouadoptedthatparticularapproach

andathoroughdiscussionalongwithanysupplementarymaterialrequired(suchaspseudo

code,images,graphs,tables...).

Assignment1-FIT5222Planningandautomatedreasoning

ReportMarkingRubric

CriteriaN

0%-49%

P

50%-59%

C

60%-69%

D

70%-79%

HD

80%-100%

Descriptionof

yourapproach

(35points)

Incompleteor

insufficient

descriptionof

theapproach

and/or

pseudo-code

High-level

descriptionof

theapproach

and

pseudo-code

+Discussionand

algorithmic

analysis.E.g.,

time,space,

completeness,

optimality.

+Reflections:

advantagesand

disadvantages

ofyour

approach(es)

+Numerical

experiments,

analysingthe

efficiencyofyour

implementations

(e.g.onstandard

benchmarksand

vs.appropriate

reference

algorithms)

Communication

skills

(15points)

Hardtofollow

withnoclear

narrative.

Inadequateor

noseparation

ofdiscussion

textinto

coherent

sections.

Writingisnot

accurateor

articulate.

Inadequate

supporting

materials.

Inadequateor

missing

referencing.

Thewritinghas

atenuously

logical

narrative.Some

attemptatthe

expected

structural

elements(e.g.

Intro,

conclusion).

Writingisnot

accurateor

articulatemost

ofthetime.

Thedocument

hasfew

supporting

materials

(tables,images,

pseudo-code).

Thestudenthas

attemptedto

undertake

citingand

referencing

withfrequent

errors.

Thetexthasa

clearlogical

narrativaeand

expected

structural

elements(e.g.

intro,conclusion).

Writingisnot

accurateor

articulatemostof

thetime.

Therearesome

supporting

materials(tables,

images,

pseudo-code)but

notwellintegrated

withtherestof

thetext.

Thestudent

followsthe

requirementsfor

citingand

referencing,with

somenotable

errors.

Thewritingis

wellcomposed

andhasaclear

andlogical

narrativeandis

wellstructured.

Writingis

generally

accurateand

articulate.

Thedocument

hasappropriate

supporting

materialsthat

arewell

integratedwith

therestofthe

text.

Thestudent

followsthe

requirementsfor

citing

andreferencing,

with

someminor

errors.

Thewritingisvery

wellcomposed

andhasavery

clearandlogically

formednarrative

asawhole.

Writingisaccurate

andarticulate.

Thedocumentis

expertlystructured

inthestyleofa

scientificreport,

including

appropriate

supporting

materialsthat

clearlyimprovethe

qualityof

associated

discussion.

Thestudent

followsthe

requirementsfor

citingand

referencing.

Assignment1-FIT5222Planningandautomatedreasoning

BonusPoints

Wewillissuebonuspointsforstudentsimplementingmultipleapproachesforthesame

problem,and/orforimplementationsofalgorithmsfromthescientificliteraturethatarenot

discussedduringtutorials/lectures(e.g.,fromoneoftherecommendedpapersor

elsewhere).Thesizeofthebonusdependsonhowambitioustheimplementationis,its

effectivenessandthequalityofthewriteup.

BONUSPOINTSCANMAKETHEDIFFERENCEBETWEEN‘D’and‘HD’

Grades

Thetotalpointsfortheassignmentis150.Apassinggradeis50%oftotalpoints,whichis

75points.

SUBMISSION

Theassignmentisdueon12thSeptember202423:55pm(ThursdayofWeek8)

SubmittoContestServer:

●Thecontestserverandsubmissioninstructionwillbereleasedsoon.Youwill

receiveanotificationwhenit’sready.

●FollowtheFIT5222FlatlandChallengeSubmissionInstructiontosubmityour

codestocontestserver.

●Yourcodewillbeautomarkedonthecontestserver,thusyoumustsubmitittothe

contestserver.

SubmittoMoodle:

1.Yourimplementationsourcecodes,inasingledirectorycalled"src"(youcancopy

everythinginthepigletfolderto"src").Zipthecodesdirectorywithfilename

last_name_student_id_flatland.zip.(Forexample,Chen_123456_flatland.zip)

2.Thereportdescribingyourapproachesasasinglepdffile.Namethepdfas

last_name_student_id_report.pdf.(Forexample,Chen_123456_report.pdf)

3.SubmitthetwofilestotheMoodleassignmentsubmissionpage.(Donotzipthepdf

report,asmoodleneedsthepdftogenerateturnitinreport).

TherearenorestrictionsonuseofgenerativeAIforthisassessmenttask,but

studentsshouldaccomplishtheirassessmentsindividually.

Assignment1-FIT5222Planningandautomatedreasoning