Swinburne
Browse

Distributed graph-based multi-agent planning

Download (1.23 MB)
thesis
posted on 2024-07-12, 17:39 authored by Jian Feng Zhang
From the Artificial Intelligence (AI) perspective, planning is the problem of selecting and organizing actions to accomplish given tasks. In many real world scenarios, a complex task is often beyond the capability of a single agent. It requires multiple agents to cooperate with each other to accomplish the task. Planning for such a task involves the selection and organization of actions belonging to multiple agents. Most existing approaches to solving such a multi-agent planning problem rely on the complete knowledge of the actions in the domain, which confronts them with difficulties in distributed, dynamic and complex environments where it is often impossible or undesirable to build up complete knowledge. We argue that such situations are happening more and more frequently. For example, with the fast growth of the Internet and emerging paradigms such as SOC (Service Oriented Computing), the Internet has become a global, dynamic and open e-business environment. Companies, organizations and entities are encouraged to build up temporary collaborations promptly to meet short-term objectives and exploit fast changing business opportunities. However, the brevity of the collaboration, the diversity of the participants and the dynamic nature of the environment, discourage them from revealing all actions to each other or to a third party, and prevent the complete knowledge from being built up. This thesis studies multi-agent planning. In particular, it investigates the feasibility of performing distributed multi-agent planning for a given task without the complete knowledge of the actions in the domain. The major contributions of the thesis are listed: A new distributed search space representation Dis-graph is proposed. This enables agents to cooperate in constructing a distributed search space in a distributed manner; A novel distributed multi-agent planning algorithm Dis-graph planning is proposed. This algorithm utilizes a Dis-graph as the search space, and enables agents to cooperate in planning for a given task in a distributed manner, without relying on the complete knowledge of the actions in the domain; A DisCSP (Distributed Constraint Satisfaction Problem) encoding of the Dis-graph is proposed. This enables agents to compile a Dis-graph into a DisCSP automatically, and search for a plan via solving the DisCSP in a distributed manner; A way of integrating non-functional requirements (i.e. Quality of Service requirements) into the Dis-graph planning framework is proposed. The consideration of Quality of Service (QoS) is seamlessly included in the search for the plan, without modifying the Dis-graph planning framework; A novel expansion-based distributed multi-agent replanning approach is proposed. This approach enables agents to cooperate in repairing a distributed plan in a distributed manner, without the reliance on either the complete knowledge of the plan or the complete knowledge of the actions in the domain.

History

Thesis type

  • Thesis (PhD)

Thesis note

A thesis submitted for the degree of Doctor of Philosophy, Swinburne University of Technology, 2009.

Copyright statement

Copyright © 2009 Jian Feng Zhang.

Supervisors

Ryszard Kowalczyk

Language

eng

Usage metrics

    Theses

    Categories

    No categories selected

    Keywords

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC