Ants project. AI Challenge theme.
Python JavaScript Java C C++ Shell
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
lin
.gitignore
Doxyfile
MyBot.py
README
ants.py
bot32
bot64
logFile.log
logutils.py
script_run.sh

README

BasculAnts PA project.

* Membrii:
    Bărbulescu Mihai - 325 CA
    Petre Andrei - 325CA
    Stana Iulian - 325CA
    Traistă-Popescu Vlad - 325CA

* Mediu de dezvoltare: vim și/sau Eclipse cu PyDev/Egit
* Mod de compilare: Interpretor Python
* Versionare: repository privat pe github

* Rulare bot:
    Rularea hartilor pentru etapa 1 se face prin script_run.sh. Pt rulare bot,
    folositi python MyBot.py sau ./MyBot.py (dacă se rulează cu a doua variantă
    trebuie să dați chmod a+x la MyBot.py). În fișierul script_run.sh am adunat
    laolată toate comenzile care rulează cele 4 hărți pentru prima etapă, pentru
    testarea botului.

* Abordarea algoritmică a etapei:
      Folosim A* pentru a trimite furnica spre o zona unde dorim noi. A*
    functioneaza pe ideea clasica, cu un scor de estimare a drumului bazat pe
    distanta de la inceput si pe cat mai are pana la destinatie (optimist).
    Complexitatea A* este proportionala cu lungimea de la sursa la destinatie
    (Theta(n)), doar ca spatiul folosit este mai mare. Pentru fiecare
    nod din spatiul starilor, adaugam toti vecinii lui (maxim 4), deci crestere
    exponentiala. Acestia sunt adaugati intr-un heap (complex. O(log(m)), m
    fiind nr de elemente in heap, care creste exponential, deci m ~ 4^k, deci
    complexitatea e cam O(k) pentru fiecare inserare) si extrasi in timp
    constant. Deci ar fi cam Theta(n*k). Probabil e loc de imbunantatiri.
      Pentru fiecare mutare, calculam pentru fiecare furnica (N furnici) noua
    directie in care sa mearga. Daca vede mancare, ii calculam drumul cu A*
    pana la mancare, altfel daca are deja un drum, continua pe el (drumurile le
    pastram intr-un dictionar "paths", deci e timp constant verificare si
    extragere / adaugare de o noua instanta). Daca nu vede mancare, o trimitem
    spre cea mai apropiata zona neexplorata, tot cu A* calculand distanta.
      Deci O(n*N*k) ~ O(n^3) complexitate pe mutare. Totodata, pentru fiecare
    mutare, mai updatam harta cu ceea ce vede fiecare furnica in parte, prin
    ants.landmap(). Asta dureaza O(N*viewradius2), unde N = nr de furnici.
      Se executa mapfilter() in landmap() o singura data, deci O(viewradius2).
      Complexitatea per mutare este O(n^3) + O(N*viewr2) + O(viewr2) = O(n^3).
      Am vrut sa folosim un A* pentru ca e mai exact decat un simplu bfs,
    conduce spre solutie mai rapid.

* Structura proiectului:
(extrasa din [a1], am folosit Doxygen)

class MyBot:

  Public attributes:
      paths
      logger

  Public member functions:
    def __init__(self)
      Initializeaza jurnalizaarea.
      Utila pentru debug sau informatii despre desfasurarea jocului.

    def heuristic_cost_estimate(self, (row1, col1), (row2, col2), ants):
      Obtine estimarea costului; e optimista.

      Parameters:
        start     - punctul din care pleaca furnica.
        goal      - puncul la care se doreste sa ajunga furnica.
      Returns:
        Distanta euclidiana minima de patratele pe care o parcurge furnica.


    def neighbor_nodes(self, current, ants):
      Returneaza toti vecinii nodului curent.

      Parameters:
        curent    - pozitia curenta, de forma (row, col).
      Returns:
        Lista continand vecinii nodului.

    def reconstruct_path(self, came_from, current_node):
      Construieste drumul din parinte in parinte, pana la nodul initial (de la
      sfarsit spre inceput).

      Parameters:
        current_node - nodul final, unde ajunge calea construita; e de forma
                       unui tuplu (row, col).
        came_from    - contine parintii nodurilor ce formeaza calea spre nodul
                       final.

    def Astar(self, start, goal, ants):
      Intoarce o cale optima de la sursa la destinatie.

      In prezent tine cont si de obstacole, dar trimite furnicile doar dupa
      mancare sau puncte necunoscute

      Parameters:
      start - punct de start, de forma (row, col).
      goal  - punct destinatie, de forma (row, col).
      ants  - obiectul furnici, construit in Ants.run().

class Ants:

  Public attributes:
      map_filter
      land_map

  Public member functions:
    def  mapfilter
      Creaza un filtru de translatare.

      Prin aplicarea filtrului asupra unei coordonate oarecare (row, col),
      acesta genereaza toate coordonatele din jurul (row, col) cu raza^2 <=
      self.viewradius2.

    def  landmap
      Aplica filtrul mapfilter() asupra fiecarei furnici.

      Translata pozitia furnicii la coordonate in jurul pozitiei furnicii,
      obtinand astfel zona pe care o vede furnica, de raza r. Pentru fiecare
      furnica, vom updata teritoriul neexplorat cu ceea ce vede pe moment
      furnica.

* Contribuțiile membrilor echipei:
    Bărbulescu Mihai - a realizat documentația proiectului,
    a adăugat posibilitatea de logging cu ajutorul căruia
    s-au putut testa codul și depana erorile.

    Petre Andrei - a implementat explorarea A* și a pus bazele
    modului în care furnicile se deplasează pe hartă
    (TODO - de adăugat ce tutoriale de pe net a folosit la
    surse de inspirație)

    Stana Iulian - a implementat funcțiile mapfilter și landmap
    și implicit a adus îmbunătățiri la modul de explorare a
    furnicilor (bazate pe functia visible din [c1])

    Vlad Traistă-Popescu - a realizat unit-testing și a făcut
    debugging pe fiecare commit al membrilor atunci când
    programul nu rula cum trebuie.

* Surse de inspirație:
    [s1] Cristian A. Giumale – Introducere în Analiza Algoritmilor,
         Polirom, 2004 (capitolul 7)
    [s2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
         și Clifford Stein – Introduction to Algorithms,
         Third Edition, MIT Press, 2009
    [s3] http://swarm.cs.pub.ro/~adrian.sc/documentatie.pdf
    [s4] http://en.wikipedia.org/wiki/A*_search_algorithm

* Surse de cod:
    [c1] https://github.com/wraithan/aichallenge-ants/blob/master/ants.py

* Alte linkuri:
    [a1] http://swarm.cs.pub.ro/~mbarbulescu/.secret/html/