Síntese automática de normas eficientes para sistemas multiagente

Abstract

A síntese de normas eficientes, um problema em aberto e de solução não trivial, consiste em determinar normas que evitem situações de conflitos ao passo que mantenham os objetivos do sistema alcançado. Contudo, sintetizar normas eficientes traz à tona uma série de desafios, como identificar corretamente as normas que mantêm um equilíbrio entre o controle que exercem e a autonomia dos agentes assim como lidar com um tempo particularmente alto para que a situação seja bem-sucedida. Para situar este problema, considere dois tipos de normas: normas muito específicas e muito gerais. Embora muitas normas específicas tendam a ser incapacitantes de evitar conflitos, dado que dão uma grande liberdade aos agentes para executarem suas ações, normas muito gerais tendem a inviabilizar o alcance dos objetivos do sistema, dado que regulam os agentes em excesso, o que pode impede a execução de ações adequadas para que os objetivos do sistema sejam alcançados. Neste sentido, para serem eficientes, as normas aplicáveis ??têm uma generalidade equilibrada não sendo, portanto, nem muito específicas nem muito gerais. Além disso, como o número de normas candidatas para regulares dos agentes pode ser grande, determinar quais normas possuem a generalidade balanceada pode ser uma tarefa custosa e que exige tempo. Para lidar com estes problemas, propomos: i) uma conceitualização formal para a síntese automática de normas eficientes; ii) uma integração entre a síntese de normas e a análise da alcançabilidade dos objetivos do sistema; iii) uma forma de considerar os conflitos do sistema na síntese de normas; iv) estratégias para estimar a generalidade das normas; v) estratégias para ordenar as normas; vi) estratégias para explorar espaços de busca; e vii) estratégias para reduzir a complexidade da síntese de normas eficientes. Isso nos permite organizar as normas, aproximadamente, das mais específicas para o mais geral e obter espaços de busca ordenados. Sobre tais espaços, aplicamos estratégias de exploração que se beneficiam da estrutura das ordenações para encontrar normas eficientes. Supondo que tais normas não estejam localizadas nos extremos das ordenações, podemos poder fazer parte do espaço de busca e economizar tempo e esforço computacional na síntese de normas eficientes. Também propomos um conjunto de algoritmos para a síntese de normas eficientes que são avaliadas em cenários diferentes. Para cada cenário, os algoritmos se organizam e exploram os espaços de busca de diferentes formas. Como principais resultados dos experimentos, verificamos que: i) certas estratégias para organizar e explorar o espaço de pesquisa são mais destacadas para a visão geral de normas eficientes ao aprimorar o desempenho da visão; ii) a análise da alcancebilidade dos objetivos do sistema auxilia a construir espaços de busca com normas melhor verificadas a comportamentos que observam de regulação e permitem que os agentes executem, pelo menos, uma sequência de ações que os levam aos objetivos do sistema; e iii) a análise da alcançabilidade dos objetivos do sistema auxilia a construir espaços de busca menores fazendo com que o tempo de busca por normas eficientes diminua.

Abstract: The synthesis of efficient norms, an open problem with a non-trivial solution, consists of determining norms that avoid conflict situations while maintaining the system goals reachable. However, synthesizing efficient norms brings up several challenges, such as correctly identifying norms that maintain a balance between the control they exert and the autonomy of agents, as well as dealing with a potentially high time to the synthesis be successful. To contextualize this problem, consider two types of norms: very specific and very general norms. While very specific norms tend to be incapable of avoiding conflicts, as they grant agents significant freedom to execute their actions, very general norms may impede the system goals to be reached, as they overregulate agents, which can prevent them from performing necessary actions for satisfying such goals. In this sense, to be efficient, norms need to have a balanced generality, neither being too specific nor too general. In addition, as the number of candidate norms for regulating agents can be large, determining which norms have a balanced generality can be a costly and time-consuming task. To address these problems, in this thesis we propose: i) a formal conceptualization for the automatic efficient norm synthesis; ii) an integration between norm synthesis and system goal reachability analysis; iii) a method to consider system conflicts in norm synthesis; iv) strategies for estimating the norms generality; v) strategies for ordering norms; vi) strategies for exploring the search space; and vii) strategies for reducing the complexity of efficient norm synthesis. Through this approach, we can organize the norms approximately from the most specific to the most general and obtain ordered search spaces. In these spaces, we can apply exploration strategies that benefit from the structure of the orderings to find efficient norms. Assuming that such norms are not located at the extremes of the orderings, we can prune part of the search space, saving time and computational effort in the synthesis of efficient norms. We also propose a set of algorithms for synthesizing efficient norms, which are evaluated in various scenarios. For each scenario, the algorithms organize and explore the search spaces in different ways. The main results of the experiments indicate that: i) certain strategies for organizing and exploring the search space enhance the synthesis performance of efficient norms; ii) the analysis of the system goals reachability aids in constructing search spaces with norms aligned to behaviors that need regulation and enable agents to execute, at least, a sequence of actions leading to the reachability of system goals; and iii) the analysis of the system goals reachability helps to build smaller search spaces, which may reduce the search time for efficient norms.