Symbolic representations and common - sense reasoning in open multi - agent systems

Abstract

This thesis concerns with intelligent autonomous software agents that populate open computational environments, in which they interact for various purposes, e.g. competitively in the case of auctions or resource allocation problems, collaboratively in the case of distributed problem solving or parallel processing, joint planning, etc. We use the term open to characterize a computational environment in Hewitt’s sense, that is to describe an environment that is dynamic, continuous, unobservable (or, at best, partially observable) and non-deterministic. Agents in such environments possess, unavoidably, information that is incomplete, imprecise, maybe even incorrect, due to the very fact that the environment is open and, at the very least, agents join and leave it as they please. The information exchanged between agents may be delayed, or distorted by noise during its communication, and in any case, as the environment evolves, it is bound to change. The interactions among agents in any multi-agent system are typically governed by norms. These may refer to restrictions on communication means among agents, or to particular coordination mechanisms, liveness and safety properties of the system etc. In some application areas, such as ecommerce, additional norms may regulate the agents’ behaviours, resulting from agreements into which the agents enter willingly, and possibly from the protocol that governs the e-market. Norms prescribe what each agent is obliged, permitted, prohibited, empowered and so on, to do during its life in the particular environment. Autonomous agents decide for themselves which norms to subject itself to and whether to comply with the norms of their environment. This decision-making is all the more challenging when an agent has to perform it in circumstances where its available knowledge is incomplete/imprecise/incorrect. This thesis addresses the need and requirement for common-sense reasoning agents in open computational environments. We discuss and illustrate our proposals with reference to an e-commerce example. First, based on the example scenario, we identify the requirements for the representation of the norms that govern the environment and the specifications for the environment itself. Nevertheless, our proposals are generally applicable to any case where multiple agents interact and their interaction is governed by some contract as a coordination or collaboration mechanism. Primarily, this thesis examines and motivates the need of agents to fill in information gaps by resorting to assumptions. Agents need to be able to identify and use assumptions dynamically, in any open computational environment, as well as in the particular application context of an e-commerce example. We present a novel approach to dynamic assumption identification and hypothetical nonmonotonic reasoning inspired by the syntax and semantics of Default Logic, without however resorting to proof, which is notably computationally hard. We discuss in detail what distinguishes our approach from other work on dynamic assumption based reasoning, namely i.e., we do not resort to a prespecified pool of assumptions, nor to goal-orientation as a means to identify candidate assumptions. In this way, we claim, an agent is autonomous in deciding which assumptions are appropriate, given its knowledge-hypotheses requirements at any given time. We propose symbolic and schematic representations to characterize formally the possible knowledge-hypotheses status of an agent, and we use their properties to characterize their dynamics. From these formal characterizations we derive and present the algorithms that support our approach, which we have implemented in a prototype.

Η παρούσα διατριβή αφορά στους ευφυείς και αυτόνομους πράκτορες λογισμικού ως μέλη ενός ανοιχτού υπολογιστικού περιβάλλοντος, στο πλαίσιο του οποίου αλληλεπιδρούν με διάφορους σκοπούς, για παράδειγμα, ανταγωνιστικά στην περίπτωση δημοπρασίας ή προβλημάτων κατανομής πόρων, συνεργατικά στην περίπτωση κατανεμημένης επίλυσης προβλημάτων, συντονισμένου σχεδιασμού ενεργειών κ.α. Χρησιμοποιούμε τον όρο ανοιχτό για να χαρακτηρίσουμε ένα υπολογιστικό περιβάλλον κατά την έννοια που αποδόθηκε από τον Hewitt, δηλαδή ένα περιβάλλον δυναμικό, συνεχές, μη παρατηρήσιμο (ή, στην βέλτιστη περίπτωση, μερικώς παρατηρήσιμο) και μη αιτιοκρατικό. Σε αυτού του είδους τα περιβάλλοντα, οι πράκτορες, αναπόφευκτα, κατέχουν πληροφορία η οποία είναι μη πλήρης, μη ακριβής, και ίσως, μη ορθή, εξαιτίας του γεγονότος πως το περιβάλλον είναι ανοιχτό, και στην ελάχιστη περίπτωση, οι πράκτορες εισέρχονται και αποχωρούν από το περιβάλλον κατά βούληση. Η πληροφορία που ανταλλάσσεται μεταξύ των πρακτόρων μπορεί να καθυστερεί ή να στρεβλώνεται από θόρυβο κατά τη διάρκεια της επικοινωνίας, και σε κάθε περίπτωση, καθώς το περιβάλλον εξελίσσεται, η πληροφορία αλλάζει κατ’ ανάγκη. Οι αλληλεπιδράσεις μεταξύ των πρακτόρων σε ένα πολύ-πρακτορικό σύστημα, συνήθως, ελέγχονται από κανόνες. Αυτοί μπορεί να αναφέρονται σε περιορισμούς των μέσων επικοινωνίας μεταξύ των πρακτόρων, σε ιδιαίτερους μηχανισμούς συντονισμού, στην ασφάλεια του συστήματος κ.α. Σε μερικές περιοχές εφαρμογής, όπως το ηλεκτρονικό εμπόριο, μπορεί ενδεχομένως, επιπρόσθετοι κανόνες να διέπουν τη συμπεριφορά των πρακτόρων, οι οποίοι προκύπτουν από συμφωνίες στην οποίες ο πράκτορας εισέρχεται κατά βούληση, και πιθανώς από πρωτόκολλα τα οποία διέπουν την ηλεκτρονική αγορά. Οι κανόνες υπαγορεύουν στους πράκτορες τι υποχρεούνται, επιτρέπεται, απαγορεύεται, έχουν εξουσιοδότηση κ.α., να πράξουν κατά τη διάρκεια της παρουσίας τους στο συγκεκριμένο περιβάλλον. Οι αυτόνομοι πράκτορες αποφασίζουν για τον εαυτό τους σε ποιούς κανόνες υπάγονται και εάν θα υπακούουν στους κανόνες τους περιβάλλοντος τους. Αυτή η απόφαση αποτελεί, ακόμα μεγαλύτερη πρόκληση, όταν οι πράκτορες θα πρέπει να τη λάβουν σε συνθήκες όπου κατέχουν πληροφορία μη πλήρη/μη ακριβή/μη ορθή. Αυτή η διατριβή ασχολείται με την ανάγκη και την απαίτηση για πράκτορες κοινής λογικής στα ανοικτά υπολογιστικά περιβάλλοντα. Συζητάμε και απεικονίζουμε τις προτάσεις μας αναφορικά με ένα παράδειγμα ηλεκτρονικού εμπορίου. Αρχικά, βάση του πρότυπου σεναρίου, καθορίζουμε τις απαιτήσεις για την αναπαράσταση των κανόνων που διέπουν το περιβάλλον και τις προδιαγραφές του περιβάλλοντος καθαυτού. ?στόσο, οι προτάσεις μας είναι γενικότερα εφαρμόσιμες σε κάθε περίπτωση όπου πολλαπλοί πράκτορες αλληλεπιδρούν και οι αλληλεπιδράσεις τους καθορίζονται από μια συμφωνία που δρα ως μηχανισμός συνεργασίας και συντονισμού. Πρωτίστως, η διατριβή εξετάζει και αποτελεί κίνητρο της ανάγκης των πρακτόρων να καλύψουν κενά στην πληροφορία που κατέχουν μέσω υποθέσεων. Οι πράκτορες οφείλουν να είναι ικανοί να προσδιορίζουν και να χρησιμοποιούν υποθέσεις δυναμικά, σε κάθε ανοιχτό υπολογιστικό περιβάλλον,