RoboCourier - Трудност: HARD

RoboCourier - Трудност: HARD | MLCompete

Описание на задачата

Poveste

În orașul Algorithmia, livrările rapide nu mai sunt făcute de curieri umani, ci de roboți autonomi. Un astfel de robot, numit RoboCourier, trebuie să transporte pachete între diferite puncte ale orașului.

Orașul este însă plin de situații dificile: drumuri blocate, semafoare, zone alunecoase, vânt lateral și baterii care se descarcă. RoboCourier trebuie să decidă nu doar drumul cel mai scurt, ci drumul cu cea mai bună recompensă obținută în urma simulării.

Pentru fiecare scenariu, robotul primește o hartă, poziția inițială, energia disponibilă și lista pachetelor. Programul concurentului trebuie să producă o secvență de acțiuni pe care evaluatorul o va simula automat.

Harta

Orașul este reprezentat ca o matrice cu N linii și M coloane.

Fiecare celulă conține unul dintre următoarele simboluri:

Simbol	Semnificație
`.`	drum normal
`#`	obstacol; robotul nu poate intra în această celulă
`C`	stație de încărcare
`S`	zonă alunecoasă
`W`	zonă cu vânt lateral
`T`	semafor

Pachetele nu sunt marcate direct în hartă. Ele sunt date separat prin coordonatele sursei și destinației.

Coordonatele sunt indexate de la 0.

Acțiuni posibile

La fiecare pas, RoboCourier poate executa una dintre acțiunile:

1UP DOWN LEFT RIGHT WAIT PICK DROP CHARGE

Semnificație:

Acțiune	Efect
`UP`	deplasare cu o linie în sus
`DOWN`	deplasare cu o linie în jos
`LEFT`	deplasare cu o coloană la stânga
`RIGHT`	deplasare cu o coloană la dreapta
`WAIT`	robotul așteaptă o unitate de timp
`PICK`	robotul ridică un pachet aflat în celula curentă
`DROP`	robotul livrează pachetul transportat, dacă se află la destinația lui
`CHARGE`	robotul se încarcă dacă se află pe o celulă `C`

Robotul poate transporta cel mult un pachet la un moment dat.

Reguli de simulare

O acțiune de deplasare consumă 1 unitate de energie și produce o penalizare de -1 în scor.

Dacă robotul încearcă să intre într-un obstacol sau în afara hărții, rămâne pe loc și primește o penalizare suplimentară.

Acțiunea WAIT consumă 1 unitate de energie și produce o penalizare de -1 în scor.

Acțiunile PICK și DROP consumă o unitate de timp, dar nu consumă energie.

Acțiunea CHARGE consumă o unitate de timp și crește energia robotului cu 5 unități, fără a depăși energy_cap, dacă robotul se află pe o celulă C. Dacă robotul nu se află pe o celulă C, acțiunea este considerată invalidă.

Dacă energia robotului ajunge la 0, episodul se termină.

Dacă numărul de pași executați ajunge la max_steps, episodul se termină.

Elemente stochastice

În unele subtask-uri apar celule cu efect aleatoriu.

Celule alunecoase `S`

Dacă robotul ajunge pe o celulă S după o acțiune de deplasare, atunci cu probabilitatea p_slide este mutat automat încă o celulă în aceeași direcție.

Dacă a doua celulă este invalidă, alunecarea nu se produce.

Celule cu vânt `W`

Dacă robotul ajunge pe o celulă W după o acțiune de deplasare, atunci cu probabilitatea p_wind este mutat automat într-una dintre cele două direcții perpendiculare pe direcția deplasării inițiale, aleasă uniform aleator.

Dacă celula rezultată este invalidă, robotul rămâne pe loc.

Semafoare `T`

O celulă T poate fi traversată doar atunci când semaforul este deschis.

La momentul t, semaforul este deschis dacă:

1t mod traffic_period este 0 sau 1

În restul timpului, semaforul este închis.

Dacă robotul încearcă să intre într-o celulă T când semaforul este închis, mutarea este blocată, robotul rămâne pe loc și primește penalizarea pentru acțiune invalidă.

Pachete

Fiecare pachet are:

1id, sursă, destinație, recompensă, deadline

Un pachet poate fi ridicat doar din celula sa sursă, prin acțiunea PICK.

Un pachet poate fi livrat doar în celula sa destinație, prin acțiunea DROP.

Dacă pachetul este livrat până la deadline, se acordă recompensa completă.

Dacă pachetul este livrat după deadline, recompensa este diminuată proporțional cu întârzierea, conform regulilor implementate în evaluator.

Un pachet poate fi livrat cel mult o dată.

Date de intrare

Datasetul este format din trei fișiere CSV:

1train.csv2val.csv3test.csv

Toate scenariile sunt stocate în același tip de fișier tabelar.

Coloanele principale sunt:

Coloană	Descriere
`datapointID`	identificatorul scenariului
`subtaskID`	subtask-ul din care face parte scenariul
`rows`	numărul de linii ale hărții
`cols`	numărul de coloane ale hărții
`grid`	harta codificată ca șir; liniile sunt separate prin `/`
`start_r`	linia inițială a robotului
`start_c`	coloana inițială a robotului
`energy`	energia inițială
`energy_cap`	energia maximă permisă
`max_steps`	numărul maxim de pași simulați
`packages`	lista pachetelor, în format JSON compact
`p_slide`	probabilitatea de alunecare
`p_wind`	probabilitatea de deviere din cauza vântului
`traffic_period`	perioada semafoarelor

În train.csv și val.csv există și coloanele:

Coloană	Descriere
`target_actions`	o secvență demonstrativă de acțiuni
`oracle_score`	scorul mediu al secvenței demonstrative

În test.csv, coloanele target_actions și oracle_score nu sunt disponibile.

Secvența target_actions nu este garantată ca fiind optimă. Ea este oferită doar ca exemplu de soluție validă.

Formatul hărții în CSV

Exemplu de hartă:

1..#..C/.S..T./..W.../C..#..

Aceasta reprezintă harta:

1..#..C2.S..T.3..W...4C..#..

Formatul pachetelor

Coloana packages conține o listă JSON.

Exemplu:

JSON
1[{"id":0,"sr":1,"sc":0,"dr":3,"dc":5,"reward":100,"deadline":25}]

Aici există un pachet:

id-ul pachetului este 0;
sursa este (1, 0);
destinația este (3, 5);
recompensa maximă este 100;
deadline-ul este 25.

Date de ieșire

Participanții trebuie să trimită un fișier submission.csv cu următoarele coloane:

1datapointID,subtaskID,answer2test_000000,1,DOWN;LEFT;LEFT;PICK;DOWN;RIGHT;RIGHT;DROP3test_000001,2,UP;UP;RIGHT;WAIT;RIGHT;PICK;LEFT;DROP

Coloana datapointID trebuie să corespundă identificatorului scenariului din test.csv.

Coloana subtaskID trebuie să conțină subtask-ul scenariului.

Coloana answer conține acțiunile separate prin caracterul ;.

Pentru fiecare scenariu din test.csv trebuie să existe exact o linie în submission.csv.

Dacă secvența este mai scurtă decât max_steps, evaluatorul consideră că robotul execută WAIT pentru restul pașilor.

Dacă secvența este mai lungă decât max_steps, acțiunile suplimentare sunt ignorate.

Format valid al răspunsului

În coloana answer sunt permise doar acțiunile:

1UP DOWN LEFT RIGHT WAIT PICK DROP CHARGE

Acțiunile trebuie scrise cu majuscule și separate prin ;.

Exemple valide:

1RIGHT;PICK;DOWN;DROP2WAIT;WAIT;RIGHT;CHARGE

Exemple invalide:

1RIGHT PICK DOWN DROP2right;pick;down;drop3RIGHT, PICK, DOWN, DROP

Evaluare

Evaluatorul simulează acțiunile trimise de concurent.

Pentru fiecare scenariu se calculează un scor brut, compus din:

recompense pentru pachetele livrate;
penalizări pentru pași;
penalizări pentru acțiuni invalide;
penalizări pentru pachete nelivrate;
bonus pentru energie rămasă după livrarea tuturor pachetelor.

Pentru scenariile stochastice, aceeași secvență de acțiuni este simulată pe mai multe seed-uri ascunse, iar scorul final al scenariului este media scorurilor obținute.

Scorul brut este normalizat folosind valori de referință precalculate pentru fiecare scenariu. Aceste valori nu sunt disponibile în test.csv, dar sunt folosite de evaluator pentru a face scenariile comparabile între ele.

Punctajul total este suma punctajelor obținute pe cele patru subtask-uri:

Subtask	Punctaj
Subtask 1	20 puncte
Subtask 2	25 puncte
Subtask 3	25 puncte
Subtask 4	30 puncte

Pentru leaderboard-ul public, punctajul este calculat doar pe o parte dintre scenariile de test.

Pentru evaluarea finală, punctajul este calculat pe toate scenariile de test.

Subtask-uri

Subtask 1 — traseu determinist cu un singur pachet (20 puncte)

Pentru acest subtask, sunt garantate următoarele constrângeri:

există un singur pachet;
nu apar celule stochastice;
nu există vânt;
nu există semafoare active;
energia este suficientă.

Subtask 2 — mai multe pachete și energie limitată (25 puncte)

Pentru acest subtask, sunt garantate următoarele constrângeri:

pot exista mai multe pachete;
pot apărea stații de încărcare C;
mediul este determinist;
energia este limitată.

Subtask 3 — hărți stochastice mari (25 puncte)

Pentru acest subtask, sunt garantate următoarele constrângeri:

pot exista mai multe pachete;
pot apărea zone alunecoase S;
poate apărea vânt W;
pot apărea semafoare T;
hărțile pot fi mai mari decât în celelalte subtask-uri.

Subtask 4 — hărți stochastice mici (30 puncte)

Pentru acest subtask, sunt garantate următoarele constrângeri:

hărțile sunt mici;
există un singur pachet;
pot exista tranziții stochastice;
numărul de pași este limitat.

Exemplu minimal

Rând din test.csv:

Python
1datapointID,subtaskID,rows,cols,grid,start_r,start_c,energy,energy_cap,max_steps,packages,p_slide,p_wind,traffic_period2test_000000,1,3,4,...#/..../....,0,0,20,20,30,"[{""id"":0,""sr"":0,""sc"":1,""dr"":2,""dc"":3,""reward"":100,""deadline"":12}]",0,0,4

O ieșire posibilă în submission.csv:

1datapointID,subtaskID,answer2test_000000,1,RIGHT;PICK;DOWN;DOWN;RIGHT;RIGHT;DROP

Poveste

Harta

Acțiuni posibile

Reguli de simulare

Elemente stochastice

Celule alunecoase S

Celule cu vânt W

Semafoare T

Pachete

Date de intrare

Formatul hărții în CSV

Formatul pachetelor

Date de ieșire

Format valid al răspunsului

Evaluare

Subtask-uri

Subtask 1 — traseu determinist cu un singur pachet (20 puncte)

Subtask 2 — mai multe pachete și energie limitată (25 puncte)

Subtask 3 — hărți stochastice mari (25 puncte)

Subtask 4 — hărți stochastice mici (30 puncte)

Exemplu minimal

Celule alunecoase `S`

Celule cu vânt `W`

Semafoare `T`