Συντάχθηκε 23-08-2012 11:21
από Galateia Malandraki
Email συντάκτη: gmalandraki<στο>tuc.gr
Ενημερώθηκε:
-
Ιδιότητα: υπάλληλος ΑΡΜΗΧ.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Τμήμα Ηλεκτρονικών Μηχανικών & Μηχανικών Υπολογιστών
ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ
ΓΕΩΡΓΙΟΥ ΜΕΘΕΝΙΤΗ
με θέμα
“Συμπεριφορά Παικτών και Στρατηγική Ομάδας για το Πρωτάθλημα RoboCup 3D Simulation”
“Player Behavior and Team Strategy for the RoboCup 3D Simulation League”
Παρασκευή 24 Αυγούστου 2012, 11πμ
Αίθουσα 145.Π42, Κτίριο Επιστημών, Πολυτεχνειούπολη
Εξεταστική Επιτροπή
Επίκουρος Καθηγητής Μιχαήλ Γ. Λαγουδάκης (επιβλέπων)
Επίκουρος Καθηγητής Γεώργιος Χαλκιαδάκης
Καθηγητής Μίνως Γαροφαλάκης
Περίληψη
Κάθε ομάδα που συμμετέχει σ' ένα ομαδικό άθλημα απαιτεί δεξιότητες τόσο σε ατομικό όσο και σε ομαδικό επίπεδο, προκειμένου να είναι επιτυχημένη. Για ανθρώπινες ομάδες τέτοιες δεξιότητες είναι έμφυτες και φυσιολογικά βελτιώνονται με την πάροδο του χρόνου. Ωστόσο, για ρομποτικές ομάδες αυτές οι ικανότητες θα πρέπει να προγραμματισθούν από τους σχεδιαστές τους. Το ρομποτικό ποδόσφαιρο, γνωστό ως RoboCup, αποτελεί ένα σύνθετο, στοχαστικό, πολυ-πρακτορικό και ανταγωνιστικό περιβάλλον πραγματικού χρόνου. Σ' ένα τέτοιο περιβάλλον, οι ομαδικές ικανότητες είναι εξίσου σημαντικές με τις ατομικές ικανότητες των παικτών, αναλογιζόμενοι ότι στα πρωταθλήματα προσομοίωσης ποδοσφαίρου υπάρχουν μέχρι και 9 ή 11 παίκτες ανά ομάδα. Η παρούσα διπλωματική εργασία παρουσιάζει τον πλήρη σχεδιασμό μιας ομάδας για το πρωτάθλημα RoboCup 3D Simulation, δίνοντας έμφαση στη συμπεριφορά των παικτών, στην στρατηγική της ομάδας και στον συντονισμό της. Οι πράκτορές μας σχεδιάστηκαν με τρόπο που τους επιτρέπει να δρουν αποτελεσματικά τόσο αυτόνομα όσο και ως μέλη της ομάδας. Αρχικά, περιγράφεται η ανάπτυξη των ατομικών δεξιοτήτων των παικτών. Αυτές οι δεξιότητες περιλαμβάνουν τον αξιόπιστο εντοπισμό της θέσης τους και την αξιόπιστη παρακολούθηση αντικειμένων, την μετακίνηση και τις ποδοσφαιρικές κινήσεις, την εκτέλεση βασικών και πολύπλοκων ενεργειών, καθώς και την επικοινωνία με τους συμπαίκτες. Στη συνέχεια, περιγράφεται ένα ιεραρχικό πρωτόκολλο συντονισμού, το οποίο συντονίζει όλες τις επιμέρους ικανότητες των παικτών παρέχοντας μια πλήρη συμπεριφορά για κάθε πράκτορα στα πλαίσια μιας συνολικής στρατηγικής για την ομάδα. Η προσέγγισή μας βασίζεται αρχικά στην ανταλλαγή και σύνθεση πληροφοριών για την κατάσταση του παιχνιδιού και κατόπιν στην αποσύνθεση του προβλήματος του συνολικού συντονισμού για τους 9 ή τους 11 παίκτες σε μικρότερα προβλήματα συντονισμού για υποσύνολα παικτών που καθορίζονται δυναμικά βάσει ενός προσαρμοζόμενου σχηματισμού της ομάδας. Ένας εξαντλητικός αλγόριθμος χρησιμοποιείται για να εξαχθεί ένα βέλτιστο σύνολο ενεργειών για το σημαντικότερο υποσύνολο ενεργών παικτών (οι τρεις πλησιέστεροι στην μπάλα), ενώ ένας λιγότερο δαπανηρός αλγόριθμος δυναμικού προγραμματισμού χρησιμοποιείται για να αντλήσουν τις ενέργειές τους οι υπόλοιποι παίκτες (υποστηρικτικοί παίκτες). Οι συντονισμένες ενέργειες αξιολογούνται μέσω μιας συνάρτησης που συνδυάζει κόστη σχετικά με τις θέσεις, τις αποστάσεις, τις πιθανές συγκρούσεις και την κάλυψη του γηπέδου. Η προσέγγισή μας και η υλοποίησή μας σε Java επιτρέπουν στην ομάδα μας να υπολογίζει συντονισμένες δράσεις περίπου κάθε δύο δευτερόλεπτα αποδίδοντας γρήγορη ανταπόκριση στις δυναμικά μεταβαλλόμενες συνθήκες του παιχνιδιού. Τα αποτελέσματα που προέκυψαν από πλήρεις αγώνες απέναντι σε υπάρχουσες ομάδες, μερικές από τις οποίες αγωνίζονται για αρκετά χρόνια στο πρωτάθλημα RoboCup 3D Simulation, αποκαλύπτουν ότι η ομάδα μας είναι ιδιαίτερα ανταγωνιστική ως επί το πλείστον χάρη στο προτεινόμενο πρωτόκολλο συντονισμού.
Abstract
Any team participating in a team sport requires both individual and team skills in order to be successful. For human teams, these skills are inherent and naturally improve over time. However, for robot teams these skills must be programmed by the designers of the team. Robotic soccer, known as RoboCup, represents a complex, stochastic, real-time, multi-agent, competitive domain. In such domains, team skills are as important as individual player skills, considering that in soccer simulation leagues there are up to 9 or 11 players per team. This thesis presents a complete team design for the RoboCup 3D Simulation League focusing on player behavior, team strategy, and team coordination. Our agents are designed in a way that enables them to act effectively both autonomously and as members of the team. Initially, the development of the individual player skills is described. These skills include robust self localization and object tracking, effective locomotion and soccer motions, basic and complex action execution, and communication with teammates. Subsequently, a hierarchical coordination protocol is described, which coordinates all the individual player skills yielding a complete behavior for each agent within the frame of a global team strategy. Our approach is based on first sharing and fusing information about the game state and then decomposing the global coordination problem for the 9 or 11 players to smaller coordination problems over dynamically-determined subsets of players adhering to an adaptive global team formation. An exhaustive algorithm is used over the most important subset of active players (the three ones closest to the ball) to derive an optimal set of actions, whereas a less-expensive dynamic programming algorithm is used over the remaining players (support players) to derive their actions. Coordinated actions are evaluated through a function that combines costs related to positions, distances, potential collisions, and field coverage. Our approach and our Java implementation enable the team to compute coordinated actions approximately every two seconds yielding quick responsiveness to dynamically changing game states. The results of complete games against existing teams, some of which compete for several years in the RoboCup 3D Simulation League, reveal that our team is quite competitive mostly thanks to the proposed coordination approach.
Συνημμένα:
-
2012-08-23-Methenitis-Announcement.doc
Μεταφορτώσεις: 184,
Μέγεθος: 39 KB application/msword
