Distributed constraint optimization, resource allocation and scheduling in large scale agent networks

Abstract

The thesis explores new directions pertaining to methods for scheduling andallocating atomic and complex tasks in large-scale networks of homogeneous orheterogeneous cooperative agents. Tasks are requests for resources managed by theagents that populate the network. The proposed methods encapsulate the concepts ofsearching, task allocation and scheduling seamlessly in decentralized processes.Consequently, there is no need for accumulated or centralized knowledge.Furthermore, centralized coordination is also not necessary. Efficient searching foragent groups that can facilitate the scheduling of tasks is accomplished through theuse of a dynamic overlay structure of gateway agents and the exploitation of routingindices. Gateway agents are network nodes that due to specific topological issues havethe ability to accumulate limited knowledge relevant to the resources available in theirimmediate neighbourhood. They issue, keep and constantly update routing indicesbased on their view on local resources. Routing indices are used for directing requestsχfor resources towards parts of the network where the probability of them beingserved is high. Efficient routing leads to formation of agent teams that try to breakdown each task into smaller pieces and allocate the appropriate resources to it. Thetask allocation and the scheduling of complex tasks are accomplished by combiningdynamic reorganization of agent groups and distributed constraint optimizationmethods. After a complex task has been broken down into subtasks, constraints thatmay exist between the derived subtasks or constraints inherent to the resourceallocation procedure are modelled as a distributed constraint optimization problem.The newly formed agent team that has been assigned the problem tries to solve itoptimizing the cost due to constraints, at the same time. Upon success the requestedresources are allocated accordingly. Otherwise the complex task is forwarded on itsentirety so as to another agent team can be formed and try to solve the problemExperiments have demonstrated promising results.

Η διδακτορική διατριβή παρουσιάζει πρωτότυπες μεθόδους για τον καταμερισμόπόρων και αποτελεσματικό τρόπο κατανομής αυτών σε μεγάλα δίκτυα ομογενών ήετερογενών πρακτόρων. Οι προτεινόμενες τεχνικές συμπεριλαμβάνουν και υλοποιούντις έννοιες της αναζήτησης, του καταμερισμού πόρων και της κατανομής πόρων σεένα ενιαίο σύστημα, πλήρως κατανεμημένο. Δεν είναι απαραίτητο να υπάρχεικεντρικό σύστημα διαχείρισης δεδομένων ή οποιασδήποτε άλλης οντότητας σχετικήςμε τη διαδικασία. Η αποτελεσματική υλοποίηση του περιβάλλοντος επικοινωνίαςμεταξύ ομάδων πρακτόρων και της διαδικασίας αναζήτησης επιτυγχάνεται με τηβοήθεια δικτύων επικάλυψης. Τα δίκτυα αυτά είναι δυναμικά και αποτελούνται απόπράκτορες οι οποίοι λόγω τοπολογίας είναι σε θέση να διατηρούν εκτεταμένη γνώσηόσον αφορά τους πράκτορες με τους οποίους γειτνιάζουν. Διατηρούν επιπλέονδείκτες αναδρομολόγησης που χρησιμοποιούν για την κατεύθυνση του εργασιακούφόρτου προς περιοχές του δικτύου πρακτόρων οι οποίες κρίνεται ότι έχουν αυξημένεςπιθανότητες να ικανοποιήσουν τη ζήτηση σε πόρους. Ο καταμερισμός και ηκατανομή των πόρων του συστήματος γίνονται με δυναμική αναδιάρθρωση ομάδωνπρακτόρων, κάτι το οποίο οδηγεί σε σχηματισμό προσωρινών ομάδων τα μέλη τωνοποίων είναι πιθανοί αποδέκτες τμήματος ή τμημάτων των διεργασιών που απαιτούνπόρους προς ίδια χρήση. Οι διεργασίες που ζητούν πόρους και οι περιορισμοί μεταξύτους ή μεταξύ της διαθεσιμότητας των πόρων του συστήματος μοντελοποιούνται καιπαίρνουν την μορφή ενός κατανεμημένου προβλήματος βέλτιστης ικανοποίησηςπεριορισμών. Στη συνέχεια η νεοσυσταθείσα ομάδα προσπαθεί να λύσει τοκατανεμημένο πρόβλημα. Σε περίπτωση επιτυχίας δεσμεύονται και οι αντίστοιχοιπόροι του συστήματος. Σε άλλη περίπτωση το πρόβλημα προωθείται έτσι ώστε μιαάλλη ομάδα πρακτόρων να συσταθεί και να προσπαθήσει να το λύσει. Πειραματικάαποτελέσματα έχουν δείξει ότι η παραπάνω προσέγγιση επιτυγχάνει άκρωςικανοποιητικά αποτελέσματα.