Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 5 of 5
-
ItemImprovised coordination in agent organisations( 2018)This thesis investigates coordination between intelligent software agents operating within agent organisations. Motivated by the prospect of agents working with humans in real world complex domains, the thesis focuses on flexible behaviour and improvisation in agent organisations. Methods used to design organisations of software agents are explored with particular consideration given to problem situations that cannot be defined with a detailed pre-scripted solution for coordinated action. A conceptual model that describes the components that are needed in an agent based model in a multi-agent system is referred to in this thesis as a meta-model. A number of agent organisation-based meta-models and frameworks for coordination of agents have been proposed such as OperA, OMACS and SharedPlans. There is however, no specific meta-model or approach that addresses agent improvisation and unscripted coordination. The reality of complex coordination in people's behaviour is analysed and used to develop requirements for agents' behaviour. A meta-model is proposed to include components to address these requirements. A process outlining how to design and implement such organisations is presented. The meta-model draws on features in existing models in the literature and describes components to guide agents to behave with flexibility at run time. The thesis argues that coordinated agents benefit from an explicit representation of an organisational model and policies to guide agents' run time behaviour. Policies are proposed to maintain consistent knowledge and mutual plans between team members. Coordination is explicit and some flexibility is given to agents to improvise beyond the solution anticipated at design-time. Agents can mutually adjust individual plans to fit in with others so the multi-agent organisation is able to dynamically adapt to a changing environment. The meta-model and design approach is successfully demonstrated and validated using an implementation of a simulation system. In this demonstration system, agents in multiple organisations collaborate and coordinate to resolve a problem within an artificial simulation world.
-
ItemOptimizing projection in the situation calculus( 2018)Among the most frequent reasoning tasks in the situation calculus are projection queries that query the truth of conditions in a future state of affairs. However, in long running action sequences involving thousands or millions of independent actions, solving the projection problem is complex. Existing approaches require either syntactically rewriting queries through each action that has occurred via a mechanism called regression or producing and maintaining an updated representation of the knowledge base via progression. This latter approach is often infeasible, as updating a knowledge base without loss of relevant information is not possible for many domains. This thesis introduces a new technique which allows the length of the action sequences to be reduced by reordering independent actions and removing dominated actions; maintaining semantic equivalence with respect to the original action theory. This transformation allows for the removal of actions that are problematic with respect to progression, allowing for periodic update of the action theory to reflect the current state of affairs. We provide the logical framework for the general case and give specific methods for important classes of action theories. We also show how more expressive cases may be handled, such as the reordering of sensing actions in order to delay progression. We investigate mechanisms for deciding which actions should be removed or reordered to improve the efficiency via a guided search and introduce appropriate heuristics. The end result is a method that allows long-running situation calculus based agents to reason more efficiently about their current and future situations.
-
ItemOn the analysis of interaction between decision variables( 2017)Many real-world design and decision-making problems are characterized by the interactions between decision variables. In engineering optimization problems, the effects of one input variable on the performance measure may be influenced by one or several other input variables. In classification problems, one feature by itself may be irrelevant to the class label, however when combined with one or many feature(s), it may become highly relevant to the class label. Identifying variable interactions is important yet non-trivial. In this thesis, the overarching goals are (1) to identify and quantify variable interactions in a given optimization or classification problem and (2) to use this information to effectively solve the problem. The methodologies used to meet these goals are a combination of theoretical inquiry, computational modelling and experimental validation of the proposed methods. To identify and quantify variable interactions in a `Black-box' Continuous Optimization Problem (BCOP), a novel Exploratory Landscape Analysis (ELA) measure is proposed based on the Maximal Information Coefficient (MIC). MIC can identify a wide range of functional relationships with high levels of accuracy. Then the proposed ELA measure is embedded into an algorithm design framework to effectively solve a BCOP. The experimental results confirm the effectiveness of the proposed ELA measure. The high computational cost is the main limitation of the proposed ELA measure, especially in large-scale BCOPs. Therefore I propose an eXtended Differential Grouping (XDG) method, which can be used to identify variable interactions based on non-linearity detection. The XDG method decomposes a large-scale BCOP into several sub-problems considering both direct and indirect variable interactions. When XDG is embedded into a Cooperative Co-evolution framework to solve large-scale BCOPs, it generates high quality solution. To further improve the efficiency of problem decomposition, a Recursive Differential Grouping (RDG) method is proposed, which avoids the need to check the pairwise interactions between decision variables. RDG recursively examines the interaction between a selected decision variable and the remaining variables, placing all interacting decision variables into the same group. The efficiency of RDG is shown both theoretically and empirically. In the final stage of this thesis, I shift the focus from optimization problems to the closely related classification (more specifically feature selection) problems, by investigating the interactions between features to improve classification accuracy. I relax the assumptions made on the distribution of features and class labels, and propose a novel feature selection method which considers the Mutual Information (MI) between three features. To reduce the computational cost, the MI between three features is estimated from the pairwise MI between features. The experimental results confirm the effectiveness of the proposed method. In summary, the interactions between decision variables have been investigated in the optimization and classification domains. Novel methods have been proposed to improve the accuracy and efficiency of identifying variable interactions in a BCOP, large-scale BCOP or feature selection problem. I then have shown that this information can be used to guide the design of search techniques to effectively solve the problem.
-
ItemInterest-based negotiation in multi-agent systems( 2004)Software systems involving autonomous interacting software entities (or agents) present new challenges in computer science and software engineering. A particularly challenging problem is the engineering of various forms of interaction among agents. Interaction may be aimed at enabling agents to coordinate their activities, cooperate to reach common objectives, or exchange resources to better achieve their individual objectives. This thesis is concerned with negotiation: a process through which multiple self-interested agents can reach agreement over the exchange of scarce resources. In particular, I focus on settings where agents have limited or uncertain information, precluding them from making optimal individual decisions. I demonstrate that this form of bounded-rationality may lead agents to sub-optimal negotiation agreements. I argue that rational dialogue based on the exchange of arguments can enable agents to overcome this problem. Since agents make decisions based on particular underlying reasons, namely their interests, beliefs and planning knowledge, then rational dialogue over these reasons can enable agents to refine their individual decisions and consequently reach better agreements. I refer to this form of interaction as “interested-based negotiation.” (For complete abstract open document)
-
ItemArguments and actions: decoupling preference and planning through argumentation( 2011)Automated decision-making and planning is a capability that lays the foundation for the development of intelligent decision-support. These systems range from sophisticated multi-agent solutions for corporate decision-support, to decision recommendation for the general consumer. The ideas, algorithms, and tools developed within this thesis cater for this latter category - a class of approaches that includes online travel planners, smart environments, context-aware navigational aides, and personal shopping assistants. Operating on behalf of a human user, these tools are charged with the recommendation of a decision that best serves their interests - characterised by their preference over available choices. The mission of an automated decision-maker is to extract and use this knowledge in the selection of a decision. Across the range of problem-domain scenarios faced by a human decision-maker, the appropriate means by which their preference is communicated varies - from the quantitative to qualitative, logical to heuristic, and simple to complex. The capacity of these tools to select choices on the basis of such wide ranging classes of preference increases their utility as human decision aides. This thesis considers the decoupling of preference from the decision-making and planning algorithms that underly such systems. These algorithms operate on this preference as if it were an instance of an abstract type - supporting the use of general expressions of preference while abstracting away from its representational detail. Such algorithms can not only be reused across a range of decision-making problems faced by an agent or user, but cater for the diversity of human users on whose behalf decision-making is taking place. This thesis presents three key contributions within this domain. The existing body of work within the field of automated decision-making and planning with preference is critiqued, identifying the field of computational argumentation as a promising vehicle for the discovery of decoupled decision-making. The argumentation-based approach to decision-making allows preference to be captured by structures - structures that are manipulated by the decision-making process as abstract entities. This thesis develops a decoupled algorithm for the selection of choices on the basis of general mechanisms of choice comparison - a feat not achieved within existing work. Attention is then shifted from decision-making over single choices or actions to the problem of planning with preference. Algorithms are developed that chart a course of action for an agent or human user to follow in pursuit of their goals. This thesis focuses on a specific planning formalism - the GOLOG family of agent programming languages. High level instructions in the form of programs are interpreted to discover a sequence of actions for an agent or human user to perform. Two interpreters are devised for the discovery of preferred program executions - the first providing support for only one form of preference expression; the second presenting a decoupled approach to program interpretation with general preference. These interpreters go beyond the capabilities of existing works, with improved heuristic guidance in the form of a relaxed lookahead and support for decoupling through argumentation-based program interpretation.