Plánování a řešení problémů v decentralizovaném prostředí je klíčový problém v mnoha průmyslových aplikacích, počínaje výrobou, logistikou, virtuálními organizacemi a konče multi-robotickými systémy. Integrace procesu dekompozice úkolů, jejich alokace na agenty a lokálního plánování umožňuje využít metody plánování a alokace s důrazem na dostupnost zdrojů. Každý úkol lze obecně dekomponovat několika způsoby. Pro každou dekompozici existuje mnoho možných alokací a jednotliví agenti mohou vygenerovat rozdílné plány pro každou část úkolu. Otázku zvolení vhodné dekompozice pro daný úkol nelze snadno zodpovědět bez znalosti konkrétní alokace a vyhodnocení lokálních plánů. Jelikož počet možných kombinací značně stoupá s počtem agentů jakožto i s počtem možných dekompozic a alokací dostáváme se k netriviálnímu problému multi-agetního řešení problémů.
V této práci představujeme abstraktní architekturu multi-agentího solveru a odpovídající algoritmy zajišťující dekompozici úloh, jejich alokaci a delegaci. Architektura je založena na principech maximalizace sociálního užitku pomocí agentního vyjednávání o alokaci, delegaci a realokaci úkolů. Interakční mechanismy zaručují optimalizaci v globálním měřítku, přičemž jednotliví agenti používají lokální plánovací heuristiky a strategie. Práce také analyzuje vlastnosti této abstraktní architektury jako je výpočetní složitost nebo přípustnost použitých optimalizačních heuristik.
V další části představujeme reprezentaci plánů pomocí sociálních závazků, která je vhodná zejména pro flexibilní přeplánování a opravy plánů v dynamickém nedeterministickém prostředí. Nosnou myšlenkou je reprezentace distribuovaného hierarchického plánu pomocí sociálních závazků za použití formální teorie pro zachycení vzájemných relací mezi záměry a cíli spolupracujících agentů. Uvažování nad takovými závazky a alternativami jejich možného plnění či rušení přispívá v plánovacím procesu k tvorbě flexibilních a robustních plánů. V práci formálně definujeme a analyzujeme tři základní vyvazovací pravidla: (i) relaxaci, (ii) delegaci a (iii) úplné zrušení závazku. Koordinační a interakční proces mezi agenty je silně vázán na schopnost jednotlivých agentů inteligentně použít vyvazovací pravidla na základě konkrétních změn v prostředí. Ukazujeme, že správný výběr, nastavení a řazení vyvazovacích pravidel přispívá k robustnosti celkového řešení. Výše uvedenou abstraktní architekturu pro agentní řešení problémů jsme obohatili o možnost práce se sociálními závazky a diskutujeme možný vyvazovací model.
V závěru verifikujeme a vyhodnocujeme představené přístupy v simulovaném prostředí i na konkrétních příkladech z reálného světa. Experimentální ověření potvrzuje možnosti multi-agentího řešení problémů poskytnout kvalitní řešení, výkonnost, stabilitu a robustnost systému v komplexních scénářích. Abychom demonstrovali aplikovatelnost předložených přístupů v širokém spektru problémů reálného světa, předkládáme čtyři implementace abstraktní architektury pro konkrétní domény -- vehicle routing problémy, strategické plánování misí, multi-robotický průzkum okrajových bodů a plánování výroby.
Problem solving and planning in decentralized environments is a key technical challenge in numerous industrial applications, ranging from manufacturing, logistics, virtual enterprises to multi-robotics systems. The integration of the task refinement (decomposition), allocation and local planning enables to explore the planning and allocation possibilities taking into account the availability of resources. There may be several ways to decompose a task. For each such a decomposition various allocations exist and each agent can make different plans for each part of a decomposed task. The question of which decomposition is the best for a given task cannot be answered easily without allocation and local plans' evaluation. Since the number of combinations grows rapidly with the number of agents as well as the decomposition and allocation possibilities, it leads us to the non-trivial problem of multi-agent problem solving.
This work presents an abstract architecture of a multi-agent solver and a respective algorithm providing decomposition, task allocation and task delegation. The architecture is based on social welfare maximization using agent negotiation over task allocation, delegation and reallocation. The interaction mechanism ensures global optimization behavior while the individual agents apply local planning heuristics and strategies. Various features of the abstract architecture, such as computational complexity or admissibility of the underlying optimization heuristics, are analyzed.
Additionally, an approach to plan representation based on social commitments suitable for flexible replanning and plan revision purposes in dynamic non-deterministic environments is introduced. The key idea is in the representation of a distributed hierarchical plan by social commitments, as a theoretically studied formalism for representing mutual relations among intentions of collaborating agents. Reasoning about decommitment alternatives during the planning process contributes to flexibility and robustness of the resulting plan. We formally introduce and discuss three specific decommitment rules: (i) relaxation, (ii) delegation and (iii) full decommitment. The process of coordination and interaction between agents depends strongly on the ability of individual actors to perform intelligent decommitment upon specific changes in the environment. We argue that an appropriate selection, setting and preference ordering of decommitment rules contributes to robustness of the overall solution. The abstract problem solving architecture is extended for commitment allocation and the decommitment model is discussed. %The decommitment rules definition and their influence on the plan execution robustness and stability is also presented.
The approach was verified and evaluated in simulated environments and real case studies. The experimental validation confirms the ability of the multi-agent problem solver to provide high-quality solutions, performance, stability and robustness of the system in complex scenarios. Four instances of the abstract architecture implementations are given to demonstrate the applicability of the presented approaches in a wide variety of real world problem domains -- vehicle routing problems, strategic mission planning, multi-robot frontiers exploration and production planning.