μικρότερο δυνατό κόστος. Για την επίλυση αυτού του προβλήματος, χρησιμοποι-

ήθηκε ο αλγόριθμος του Lee [40]. Πρόκειται για έναν αλγόριθμο βασισμένο στην

αναζήτηση κατα πλάτος (Breadth First Search, BFS). Αναζήτηση κατά πλάτος είναι

ένας αλγόριθμος για διάσχιση ή αναζήτηση σε δομές δεδομένων τύπου δέντρου ή

γράϕου. Η αναζήτηση ξεκινά από τη ρίζα του δέντρου ή από κάποιο αυθαίρετο

κόμβο του γραϕήματος, που μερικές ϕορές αναϕέρεται ως ”κλειδί αναζήτησης του”

και διερευνά πρώτα τους γειτονικούς κόμβους, προτού μεταβεί στους γείτονες του

επόμενου επίπεδο. Ακολουθεί αντίθετη στρατηγική σε σχέση με την αναζήτηση κατα

βάθος, που διερευνά πρώτα τους κόμβους με το μεγαλύτερο βάθος. Στον αλγόριθμο

2 βλέπουμε τον ψευδοκώδικα του αλγορίθμου του Lee.

Result: Ψευδοκώδικας του αλγορίθμου του Lee
// Stage 1
// select start point and mark with 0
i = 0;

// stage 2

do

// mark all unlabeled neighbors of points marked with i with i+1
i = i + 1

while

target reached OR no points can be marked;

// Stage 3
// go to target point
do

// go to next node that has a lower mark than the current node
// add this node to path
i = i + 1

while

start point reached;

// Stage 4
// block the path for future wirings
// delete all marks

Αλγόριθμος 2: Αλγόριθμος εύρεσης μονοπατιού μεταξύ δύο σημείων στον τρισ-
διάστατο χώρο.

3.6

Διαμοιρασμός της συνολικής περιοχής σε υποπεριοχές για

κάθε όχημα

Σε αυτό το στάδιο, χρησιμοποιώντας τον αλγόριθμο DARP (Divide Areas based

on Robots initial Positions), η περιοχή ενδιαϕέροντος χωρίζεται σε έναν αριθμό υπο-

περιοχών, που η κάθε μια αντιστοιχεί σε ένα συγκεκριμένο όχημα, έτσι ώστε να

εξασϕαλίζεται η πλήρης κάλυψη του συνολικής επιϕάνειας και να εκμεταλλεύεται

37