Σχεδιασμός κίνησης ρομπότ σε περιβάλλον εμποδίων

Abstract

Developing autonomous robots (either mobile or articulated robots) is a fundamental goal in modern industrial production systems and has attracted the attention of many researchers from the robotics fields. The robots must be able to accept high-level instructions of their missions and carry out these missions (at the lowest cost) by making their own decisions while moving safely in the shop floor. Such vehicles will be capable to accept high level descriptions of desired tasks and execute them without any human intervention. The theme of this thesis is the study and the solution of the motion planning problem either for one robot or for a set of robots (mobile or articulated robots). Most of the industrial applications such as pickup and delivery of products, spot-welding, multiple drilling, laser cutting and car-painting, they demand the smooth motion of the robot (or the robots) in the workspace. Each robot should be able to avoid the obstacles (static or moving) or the other robots. The complexity of the problem is depended by the geometry of the environment, the dimension of the robots’ workspace and by the robots’ kinematical constraints. Firstly, the generalization of the Bump-Surface concept for the solution of the motion planning problem in multidimensional workspaces is presented. Using the generalized Bump-Surface concept, the properties of the workspace are transferred into the surface which is constructed by B-Spline Surfaces. The robot’s path is represented by a B-Spline curve in the initial environment. The main target was the development of a methodology which is able to solve the basic motion planning problem and its generalizations. Secondly, is presented the computational time study required to construct the generalized Bump-surface depends only on the geometry and on the dimension of the environment. Furthermore, is presented the computational time required to solve the motion planning problem with constant workspace and varying number of robots. In contract with previous methods which are solved the motion planning problem for non-holonomic robots in two phases, in the present thesis is presented a solution of the problem under a global way with the capacity to handle either holonomic or non-holonomic robot (or a set of robots) moving in a dynamic 2D environment. Furthermore, is presented for a first time the solution of the combinatorial problem of motion planning and task scheduling for a set of robots.

Η δημιουργία αυτόνομων ρομπότ (είτε οχημάτων ή αρθρωτών ρομπότ) έχει προσελκύσει το ενδιαφέρον πολλών ερευνητών που ασχολούνται με το αντικείμενο της ρομποτικής. Τα ρομπότ πρέπει να είναι ικανά να δέχονται υψηλού-επιπέδου οδηγίες για την εργασία τους και να την εκτελούν (με το μικρότερο δυνατόν κόστος) παίρνοντας μόνα τους αποφάσεις καθώς κινούνται με ασφάλεια στο χώρο εργασίας τους. Οι οδηγίες θα καθορίζουν τι πρέπει να κάνουν χωρίς να ορίζουν το τρόπο που θα το κάνουν. Αναγνωρίζοντας ότι η εκτέλεση οποιασδήποτε εργασίας από ένα ή περισσότερα ρομπότ είναι μια ακολουθία από διαδοχικές κινήσεις στο χώρο εργασίας τους, το ελάχιστο που μπορεί κάποιος να περιμένει από ένα ρομπότ είναι η ικανότητα δημιουργίας της διαδρομής που πρέπει να ακολουθήσει για να εκτελέσει τις απαιτούμενες εργασίες. Αντικείμενο της παρούσας διατριβής είναι η μελέτη και η επίλυση του προβλήματος σχεδιασμού κίνησης για ένα ή περισσότερα ρομπότ (είτε οχημάτων ή βραχιόνων) τα οποία καλούνται να εκτελέσουν μια σειρά από εργασίες. Αρκετές βασικές βιομηχανικές και μη εφαρμογές όπως παραλαβή και παράδοση προϊόντων, συνεχής συγκόλληση, καθαρισμός κτιρίων κτλ, απαιτούν την ομαλή κίνηση του ρομπότ στο χώρο εργασίας του. Το ρομπότ θα πρέπει να αποφεύγει κινούμενα ή ακίνητα εμπόδια ή ακόμη και άλλα ρομπότ τα οποία μπορεί να εργάζονται στον ίδιο χώρο. Η δυσκολία του προβλήματος εξαρτάται από: τη γεωμετρία (πολυπλοκότητα) του περιβάλλοντος, τη διάσταση του χώρου εργασίας, τη διάσταση του ρομπότ και τους κινηματικούς περιορισμούς του ρομπότ. Αρχικά, έγινε η γενίκευση της Bump-Surface καθώς επίσης και το μαθηματικό της μοντέλο για την αντιμετώπιση του προβλήματος ΣΚΡ σε πολυδιάστατους χώρους. Με την χρήση της γενικευμένης Bump-Surface, οι ιδιότητες του χώρου εργασίας στον οποίο κινείται το ρομπότ μεταφέρονται στην επιφάνεια η οποία κατασκευάζεται χρησιμοποιώντας γενικευμένες B-Spline επιφάνειες. Η διαδρομή του κινούμενου αντικειμένου παριστάνεται στο αρχικό περιβάλλον με μια B-Spline καμπύλη. Ο βασικός στόχος ήταν η ανάπτυξη μιας ενιαίας και ολοκληρωμένης μεθοδολογίας για τον σχεδιασμό κίνησης ρομπότ. Με τον τρόπο αυτό συμβάλλουμε στην εξέλιξη των μεθόδων, σχεδιασμού κίνησης ρομπότ εισάγοντας μια μεθοδολογία η οποία θα μπορεί να επίλυση το πρόβλημα σχεδιασμού κίνησης μεταβάλλοντας την διάσταση του χώρου εργασίας και προσθαφαιρώντας κριτήρια και περιορισμούς ανάλογα με το πρόβλημα που θα έχουμε να αντιμετωπίσουμε. Έγινε διερεύνηση, της εξάρτησης του υπολογιστικού χρόνου που απαιτείται για την κατασκευή της γενικευμένης Bump-Surface από την διάσταση και την γεωμετρία του χώρου εργασίας και της εξάρτησης του υπολογιστικού χρόνου που απαιτείται για την επίλυση του προβλήματος ΣΚΡ όταν διατηρείται η γεωμετρία του περιβάλλοντος σταθερή και μεταβάλλεται ο αριθμός των ρομπότ που κινούνται στο χώρο εργασίας. Σε αντίθεση με τις προηγούμενες μεθόδους επίλυσης του προβλήματος σχεδιασμού κίνησης μη-ολονομικών ρομπότ οι οποίες έλυναν το πρόβλημα σε δύο στάδια: (α) προσδιορισμός της βέλτιστης διαδρομής του ρομπότ θεωρώντας το ρομπότ σημειακό (β) τροποποιούν τη διαδρομή λαμβάνοντας υπόψη τη διάσταση του και τους μη-ολονομικούς περιορισμούς του ρομπότ. Στη παρούσα διατριβή, προτάθηκε ένας ενιαίος τρόπος αντιμετώπισης του προβλήματος σχεδιασμού κίνησης μη-ολονομικών ρομπότ όπου τόσο η διάσταση του ρομπότ όσο και οι μη-ολονομικοί περιορισμοί στη κίνηση του λαμβάνονται υπόψη εξ’ αρχής στη διαδικασία εύρεσης της διαδρομής. Επίσης, επιλύθηκε για πρώτη φορά το πρόβλημα σχεδιασμού κίνησης για μια ομάδα ρομπότ με την ταυτόχρονη εύρεση της βέλτιστης διαδρομής για κάθε ένα ρομπότ. Τέλος, η προτεινόμενη μεθοδολογία εφαρμόστηκε με επιτυχία στο συνδυαστικό πρόβλημα ΣΚΡ και προγραμματισμού εργασιών για αυτόνομο όχημα. Λόγω της πολυπλοκότητας των δύο προβλημάτων δεν είχαν προταθεί μέχρι τώρα μέθοδοι για την ταυτόχρονη επίλυση τους.