Choices that make you chnage your mind : a dynamic epistemic logic approach to the semantics of BDI agent programming languages

Abstract

As the notions of Agency and Multiagent System became important topics for the Computer Science and Artificial Intelligence communities, Agent Programming has been proposed as a paradigm for the development of computer systems. As such, in the last decade, we have seen the flourishing of the literature on Agent Programming with the proposal of several programming languages, e.g. AgentSpeak (RAO, 1996; BORDINI; HUBNER;WOOLDRIDGE, 2007), Jadex (POKAHR; BRAUBACH; LAMERSDORF, 2005), JACK (HOWDEN et al., 2001), 3APL/2APL (DASTANI; VAN RIEMSDIJK; MEYER, 2005; DASTANI, 2008), GOAL (HINDRIKS et al., 2001), among others. Agent Programming is a programming paradigm proposed by Shoham (1993) in which the minimal units are agents. An agent is an entity composed of mental attitudes, that describe the its internal state - such as its motivations and decisions - as well as its relation to the external world - its beliefs about the world, its obligations, etc. This programming paradigm stems from the work on Philosophy of Action and Artificial Intelligence concerning the notions of intentional action and formal models of agents’ mental states. As such, the meaning (and properties) of notions such as belief, desire, intention, etc. as studied in these disciplines are of central importance to the area. Particularly, we will concentrate in our work on agent programming languages influenced by the so-called BDI paradigm of agency, in which an agent is described by her beliefs, desires, intentions. While the engineering of such languages has been much discussed, the connections between the theoretical work on Philosophy and Artificial Intelligence and its implementations in programming languages are not so clearly understood yet. This distance between theory and practice has been acknowledged in the literature for agent programming languages and is commonly known as the “semantic gap”. Many authors have attempted to tackle this problem for different programming languages, as for the case of AgentSpeak (BORDINI; MOREIRA, 2004), GOAL (HINDRIKS; VAN DER HOEK, 2008), etc. In fact, Rao (1996, p. 44) states that “[t]he holy grail of BDI agent research is to show such a one-to-one correspondence with a reasonably useful and expressive language.” One crucial limitation in the previous attempts to connect agent programming languages and BDI logics, in our opinion, is that the connection is mainly established at the static level, i.e. they show how a given program state can be interpreted as a BDI mental state. It is not clear in these attempts, however, how the execution of the program may be understood as changes in the mental state of the agent. The reason for this, in our opinion, is that the formalisms employed to construct BDI logics are usually static, i.e. cannot represent actions and change, or can only represent ontic change, not mental change. The act of revising one’s beliefs or adopting a given desire are mental actions (or internal actions) and, as such, different from performing an action over the environment (an ontic or external action). This difference is well recognized in the literature on the semantics of agent programming languages (D’INVERNO et al., 1998; BORDINI; HUBNER; WOOLDRIDGE, 2007; MENEGUZZI; LUCK, 2009), but this difference is lost when translating their semantics into a BDI logic. We believe the main reason for that is a lack of expressibility in the formalisms used to model BDI reasoning. Dynamic Epistemic Logic, or DEL, is a family of dynamic modal logics to study information change and the dynamics of mental attitudes inspired by the Dutch School on the “dynamic turn” in Logic (VAN BENTHEM, 1996). This formalism stems from various approaches in the study of belief change and differs from previous studies, such as AGM Belief Revision, by shifting from extra-logical characterization of changes in the agents attitudes to their integration within the representation language. In the context of Dynamic Epistemic Logic, the Dynamic Preference Logic of Girard (2008) seems like an ideal candidate, having already been used to study diverse mental attitudes, such as Obligations (VAN BENTHEM; GROSSI; LIU, 2014), Beliefs (GIRARD; ROTT, 2014), Preferences (GIRARD, 2008), etc. We believe Dynamic Preference Logic to be the ideal semantic framework to construct a formal theory of BDI reasoning which can be used to specify an agent programming language semantics. The reason for that is that inside this logic we can faithfully represent the static state of a agent program, i.e. the agent’s mental state, as well as the changes in the state of the agent program by means of the agent’s reasoning, i.e. by means of her mental actions. As such, in this work we go further in closing the semantic gap between agent programs and agency theories and explore not only the static connections between program states and possible worlds models, but also how the program execution of a language based on common operations - such as addition/removal of information in the already mentioned bases - may be understood as semantic transformations in the models, as studied in Dynamic Logics. With this, we provide a set of operations for the implementation of agent programming languages which are semantically safe and we connect an agent program execution with the dynamic properties in the formal theory. Lastly, by these connections, we provide a framework to study the dynamics of different mental attitudes, such as beliefs, goals and intentions, and how to reproduce the desirable properties proposed in theories of Agency in a programming language semantics.

Dada a importância de agentes inteligentes e sistemas multiagentes na Ciência da Computação e na Inteligência Artificial, a programação orientada a agentes (AOP, do inglês Agent-oriented programming) emergiu como um novo paradigma para a criação de sistemas computacionais complexos. Assim, nas últimas décadas, houve um florescimento da literatura em programação orientada a agentes e, com isso, surgiram diversas linguages de programação seguindo tal paradigma, como AgentSpeak (RAO, 1996; BORDINI; HUBNER; WOOLDRIDGE, 2007), Jadex (POKAHR; BRAUBACH; LAMERSDORF, 2005), 3APL/2APL (DASTANI; VAN RIEMSDIJK; MEYER, 2005; DASTANI, 2008), GOAL (HINDRIKS et al., 2001), entre outras. Programação orientada a agentes é um paradigma de programação proposto por Shoham (1993) no qual os elementos mínimos de um programa são agentes. Shoham (1993) defende que agentes autônomos e sistemas multiagentes configuram-se como uma forma diferente de se organizar uma solução para um problema computacional, de forma que a construção de um sistema multiagente para a solução de um problema pode ser entendida como um paradgima de programação. Para entender tal paradigma, é necessário entender o conceito de agente. Agente, nesse contexto, é uma entidade computacional descrita por certos atributos - chamados de atitudes mentais - que descrevem o seu estado interno e sua relação com o ambiente externo. Atribuir a interpretação de atitudes mentais a tais atributos é válida, defende Shoham (1993), uma vez que esses atributos se comportem de forma semelhante as atitudes mentais usadas para descrever o comportamento humano e desde que sejam pragmaticamente justificáveis, i.e. úteis à solução do problema. Entender, portanto, o significado de termos como ’crença’, ’desejo’, ’intenção’, etc., assim como suas propriedades fundamentais, é de fundamental importância para estabelecer linguagens de programação orientadas a agentes. Nesse trabalho, vamos nos preocupar com um tipo específico de linguagens de programação orientadas a agentes, as chamadas linguagens BDI. Linguagens BDI são baseadas na teoria BDI da Filosofia da Ação em que o estado mental de um agente (e suas ações) é descrito por suas crenças, desejos e intenções. Enquanto a construção de sistemas baseados em agentes e linguagens de programação foram tópicos bastante discutidos na literatura, a conexão entre tais sistemas e linguagens com o trabalho teórico proveniente da Inteligência Artificial e da Filosofia da Ação ainda não está bem estabelecida. Essa distância entre a teoria e a prática da construção de sistemas é bem reconhecida na literatura relevante e comumente chamada de “gap semântico” (gap em inglês significa lacuna ou abertura e representa a distância entre os modelos teóricos e sua implementação em linguagens e sistemas). Muitos trabalhos tentaram atacar o problema do gap semântico para linguagens de programação específicas, como para as linguagens AgentSpeak (BORDINI; MOREIRA, 2004), GOAL (HINDRIKS; VAN DER HOEK, 2008), etc. De fato, Rao (1996, p. 44) afirma que “O cálice sagrado da pesquisa em agentes BDI é mostrar uma correspondência 1-a-1 com uma linguagem razoavelmente útil e expressiva” (tradução nossa)1 Uma limitação crucial, em nossa opinião, das tentativas passadas de estabeler uma conexão entre linguagens de programação orientadas a agentes e lógicas BDI é que elas se baseiam em estabelecer a interpretação de um programa somente no nível estático. De outra forma, dado um estado de um programa, tais trabalhos tentam estabelecer uma interpretação declarativa, i.e. baseada em lógica, do estado do programa respresentando assim o estado mental do agente. Não é claro, entretanto, como a execução do programa pode ser entendida enquanto mudanças no estado mental do agente. A razão para isso, nós acreditamos, está nos formalismos utilizados para especificar agentes BDI. De fato, as lógicas BDI propostas são, em sua maioria, estáticas ou incapazes de representar ações mentais. O ato de revisão uma crença, adotar um objetivo ou mudar de opinião são exemplos de ações mentais, i.e. ações que são executadas internarmente ao agente e afetando somente seu estado mental, sendo portanto não observáveis. Tais ações são, em nossa opinião, intrinsecamente diferentes de ações ônticas que consistem de comportamento observável e que possivelmente afeta o ambiente externo ao agente. Essa diferença é comumente reconhecida no estudo da semântica de linguagens de programação orientadas a agentes (BORDINI; HUBNER; WOOLDRIDGE, 2007; D’INVERNO et al., 1998; MENEGUZZI; LUCK, 2009), entretanto os formalismos disponíveis para se especificar raciocínio BDI, em nosso conhecimento, não provem recursos expressivos para codificar tal diferença. Nós acreditamos que, para atacar o gap semântico, precisamos de um ferramental semântico que permita a especificação de ações mentais, assim como ações ônticas. Lógicas Dinâmicas Epistêmicas (DEL, do inglês Dynamic Epistemic Logic) são uma família de lógicas modais dinâmicas largamente utilizadas para estudar os fenômenos de mudança do estado mental de agentes. Os trabalhos em DEL foram fortemente influenciados pela escola holandesa de lógica, com maior proponente Johna Van Benthem, e seu “desvio dinâmico” em lógica (dynamic turn em inglês) que propõe a utilização de lógicas dinâmicas para compreender ações de mudanças mentais (VAN BENTHEM, 1996). O formalismo das DEL deriva de diversas vertentes do estudo de mudança epistêmica, como o trabalho em teoria da Revisão de Crenças AGM (ALCHOURRÓN; GÄRDENFORS; MAKINSON, 1985), e Epistemologia Bayesiana (HÁJEK; HARTMANN, 2010). Tais lógicas adotam a abordagem, primeiro proposta por Segerberg (1999), de representar mudanças epistêmicas dentro da mesma linguagem utilizada para representar as noções de crença e conhecimento, diferente da abordagem extra-semântica do Revisão de Crenças a la AGM. No contexto das DEL, uma lógica nos parece particulamente interessante para o estudo de programação orientada a agentes: a Lógica Dinâmica de Preferências (DPL, do inglês Dynamic Preference Logic) de Girard (2008). DPL, também conhecida como lógica dinâmica de ordem, é uma lógica dinâmica para o estudo de preferências que possui grande expressibilidade para codificar diversas atiutudes mentais. De fato, tal lógica foi empregada para o estudo de obrigações (VAN BENTHEM; GROSSI; LIU, 2014), crenças (GIRARD; ROTT, 2014), preferências (GIRARD, 2008), etc. Tal lógica possui fortes ligações com raciocínio não-monotônico e com lógicas já propostas para o estudo de atitudes mentais na área de Teoria da Decisão (BOUTILIER, 1994b) Nós acreditamos que DPL constitui um candidato ideal para ser utilizado como ferramental semântico para se estudar atitudes mentais da teoria BDI por permitir grande flexibilidade para representação de tais atitudes, assim como por permitir a fácil representação de ações mentais como revisão de crenças, adoção de desejos, etc. Mais ainda, pelo trabalho de Liu (2011), sabemos que existem representações sintáticas dos modelos de tal lógica que podem ser utilizados para raciocinar sobre atitudes mentais, sendo assim candidatos naturais para serem utilizados como estruturas de dados para uma implementação semanticamente fundamentada de uma linguagem de programação orientada a agentes. Assim, nesse trabalho nós avançamos no problema de reduzir o gap semântico entre linguagens de programação orientadas a agentes e formalismos lógicos para especificar agentes BDI. Nós exploramos não somente como estabelecer as conexões entre as estruturas estáticas, i.e. estado de um programa e um modelo da lógica, mas também como as ações de raciocínio pelas quais se especifica a semântica formal de uma linguagem de programação orientada a agentes podem ser entendidas dentro da lógica como operadores dinâmicos que representam ações mentais do agente. Com essa conexão, nós provemos também um conjunto de operações que podem ser utilizadas para se implementar uma linguagem de programação orientada a agentes e que preservam a conexão entre os programas dessa linguagem e os modelos que representam o estado mental de um agente. Finalmente, com essas conexões, nós desenvolvemos um arcabouço para estudar a dinâmica de atitudes mentais, tais como crenças, desejos e inteções, e como reproduzir essas propriedades na semântica de linguagens de programação.