Universidade Federal da BahiaEscola Politecnica

Programa de Pos-Graduacao em EngenhariaEletrica

Dissertacao De Mestrado

Embarcando o Agente Autonomo

Concorrente em uma Rede de

Microcontroladores de um Robo Movel

Omnidirecional

Mestrando: Diego Stefano Fonseca Ferreira

Orientador: Prof. Dr. Augusto Cesar Pinto Loureiro da Costa

Salvador

Agosto - 2014

Resumo

Neste trabalho, uma rede heterogenea de microcontroladores e proposta para em-barcar o agente autonomo concorrente. A rede foi projetada para comportar osrequisitos de concorrencia do modelo cognitivo do supracitado agente. A arquite-tura do agente e composta por tres nıveis, a saber, o nıvel reativo, o nıvel instintivoe o nıvel cognitivo, que sao executados concorrentemente. O nıvel reativo foi embar-cado em um PSoC 5LP, e consistiu de comportamentos criados sobre um controladorcinematico. O nıvel instintivo e executado em um mbed, que recebe percepcoes e se-leciona comportamentos do nıvel reativo atraves de um barramento CAN. A selecaode comportamentos reativos e realizada por um sistema baseado em conhecimento(SBC) que utiliza logica de primeira ordem (LPO) e quadros como formalismos derepresentacao do conhecimento. O nıvel cognitivo, embarcado em um DNP 2486,recebe informacoes simbolicas do nıvel instintivo e envia para este ultimo metaslocais atraves de uma rede Ethernet. Tambem utiliza um SBC para implementaro seu processo decisorio, mas pode usar tanto LPO e quadros para representacaode conhecimento, como logica temporal proposicional (LTP). Experimentos com onıvel reativo isolado (utilizando um robo real), e com a rede de microcontroladorescompleta (em um ambiente simulado) validaram a arquitetura de hardware pro-posta. Uma placa de circuito impresso com a rede de microcontroladores tambem eapresentada.

Palavras Chave: Robotica movel, Navegacao de Robos, Agentes Autonomos,Sistemas Baseados em Conhecimento, Redes de Microcontroladores.

i

Abstract

In this paper, a microcontroller heterogeneous network is proposed to embed a con-current autonomous agent. The network was designed to fit the concurrency requi-rements of the cognitive model of the aforementioned agent. The architecture ofthe agent comprises three levels, namely, the reactive level, instinctive level and thecognitive level, which runs concurrently. The reactive level is embedded in a PSoC5LP, consisting of behaviours created over a embedded kinematic controller. Theinstinctive level runs in a ARM mbed, which receives perceptions from and sends theactive behaviour to the reactive level through a CAN bus. The behaviour selectionis executed by a knowledge-based system (KBS) that uses first-order logic (FOL)and frames as knowledge representation formalisms. And The cognitive level runson a DNP/2486 which, in turn, receives symbolic information from and sends newlocal goals to instinctive level through an Ethernet network. It also uses a KBS toimplement its reasoning mechanism, but it can use either FOL and frames or pro-positional temporal logic (PTL) as knowledge representation method. Experimentswith the reactive level isolated (using a real robot), and with the complete network(in a simulated environment) validated the proposed architecture. A printed circuitboard with the microcontrollers network is also presented.

Keywords: Mobile Robots, Robot Navigation, Autonomous Agents,Knowledge-Based Systems, Microcontrollers Network.

ii

Indice

Resumo i

Abstract ii

Indice iii

Lista de Figuras v

Lista de Tabelas vii

1 Introducao 1

2 Representacao de Conhecimento 42.1 Logica de Primeira Ordem (LPO) . . . . . . . . . . . . . . . . . . . . 4

2.1.1 Sintaxe da LPO . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.2 Semantica da LPO . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Logica Temporal Proposicional (LTP) . . . . . . . . . . . . . . . . . . 92.2.1 Sintaxe da LTP . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2.2 Semantica da LTP . . . . . . . . . . . . . . . . . . . . . . . . 122.2.3 O Algoritmo MetateM . . . . . . . . . . . . . . . . . . . . . 17

2.3 Quadros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4 Sistemas Baseados em Conhecimento e Sistemas Especialistas . . . . 22

2.4.1 Sistemas de Producao . . . . . . . . . . . . . . . . . . . . . . 222.4.2 Sistemas Baseados em Conhecimento e Sistemas Especialistas 24

2.5 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3 O Agente Autonomo Concorrente (AAC) 283.1 Modelo Generico para Agentes Cognitivos . . . . . . . . . . . . . . . 283.2 Arquitetura Cognitiva do AAC . . . . . . . . . . . . . . . . . . . . . 293.3 Arquitetura do AAC Embarcado . . . . . . . . . . . . . . . . . . . . 323.4 Representacao do Conhecimento no AAC . . . . . . . . . . . . . . . . 33

3.4.1 LPO e Quadros . . . . . . . . . . . . . . . . . . . . . . . . . . 333.4.2 LTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.5 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

iii

4 Arquitetura de Hardware 394.1 Visao Geral do Sistema Embarcado . . . . . . . . . . . . . . . . . . . 394.2 Protocolos de Comunicacao . . . . . . . . . . . . . . . . . . . . . . . 40

4.2.1 O Protocolo CAN . . . . . . . . . . . . . . . . . . . . . . . . . 404.2.2 O Protocolo Ethernet . . . . . . . . . . . . . . . . . . . . . . . 43

4.3 Nıvel Reativo: PSoC 5LP . . . . . . . . . . . . . . . . . . . . . . . . 444.3.1 O PSoC 5LP . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.3.2 O Sistema Operacional de Tempo Real . . . . . . . . . . . . . 454.3.3 Encapsulamento de Sistema de Controle no Nıvel Reativo . . . 46

4.4 Nıvel Instintivo: o mbed . . . . . . . . . . . . . . . . . . . . . . . . . 494.5 Nıvel Cognitivo: o DNP 2486 . . . . . . . . . . . . . . . . . . . . . . 524.6 Operacao do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.7 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5 Resultados 555.1 Nıvel Reativo: Controlador Cinematico . . . . . . . . . . . . . . . . . 55

5.1.1 Configuracao dos Experimentos . . . . . . . . . . . . . . . . . 555.1.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.2 Nıveis Reativo, Instintivo e Cognitivo: Planejamento . . . . . . . . . 585.2.1 Configuracao dos Experimentos . . . . . . . . . . . . . . . . . 585.2.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5.3 Placa de Circuito Impresso . . . . . . . . . . . . . . . . . . . . . . . . 625.4 Conclusao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

6 Conclusao 65

Referencias Bibliograficas 67

iv

Lista de Figuras

2.1 Exemplo de quadros (Bittencourt 2006). . . . . . . . . . . . . . . . . 22

2.2 Estrutura generica de um sistema de producao de regras. . . . . . . . 22

2.3 Formato Geral de um EMT. . . . . . . . . . . . . . . . . . . . . . . . 24

2.4 Exemplos de Elementos da Memoria de Trabalho. . . . . . . . . . . . 25

2.5 Estrutura de uma regra de producao logica: “n”, “m”e“k”sao interiospositivos quaisquer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.6 Exemplo de regra utilizado no Exemplo 2.4.3. . . . . . . . . . . . . . 26

3.1 O Modelo Generico de Agentes Cognitivos (Barbosa 2005). . . . . . . 29

3.2 Arquitetura do AAC (Costa e Bittencourt 1999). . . . . . . . . . . . 30

3.3 Nıvel reativo do AAC implementado no framework Expert-Coop++(da Costa et al. 2003). . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.4 Nıvel instintivo do AAC implementado no framework Expert-Coop++(da Costa et al. 2003). . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.5 Nıvel cognitivo do AAC implementado no framework Expert-Coop++(da Costa et al. 2003). . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.6 Nıvel reativo embarcado. . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.7 Nıvel instintivo embarcado. . . . . . . . . . . . . . . . . . . . . . . . 33

3.8 Nıvel cognitivo embarcado. . . . . . . . . . . . . . . . . . . . . . . . . 34

3.9 Formato de um fato simples (a) e um composto (b). . . . . . . . . . . 34

3.10 Exemplo de uma base de fatos. . . . . . . . . . . . . . . . . . . . . . 34

3.11 Formato de uma regra de producao. . . . . . . . . . . . . . . . . . . . 35

3.12 Exemplo de uma base de regras com 2 regras. . . . . . . . . . . . . . 35

3.13 Formato dos quadros na linguagem do AAC. . . . . . . . . . . . . . . 35

3.14 Sintaxe completa na forma de Backu-Naur (de Santana Junior eCosta 2007). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.15 Diagrama do SBC do AAC (de Santana Junior e Costa 2007). . . . 36

3.16 Inferencia com LTP. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.1 Diagrama de Blocos da rede de Microcontroladores. . . . . . . . . . . 40

4.2 Camadas OSI do protocolo CAN e os elementos que as implementam. 40

4.3 Codificacao diferencial dos sinais no protocolo CAN (Ranjith 2013). . 41

4.4 Barramento CAN (Barrenscheen 1998). . . . . . . . . . . . . . . . . . 41

v

4.5 Barramento CAN sem transceivers (Barrenscheen 1998). . . . . . . . 424.6 Quadro de dados do protocolo CAN (Ranjith 2013). . . . . . . . . . . 424.7 Forma de onda correspondente a sequencia de bits “0011110” sob a

codificacao Manchester (IEEE 2012). . . . . . . . . . . . . . . . . . . 434.8 Estrutura de um quadro Ethernet (Toulson e Wilmshurst 2012). . . . 434.9 Arquitetura do PSoC 5LP. . . . . . . . . . . . . . . . . . . . . . . . . 454.10 Diagrama de estados das tarefas no FreeRTOS. . . . . . . . . . . . . 464.11 Sistemas de coordenadas no AxeBot para modelagem cinematica (Bitencourt

et al. 2008). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.12 Diagrama de blocos do controlador cinematico. . . . . . . . . . . . . . 494.13 ARM mbed (Toulson e Wilmshurst 2012). . . . . . . . . . . . . . . . 504.14 Diagrama de blocos do mbed (Toulson e Wilmshurst 2012). . . . . . . 514.15 DIL/NetPC 2486. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.16 Diagrama de classes do sistema baseado em conhecimento de nıvel

cognitivo com LTP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.17 Diagrama de sequencia esperado do sistema. . . . . . . . . . . . . . . 54

5.1 Resultado para estabilizacao ponto a ponto. . . . . . . . . . . . . . . 565.2 Resultados para rastreamento de trajetoria. . . . . . . . . . . . . . . 575.3 Diagrama de circuito da rede de microcontroladores. . . . . . . . . . . 585.4 Diagrama da Rede Ethernet. . . . . . . . . . . . . . . . . . . . . . . . 595.5 Configuracao dos experimentos de planejamento de movimento. . . . 595.6 Segmentacao do espaco (a) para a posicao relativa da meta e (b) para

as localizacoes relativas dos obstaculos. . . . . . . . . . . . . . . . . . 605.7 Base de regras para o nıvel cognitivo utilizando LPO. . . . . . . . . . 605.8 Resultado para planejamento utilizando LPO. . . . . . . . . . . . . . 615.9 Resultado para navegacao com LTP: em verde o ponto inicial, e em

amarelo as metas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.10 Placa de circuito impresso da rede de microcontroladores. . . . . . . . 635.11 Esquematico do barramento CAN. . . . . . . . . . . . . . . . . . . . 64

vi

Lista de Tabelas

2.1 Sintaxe da LPO na forma de Backu-Naur. . . . . . . . . . . . . . . . 62.2 Sintaxe da LTP na forma de Backu-Naur. . . . . . . . . . . . . . . . 122.3 Modelo em LTP simplificado. . . . . . . . . . . . . . . . . . . . . . . 122.4 Representacao de um modelo em LTP. . . . . . . . . . . . . . . . . . 132.5 Representacao da semantica do operador de inıcio. . . . . . . . . . . . 142.6 Representacao da semantica do operador de proximo instante. . . . . 142.7 Representacao da semantica do operador de eventualidade. . . . . . . 152.8 Representacao da semantica do operador de invariancia. . . . . . . . . 152.9 Representacao da semantica do operador “ate que”. . . . . . . . . . . 162.10 Representacao da semantica do operador “ate que”. . . . . . . . . . . 162.11 Modelo gerado pela execucao de uma sentenca de proximo instante. . 182.12 Exemplo de regras de producao de um sistema de Post . . . . . . . . 232.13 Exemplo de Execucao de um Sistema de Post. . . . . . . . . . . . . . 23

4.1 Principais caracterısticas do PSoC 5LP . . . . . . . . . . . . . . . . 444.2 Tarefas implementadas. . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.1 Regras de inıcio e de eventualidade . . . . . . . . . . . . . . . . . . . 625.2 Regras de proximo instante . . . . . . . . . . . . . . . . . . . . . . . 62

vii

Lista de Siglas

AAC Agente Autonomo Concorrente

API Application Programming Interface

BC Base de Conhecimento

CAN Controller Area Network

CPU Central Processing Unit

CRC Cyclic Redundancy Check

CSMA/CD Carrier Sense Multiple Access with Collision Detection

DNP DIL-Net PC

EMT Elemento da Memoria de Trabalho

FNS Forma Normal Separada

LLC Logical Link Control

LPC Logica Proposicional Classica

LPO Logica de Primeira Ordem

LTL Logica Temporal Linear

LTP Logica Temporal Proposicional

MAC Medium Access Control

MI Motor de Inferencia

viii

MT Memoria de Trabalho

PC Personal Computer

PSoC Programmable System-on-a-Chip

RTOS Real-Time Operating System

SBC Sistema Baseado em Conhecimento

SE Sistema Especialista

SO Sistema Operacional

SoC System-on-a-Chip

SOTR Sistema Operacional de Tempo Real

UART Universal Asynchronous Receiver/Transmitter

ix

Capıtulo 1

Introducao

O homem sempre sonhou com a possibilidade de criacao uma maquina que pudesseexecutar seus afazeres de maneira completamente autonoma. Esse sonho deu origemao ramo multidisciplinar conhecido como robotica, que se iniciou com maquinas decomando numerico e bracos mecanicos teleoperados, e desenvolveu-se a ponto decontemplar maquinas moveis completamente autonomas nos dias atuais.

O grau de autonomia conferida a um robo varia de acordo com a complexidadeda tarefa que o mesmo deve executar. Em uma linha de montagem industrial, porexemplo, o comportamento do robo pode ser implementado por uma maquina deestados discretos, que determinaria exatamente a(s) acao(oes) disponıvel(is) paraexecutar em um dado estado. Para tarefas mais complexas, o mecanismo de tomadade decisao utilizado deve ser mais robusto, atribuindo ao robo versatilidade parasuficiente para agir eficazmente mesmo em circunstancias nao previstas inicialmente.Neste utlimo caso, a entidade que encarna o mecanismo de acao inteligente e o agenteautonomo.

Existem diversas arquiteturas de agentes autonomos, oriundas principalmente deestudos da psicologia cognitiva. Essa derivacao e explicitada por Murphy (2000),onde o autor afirma que o paradigma reativo de construcao de agentes autonomossurgiu exatamente de ideias provenientes da etologia, ciencia que estuda o compor-tamento de animais.

Essa influencia da psicologia cognitiva no estudo de agentes autonomos e refor-cada em (Oudeyer 2010), e ainda a correlacao inversa e estudada, isto e, como arobotica cognitiva esta ajudando compreender aspectos comportamentais e cogniti-vos dos animais. Neste trabalho, exemplos paradigmaticos sao apresentados, como amodelagem do comportamento de insetos, a auto-organizacao de linguagens em so-ciedades roboticas, uso de robos de forma terapeutica para criancas com problemasde desenvolvimento, entre outros.

Em (M. Asada 2001) ve-se o desenvolvimento de um modelo de cognicao pararobos moveis humanoides. Neste caso, os autores utilizam a RoboCup como plata-forma de desenvolvimento. Um agente autonomo para robos e proposto em (E. Aguirre2000), cuja arquitetura utiliza logica nebulosa para coordenar seus comportamen-

1

tos, e com isso consegue navegar livre de colisoes em um ambiente com obstaculos,alcancando uma meta estabelecida.

Bittencourt (1997) propoe um modelo generico de agentes cognitivos. Esse mo-delo consiste em uma arquitetura cognitiva geral utilizada para modelar agentesde qualquer natureza. O modelo generico de agentes cognitivos e utilizado comobase por Costa e Bittencourt (1999) para a proposta de uma arquitetura de agenteautonomo chamada Agente Autonomo Concorrente (AAC), utilizado na RoboCup.A RoboCup, competicao internacional de futebol de robos, e uma plataforma bas-tante utilizada para a realizacao de pesquisas em robotica movel, conforme visto em(Kitano et al. 1997) e em (Kitano et al. 1998), onde os autores enfatizam a multi-disciplinaridade do futebol de robos e os desafios enfrentados na implementacao deum AAI robotico para este escopo de aplicacao.

Mas o AAC possui uma arquitetura cognitiva composta por nıveis decisorios quedevem executar concomitantemente. Isto implica em uma importante restricao sobreo hardware computacional onde o AAC sera executado: uma arquitetura computa-cional centrada em um unico nucleo computacional nao e suficiente. Alem disso,o AAC utiliza originalmente como metodo de representacao de conhecimento a lo-gica de primeira ordem (LPO). Mas a adicao de capacidade de raciocınio temporaltraz vantagens importantes, principalmente no que concerne ao planejamento emambientes dinamicos, como e o caso do futebol de robos.

Assim, de modo a possibilitar a um robo movel a execucao autonoma de tarefas, asua inteligencia deve ser implementada por meio de um agente autonomo em conso-nancia com as demandas de hardware do mesmo. O objetivo precıpuo deste trabalhoe o projeto de uma rede de microcontroladores para o robo movel omnidirecionalAxeBot que possibilite o embarque do Agente Autonomo Concorrente (AAC) e queseja flexıvel o suficiente para a utilzacao de mais de uma forma de representacao deconhecimento.

Para lograr o supramencionado objetivo geral, os seguintes objetivos especıficossao estabelecidos:

• desenvolver um controlador cinematico para a movimentacao do robo;

• projeto de uma rede de microcontroladores com nos dedicados para cada nıveldo AAC; e

• desenvolver uma estrategia de planejamento de movimento utilizando logicatemporal.

Este trabalho justifica-se, pois, pela geracao de uma arquitetura de hardware dedi-cada para o AAC, permitindo-o ser utilizado em aplicacoes de robotica movel, alemde estender o seu arcabouco de metodos de raciocınio automatico com a utilizacaode logica temporal.

E verdade tambem que conceber uma arquitetura de hardware multiprocessadafuncional e de grande utilidade academica nao so para o embarque do AAC, mas

2

tambem para fornecer uma plataforma experimental para implementacao dos maisdiversos algoritmos de inteligencia artificial, arquiteturas cognitivas e controle, ori-entados a robotica movel, gozando da concorrencia e rica instrumentacao dessa ar-quitetura.

O restante deste trabalho divide-se da seguinte forma:

• o Capıtulo 2 fornece uma fundamentacao teorica sobre os metodos de repre-sentacao de conhecimento utilizados no AAC;

• o AAC e descrito no Capıtulo 3, onde se explicita como os metodos expostosno Capıtulo 2 sao utilizados no AAC;

• no Capıtulo 4 a arquiteura de hardware proposta e descrita: cada no computa-cional utilizado e descrito, assim como os protocolos de comunicacao utilizadospara conecta-los;

• os resultados de experimentos sao expostos no Capıtulo 5; e

• o Capıtulo 6 apresenta uma conclusao, onde constam propostas para trabalhosfuturos.

3

Capıtulo 2

Representacao de Conhecimento

De acordo com a definicao de Barr e Feigenbaum (1981), citados por Bittencourt(1990), chama-se de representacao de conhecimento o conjunto de metodos formaiscompreendendo estruturas de dados e relacoes interpretativas que, se utilizadasapropriadamente em um programa, levariam-no a apresentar um comportamentointeligente. Bittencourt (2006) cita Furbach et al. (1984) para afirmar que umarepresentacao e composta por tres itens, a saber:

• o mundo externo;

• a representacao propriamente dita; e

• a relacao entre os dois itens acima.

O mundo externo e a representacao devem possuir operadores que possibilitem amanipulacao dos seus elementos, e a relacao entre estes corpos de conhecimento,como o autor os denomina, compoe a semantica da representacao.

Neste capıtulo, serao abordados os metodos de representacao de conhecimentoutilizados pelo AAC. A primeira representacao abordada sera a Logica de PrimeiraOrdem (LPO). Em seguida, a Logica Proposicional Temporal (LTP) e descrita, comuma subsecao dedicada ao algoritmo MetateM para execucao formulas em LTP.Depois, o formalismo de representacao de quadros sera apresentado. Finalmente, ossistemas especialistas e sistemas baseados em conhecimento serao abordados.

2.1 Logica de Primeira Ordem (LPO)

A Logica de Primeira Ordem (LPO), ou Logica de Predicados estende a LogicaProposicional Classica (LPC) com a introducao de objetos e relacoes, permitindoum maior poder de expressao. Assim, o compromisso ontologico (relacao entre alinguagem logica e a estrutura da realidade que a linguagem pretende representar)da LPO passa a ser com objetos e a existencia de relacoes entre eles, enquanto aLPC se compromete ontologicamente apenas com a existencia de fatos (Russel eNorvig 2004).

4

2.1.1 Sintaxe da LPO

A sintaxe da LPO engloba os operadores da LPC,“∧” (e), “∨” (ou), “¬” (negacao),“⇒” (implicacao) e “⇔” (equivalencia), alem das constantes “V” (verdadeiro) e “F”(falso). A LPO tambem conta com variaveis e com os quantificadores universal“∀” e existencial “∃”. Por fim, a sintaxe da LPO inclui sımbolos para representarobjetos, relacoes entre objetos e funcoes (Bittencourt 2006, Fitting 1996, Russel eNorvig 2004).

Uma linguagem LPO L pode entao ser definida como consistindo de uma tuplados seguintes conjuntos (Bittencourt 2006, Fitting 1996):

• C, um conjunto finito ou contavel de sımbolos de constante;

• P , um conjunto finito ou contavel de sımbolos de predicado (ou demrelacao),utilizados para representar relacoes entre os objetos. Todo P ∈ P possui umnumero inteiro associado, chamado aridade, que determina a quantidade deelementos na relacao;

• F , um conjunto finito ou contavel de sımbolos de funcoes. Todos os F ∈ Ftambem possuem uma aridade, aqui determinando o numero de argumentosde F ; e

• V , um conjunto de variaveis.

Exemplo 2.1.1. Seja uma linguagem Lparentesco composta pelos conjuntos:

• Cparentesco = {Paulo,Maria,Pedro};

• Pparentesco = {Conjuge,Filho,Avo} (todos com aridade dois); e

• Fparentesco = {Mae} (de aridade um).

As seguintes sentencas poderiam ser escritas:

• Filho(Paulo,Maria) ∧ Filho(Paulo,Pedro);

• Conjuge(Maria,Pedro).

• Avo(Mae(Maria),Paulo)⇔ Filho(Paulo,Maria)

A despeito do fato de as sentencas guardarem alguma semelhanca com a linguagemnatural e fazerem sentido, nenhuma relacao foi feita com a realidade, e portanto,formalmente, ainda nao e possıvel dizer se sao verdadeiras ou falsas.

Outro conceito importante que emerge das definicoes ate aqui apresentadas e anocao de termo. Segundo Fitting (1996), o conjunto de termos de uma linguagemlogica L e definido recursivamente como o menor subconjunto de L tal que:

• todo v ∈ V e um termo de L;

5

• todo C ∈ C e um termo de L; e

• dado um F ∈ F com aridade n e um conjunto de termos t1, t2, . . . , tn ∈ L,F (t1, t2, . . . , tn) e um termo em L (se um termo nao contem variaveis, ele edito fechado; caso contrario, ele e aberto).

Uma sentenca na LPO que possui apenas um predicado de aridade qualquer ouque enunciam a igualdade entre dois termos e chamada de sentenca atomica, e e aunidade formadora de qualquer sentenca em LPO. A sintaxe da LPO e resumida naTabela 2.1 (Russel e Norvig 2004).

Tabela 2.1: Sintaxe da LPO na forma de Backu-Naur.

Sentenca → SentencaAtomica | SentencaComplexaSentencaAtomica → Predicado | Predicado( Termo, ... ) | Termo = Termo

SentencaComplexa → ( Sentenca ) | [ Sentenca ]| ¬ Sentenca| Sentenca OperadorBinario Sentenca| Quantificador Variavel, ... Sentenca

Termo → Funcao( Termo, ... )| Constante| Variavel

OperadorBinario → ∨ | ∧ | ⇒ | ⇔Quantificador → ∀ | ∃

Constante → C ∈ CPredicado → P ∈ P

Funcao → F ∈ FVariavel → v ∈ V

Quando uma sentenca em LPO contem termos abertos aplica-se um mapeamentoσ : V 7→ T , onde T denota o conjunto de termos, que substitui uma ou maisvariaveis da sentenca por termos. Este mapeamento e chamado de substituicao.Denota-se a aplicacao de uma substituicao σ sobre uma sentenca S por Sσ. Adespeito do fato de ter como domınio o conjunto de variaveis, considera-se possı-vel aplicar uma substituicao a um sımbolo de constante, tendo como resultado oproprio sımbolo, isto e, para c ∈ C, cσ = c. Para uma funcao f de aridade n,[f(t1, t2, ..., tn)]σ = f(t1σ, t2σ, ..., tnσ). Uma outra notacao permite especificar expli-citamente as substituicoes realizadas. Por exemplo, se uma substituicao σ substituias variaveis x1, x2, ..., xn pelos termos t1, t2, ..., tn, respectivamente, em uma sen-tenca S, denota-se Sσ alternativamente por S{x1/t1, x2/t2, ..., x3/t3}. Quando umasubstituicao σ deve manter inalterada uma determinada variavel x, escreve-se talsubstituicao como σx (Fitting 1996, Bittencourt 2006).

Para a aplicacao de substituicoes a sentencas quaisquer algumas propriedadesdevem ser obedecidas. Sao elas:

6

• sejam P ∈ P um predicado de aridade n e t1, t2, ..., tn um conjunto de termos,entao [P (t1, t2, ...tn)]σ = P (t1σ, t2σ, ...tnσ);

• para os sımbolos “V ” e “F”, V σ = V e Fσ = F ;

• dada uma sentenca S, [¬S]σ = ¬Sσ;

• denotando por “�” um dos operadores binarios “∨”, “∧”, “⇒”, “⇔”, se S1 e S2

sao sentencas, entao [S1 � S2]σ = S1σ � S2σ.

• para uma sentenca S, [(∀x)S]σ = [(∀x)(Sσx)];

• para uma sentenca S, [(∃x)S]σ = [(∃x)(Sσx)].

Exemplo 2.1.2. Considerando a sentenca S = Conjuge(x, y), a aplicacao de umasubstituicao σ = {x/Pedro, y/Maria} nesta expressao (escrita Sσ) produz a sentencaatomica Conjuge(Pedro,Maria).

2.1.2 Semantica da LPO

A semantica de uma linguagem logica corresponde ao estabelecimento de dire-trizes para a atribuicao de valores-verdade (verdadeiro ou falso) para expressoesnessa linguagem de acordo com a sua relacao com a realidade. Com este fim, os ele-mentos relevantes da realidade devem ser representados dentro do arcabouco formalda linguagem. A estrututura formal que possibilita esta inclusao na LPO e o modelo.Um modelo consiste de um conjunto de objetos do mundo real e um mapeamentoque relaciona os elementos da liguagem logica desenvolvida com estes objetos. Estemapeamento recebe o nome de interpretacao e o conjunto de objeto, de domınio(Russel e Norvig 2004).

Formalmente, de acordo com Fitting (1996), um modelo e uma tuplaM = 〈D, I〉,onde D e um conjunto nao-vazio representando o domınio de M e I uma interpre-tacao, que realiza os seguintes mapeamentos:

• todo c ∈ C em um cI ∈ D;

• todo f ∈ F com aridade n em um mapeamento fI : Dn 7→ D; e

• todo p ∈ P com aridade n em uma relacao pI ⊆ Dn.

Apos o estabelecimento do coneceito de modelo, Fitting (1996) prossegue com aconstrucao da semantica da LPO atraves da definicao de atribuicoes, que sao mape-amentos do tipo A : V 7→ D, do conjunto de variaveis sobre o domınio do modelo.Cada atribuicao A possui um mapeamento B associado chamado de variante-x deA, que executa a atribuicao denotada por A mantendo a variavel x inalterada. Oautor ressalta que as definicoes de atribuicao e substituicao sao similares, poremgeralmente nao identicas, exceto no caso em que o domınio D e exatamente o con-junto de termos fechados de L, caso em que o modelo M e denominado modelo de

7

Herbrand. Aqui se considerara este ultimo caso, e portanto, no procedimento dedeterminacao de valores-verdade a seguir, substituicoes serao utilizadas no lugar dasatribuicoes originalmente utilizadas pelo autor.

Assim, se M = 〈D, I〉 e um modelo de Herbrand da linguagem L = 〈C,P ,F ,V〉,e σ e uma substituicao, entao a atribuicao de valores verdadeiro ou falso parauma sentenca (Sσ)I e realizada de acordo com o seguinte (Fitting 1996):

• para as constantes “V ” e “F”, tem-se, respectivamente, (V σ)I = verdadeiroe (Fσ)I = falso;

• sejam P ∈ P e t1, t2, ..., tn termos de L, {[P (t1, t2, ..., tn)]σ}I = verdadeirose e somente se 〈(t1σ)I , (t2σ)I , ..., (tnσ)I〉 ∈ P I ;

• se S e uma sentenca, [¬(Sσ)]I = ¬(Sσ)I ;

• se S1 e S2 sao sentencas e “�” representa qualquer operador binario, [(S1 �S2)σ]I = (S1σ)I � (S2σ)I ;

• [(∀x)(Sσ)]I = verdadeiro se e somente se (Sσx)I = verdadeiro para todo

σx em M;

• [(∃x)(Sσ)]I = verdadeiro se e somente se (Sσx)I = verdadeiro para algum

σx em M;

Equivalentemente, dados um modelo M, uma sentenca S em LPO e uma subs-tituicao σ, pode-se definir um mapeamento da dupla 〈M, Sσ〉 sobre o conjunto{verdadeiro, falso} chamado de consequencia logica, e escrito como na Equacao(2.1). Esta equacao (lida “S e consequencia logica de M” ou ainda “M modela S”)representa uma outra forma de escrever (Sσ)I .

M |= S (2.1)

Exemplo 2.1.3. Continuando com o Exemplo 2.1.1, onde se definiu a linguagemLparentesco, agora ja se dispoe de recursos para avaliar o valor das sentencas apre-sentadas naquele exemplo. E importante observar que, pela definicao recursiva dostermos, a presenca de um sımbolo de funcao gera um domınio infinito. Considere-seum modelo de Herbrand M que consiste de um domınio

D = Cparentesco ∪ {Mae(c) | c ∈ Cparentesco} ∪ {Mae(Mae(c)) | c ∈ Cparentesco} ∪ . . . ,

e de uma intrepretacao I que produz os seguintes conjuntos:

• ConjugeI = {(Pedro,Maria), (Maria, Pedro)};

• FilhoI = {(Paulo, Pedro), (Paulo,Maria), (Pedro,Mae(Pedro)),(Mae(Pedro),Mae(Mae(Pedro))), . . . , (Maria,Mae(Maria)),(Mae(Maria),Mae(Mae(Maria))), . . .};

8

• AvoI = {(Mae(Maria), Paulo), (Mae(Pedro), Paulo),(Mae(Mae(Maria)),Maria), . . . , (Mae(Mae(Pedro)), P edro)}.

Assim a sentenca

Avo(Mae(Maria),Paulo)⇔ Filho(Paulo,Maria)

e verdadeira, pois (Mae(Maria),Paulo) ∈ AvoI , o que faz o lado esquerdo da equi-valencia ser verdadeiro, e (Paulo,Maria) ∈ FilhoI fazendo o lado direito tambemverdadeiro, portanto o resultado da operacao bicondicional e verdadeiro.

Dadas duas sentencas diferentes tais que pelo menos uma possui uma variavel,chama-se de unificacao o procedimento utilizado para encontrar uma substituicaoque, quando aplicada a ambas, as torne logicamente identicas. Esta substituicao, porsua vez, e denominada unificadora das duas sentencas. A unificacao pode tambemfalhar, caso nao haja uma substituicao que torne as sentencas logicamente identicas.Isso pode ocorrer devido a uma nomeacao inadequada de variaveis, conforme oExemplo 2.1.4 ilustra. Para evitar esta ultima ocasiao deve-se realizar um processode padronizacao de variaveis, que renomeia variaveis antes da aplicacao da unificacaode modo que tenham um nome unico (Fitting 1996, Russel e Norvig 2004).

Exemplo 2.1.4. Utilizando a notacao de Russel e Norvig (2004), tem-se

UNIFICAR(Filho(Paulo, x),Filho(y,Pedro)) = {x/Maria, y/Paulo}

Caso as variaveis da expressao acima tivessem o mesmo nome, teria-se

UNIFICAR(Filho(Paulo, x),Filho(x,Pedro)) = falha,

pois nao ha uma substituicao que atribua um elemento do domınio a x e unifique assentencas.

2.2 Logica Temporal Proposicional (LTP)

A Logica Temporal Proposicional (LTP) e tambem uma extensao a LPC. O com-promisso ontologico da LTP e com os fatos que sao verdadeiros em instantes detempo tomados relativamente ao tempo atual.

A LTP tem sua origem no trabalho de Pnueli (1977), quando este apresentou umsistema formal de raciocınio temporal aplicado a verificacao de programas. Estesistema formal foi chamado de Logica Temporal Linear (LTL). Segundo o autor,esta e uma abordagem unificada, uma vez que pode ser aplicada tanto a verifica-cao de programas sequenciais, quanto a de programas paralelos. E para lograr talunificacao, Pnueli introduz duas definicoes:

• Invariancia: utilizada para expressar propriedades dos programas que se man-tem validas durante toda a execucao.

9

• Eventualidade: definicao mais importante, segundo o proprio autor, a even-tualidade representa uma implicacao temporal, isto e, uma dada situacao Aassegura que eventualmente uma outra situacao B ira ocorrer.

No trabalho de Gabbay et al. (1980) a LTP foi proposta como uma forma propo-sicional da LTL sobre modelos em tempo discreto, contando com os operadores deproximo instante “X” (que permite expressar o que e ou nao verdadeiro no proximoinstante) e “ate que”“U” (que possibilita escrever expressoes do tipo, “a propriedadeA e verdadeira ate que B torne-se verdadeira”) (Konur 2010).

Esta secao se dedicara a descricao da LTP seguindo o formato da secao ante-rior: primeiro a sintaxe da LTP sera definida, e entao a semantica. Finalmente,o algoritmo MetateM sera apresentado, fornecendo as diretrizes para a execucaode formulas em LTP. O restante da secao utilzou como referencias os trabalhos deMichael Fisher (Fisher 2011), (Fisher 1996) e (Fisher 2006). Para evitar citacoesrepetitivas ao longo do texto, estas foram omitidas.

2.2.1 Sintaxe da LTP

A sintaxe da LTP contem os operadores da LPC (“∧”, “∨”, “¬”, “⇒” e “⇔”)e as constantes “V ” e “F ”. Em adicao a estes, operadores temporiais estendem aexpressividade da LPC, incorporando o tempo na estrutura da linguagem. Estesoperadores temporais sao:

• o operador “inıcio”;

• os operadores unarios de proximo instante “ e”, de invariancia “�” e de even-tualidade “♦”; e

• os operadores binarios “U” e “W”.

Um conjunto de sımbolos proposicionais P determina o alfabeto disponıvel para acriacao de sentencas proposicionais temporais.

Para estabelecer fatos conhecidos no instante inicial (isto e, no tempo t = 0),utiliza-se o operador “inıcio”.

Exemplo 2.2.1. Tomando como exemplo um caso em que as sentencas de LTP aserem desenvolvidas devem descrever as relacoes temporais entre os dias da semana,o conjunto de sımbolos proposicionais e formado por {segunda-feira, terca-feira,quarta-feira, quinta-feira, sexta-feira, sabado, domingo}. O operador de inıcio podeser utilizado nesse contexto para estabelecer um dia inicial a ser considerado norestante da analise. Por exemplo, se o dia inicial e segunda-feira, a sentenca emLTP correspondente e mostrada na Equacao (2.2).

inıcio⇒ segunda-feira (2.2)

10

O operador de proximo instante (“ e”) e utilizado para se expressar algo sobreo proximo instante de tempo. A base temporal nao e determinada na sintaxe dalinguagem, isto e, o operador pode se referir tanto ao proximo segundo, como aoproximo ano, dependendo do problema.

Exemplo 2.2.2. A expressao“amanha sera domingo”e escrita utilizando o operadorde proximo instante conforme a sentenca

edomingo

Exemplo 2.2.3. Pode-se estender o exemplo anterior para ilustrar a criacao deregras em LTP. A sentenca “se hoje e sabado entao amanha e domingo” pode serexpressa em LTP como na sentenca abaixo:

sabado⇒ edomingo

A invariancia mantem na LTP a sua utilidade original de representar fatos queconservarao um estado logico ao longo de todos os instantes futuros.

Exemplo 2.2.4. Utilizando como base o Exemplo (2.2.3), gera-se a Equacao (2.3),que expressa a sentenca “sempre que hoje for sabado, amanha sera domingo”.

�(sabado⇒ edomingo) (2.3)

O operador de eventualidade, conforme mencionado no inıcio desta secao, e tam-bem um operador unario. Ele e utilizado para expressar situacoes que irao certa-mente ocorrer em algum instante futuro, mas nao se especifica esse instante.

Exemplo 2.2.5. Expressa-se “sempre que hoje for quinta-feira entao eventualmentesera domingo” em LTP como na Equacao (2.4).

�(quinta-feira⇒ ♦domingo) (2.4)

Para completar a descricao da sintaxe da LTP, restam os dois operadores binarios“U” (ate que) e“W” (a menos que). O operador“U” e utilizado quando uma situacaoe verdadeira ate que uma outra ocorra. O operador “W” difere sutilmente do “U”:o “a menos que” e aplicado em casos onde nao e garantido que o segundo operandovenha a ser tornar verdadeiro. Assim, “W” pode ser utilizado para substituir “U”,mas a recıproca nao e valida.

Exemplo 2.2.6. A expressao “hoje e sabado ate que seja domingo”, por exemplo,e escrita com este operador conforme a Equacao (2.5).

sabado U domingo (2.5)

Um resumo da sintaxe da LTP e mostrado na Tabela 2.2.

11

Tabela 2.2: Sintaxe da LTP na forma de Backu-Naur.

Sımbolo → Elemento de um conjunto de sımbolos proposicionais.Sentenca → ( Sentenca ) | [ Sentenca ]

| V | F | inıcio | Sımbolo| OperadorUnario Sentenca| Sentenca OperadorBinario Sentenca

OperadorUnario → ¬ | � | e | ♦OperadorBinario → ∨ | ∧ | ⇒ | ⇔ | U | W

2.2.2 Semantica da LTP

Assim como na LPO, a semantica na LTP tambem depende do conceito de mo-delo. Um modelo em LTP e dado por uma sequencia de mundos, indexados porinstantes discretos, em cada um dos quais um determinado conjunto de sımbolosproposicionais (subconjunto de P) e verdadeiro. A Tabela 2.3 ilustra esta definicao.Nesta tabela ve-se que no instante i− 1, os sımbolos p, s, t e w sao verdadeiros. Noinstante i, apenas s e w sao verdadeiros, e em i+ 1 nenhum sımbolo e verdadeiro.

Tabela 2.3: Modelo em LTP simplificado.

Indice Temporal · · · i− 1 i i+ 1 · · ·Sımbolos Verdadeiros · · · p, s, t, w s, w · · ·

Formalmente, um modeloM consiste de uma tripla, como a mostrada na Equacao(2.6), onde S denota o conjunto de ındices temporais, R uma relacao de acessibili-dade temporal que realize a serializacao de S e π uma aplicacao de S sobre 2P.

M = 〈S,R, π〉 (2.6)

Uma estrutura deste tipo e chamada Estrutura de Kripke. A relacao π : S 7→ 2P

deve ser definida para sentencas em LTP de modo a associar um ındice temporal dei ∈ S a um subconjunto de P se, e somente se, este subconjunto for inteiramentecomposto por sımbolos verdadeiros no tempo i. Assim, para a definicao da semanticadas sentencas em LTP, este mapeamento deve ser definido para cada tipo de sentencapresente na Tabela 2.2.

Conforme se verificou no desenvolvimento da sintaxe da LTP, os operadores aquidefinidos referem-se apenas ao futuro. Portanto, o conjunto S e dado como o con-junto dos numeros naturais, e a relacao de serializacao R em S deve ser tal que osındices temporais sejam serializados em ordem crecente. Todavia, por simplicidade,a relacao R e omitida da expressao do modelo, e este e dado, entao, pela Equacao(2.7).

M = 〈N, π〉 (2.7)

12

Uma visualizacao dessa concepcao mais formal de um modelo e mostrada naTabela 2.4.

Tabela 2.4: Representacao de um modelo em LTP.

· · · → i− 1 → i → i+ 1 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

↓π(i+ 1)↓

· · ·· · · {p, s, t, w} {s, w} {} · · ·

A atribuicao efetiva de valores-verdade a sentencas da LTP ocorre entao atravesde um mapeamento similiar ao definido na Equacao (2.1) para sentencas da LPO,mas dessa vez o mapeamento e de uma tripla sobre o conjunto {verdadeiro, falso},isso porque agora um ındice temporal deve ser considerado. Assim, dado um modeloM = 〈N, π〉, um instante i e uma sentenca da LTP, o mapeamento

|=: 〈M, i, S〉 7→ {verdadeiro, falso}

e escrito como na Equacao (2.8).

〈M, i〉 |= S (2.8)

O restante desta subsecao sera dedicado a construir a semantica das expressoesda Tabela 2.2.

Sentencas Atomicas

Sentencas atomicas em LTP sao sentencas compostas por apenas um sımboloproposicional. A semantica de uma sentenca atomica p ∈ P e dada pela Equacao(2.9).

〈M, i〉 |= p se, e somente se, p ∈ π(i) (2.9)

Sentencas com Operadores Classicos

Sejam S1 e S2 duas sentencas da LTP. A semantica de sentencas com operadoresclassicos e dada na Equacao (2.10) (onde “sse” e uma abreviacao de “se, e somentese”).

〈M, i〉 |= ¬S1 sse 〈M, i〉 2 S1

〈M, i〉 |= S1 ∧ S2 sse 〈M, i〉 |= S1 e 〈M, i〉 |= S2

〈M, i〉 |= S1 ∨ S2 sse 〈M, i〉 |= S1 ou 〈M, i〉 |= S2

〈M, i〉 |= S1 ⇒ S2 sse se 〈M, i〉 |= S1 entao 〈M, i〉 |= S2

〈M, i〉 |= S1 ⇔ S2 sse 〈M, i〉 |= S1 sse 〈M, i〉 |= S2

(2.10)

13

Sentencas com Operadores Temporais

Para sentencas com operadores temporais, a atribuicao de valores-verdade e reali-zada atraves da manipulacao do ındice temporal de acordo com a funcao do operadortemporal, seguido da verificacao, no instante resultante, de se a sentenca e ou naoconsequencia logica do modelo. A seguir, a semantica de cada operador temporalsera apresentada e ilustrada.

• Operador de Inıcio (“inıcio”)

Em qualquer modelo, o operador “inıcio” e satisfeito apenas no marco zero,conforme a Equacao (2.11).

〈M, i〉 |= inıcio sse i = 0 (2.11)

A Tabela 2.5 ilustra o exposto acima.

Tabela 2.5: Representacao da semantica do operador de inıcio.

inıcio⇒ φ · · ·0 → 1 → 2 → 3 → 4 → 5 → · · ·↓

π(0)↓

↓π(1)↓

↓π(2)↓

↓π(3)↓

↓π(4)↓

↓π(5)↓

· · ·{φ} {} {} {} {} {} · · ·

• Operador de Proximo Instante (“ e”)Uma sentenca “ eS” e verdadeira em um modelo M se, e somente se, ela forconsequencia logica do modelo no proximo instante. Isso esta formalmenterepresentado na Equacao (2.12) e ilustrado na Tabela 2.6.

〈M, i〉 |= eS sse 〈M, i+ 1〉 |= S (2.12)

Tabela 2.6: Representacao da semantica do operador de proximo instante.

· · · eφ · · ·· · · → i− 1 → i → i+ 1 → i+ 2 → i+ 3 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

↓π(i+ 1)↓

↓π(i+ 2)↓

↓π(i+ 3)↓

· · ·· · · {} {} {φ} {} {} · · ·

• Operador de Eventualidade (“♦”)

Uma eventualidade representa um indeterminismo sobre em que instante detempo o seu operando sera satisfeito. Ela representa uma restricao: a sentenca

14

do seu unico argumento sera satisfeita em algum momento do futuro (Tabela2.7). A Equacao (2.13) representa este indeterminismo atraves do operador“∃”.

〈M, i〉 |= ♦S sse, existe j ∈ N tal que (j ≥ i) ∧ 〈M, j〉 |= S (2.13)

Tabela 2.7: Representacao da semantica do operador de eventualidade.

· · · ♦φ · · ·· · · → i− 1 → i → · · · → i+ j → i+ j + 1 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

· · · ↓π(i+ j)↓

↓π(i+ j + 1)

↓· · ·

· · · {} {} · · · {φ} {} · · ·

Quando a desigualdade da Equacao (2.13) e estrita, denota-se o operador deeventualidade por ♦+, e a sua semantica e levemente alterada, produzindo aEquacao (2.14).

〈M, i〉 |= ♦+S sse, existe j ∈ N tal que (j > i) ∧ 〈M, j〉 |= S (2.14)

• Operador de Invariancia (“�”)

A Equacao (2.15) estabelece a semantica do operador de invariancia. Empalavras, a expressao “�S” e consequencia logica do modelo M no instantei se, e somente se, “S” for consequencia logica de M para todos os instantesposteriores a i (inclusive) (Tabela 2.8).

〈M, i〉 |= �S sse, para todo j ∈ N, (j ≥ i) ∧ 〈M, j〉 |= S (2.15)

Tabela 2.8: Representacao da semantica do operador de invariancia.

· · · �φ · · ·· · · → i− 1 → i → i+ 1 → i+ 2 → i+ 3 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

↓π(i+ 1)↓

↓π(i+ 2)↓

↓π(i+ 3)↓

· · ·· · · {} {φ} {φ} {φ} {φ} · · ·

De maneira similar ao operador de eventualidade, o operador de invarianciatambem possui uma variante para a utilizacao de uma desigualdade estritana Equacao 2.15. Esta variante e denotada por “�+”, e e dada pela Equacao(2.16).

〈M, i〉 |= �+S sse, para todo j ∈ N, (j > i) ∧ 〈M, j〉 |= S (2.16)

15

• Operador “Ate Que” (“U”)

Se em um dado modelo certa sentenca “S1” e verdadeira ate que uma outrasentenca “S2” se torne verdadeira, fazendo a primeira deixar de se-lo e assimse mantenha (Tabela 2.9), entao a expressao 〈M, i〉 |= S1US2 e consequencialogica do modelo (ver Equacao (2.17)).

〈M, i〉 |= S1US2 sse, (existe j ∈ N tal que j ≥ i ∧ 〈M, j〉 |= S2∧(para todo k ∈ N, se i ≤ k < j entao 〈M, k〉 |= S1 )

(2.17)

Tabela 2.9: Representacao da semantica do operador “ate que”.

· · · φ U ψ · · ·· · · → i− 1 → i → i+ 1 → i+ 2 → i+ 3 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

↓π(i+ 1)↓

↓π(i+ 2)↓

↓π(i+ 3)↓

· · ·· · · {} {φ} {φ} {ψ} {} · · ·

• Operador “A Menos Que” (“W”)

Muito proximamente relacionado ao operador “U”, o operador “W” tem suasemantica mostrada na Equacao (2.18) em termos deste operador.

〈M, i〉 |= S1WS2 sse, (〈M, i〉 |= S1US2 ∨ �S1) (2.18)

A Tabela 2.10 ilustra dois casos possıveis para o operador “a menos que”: umem que a expressao do seu segundo argumento nunca se torna verdadeira eoutro em que isso ocorre (caso em que a semantica e identica a do operador“U”).

Tabela 2.10: Representacao da semantica do operador “ate que”.

· · · φW ψ · · ·· · · → i− 1 → i → i+ 1 → i+ 2 → i+ 3 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

↓π(i+ 1)↓

↓π(i+ 2)↓

↓π(i+ 3)↓

· · ·· · · {} {φ} {φ} {φ} {φ} · · ·· · · φW ψ · · ·· · · → i− 1 → i → i+ 1 → i+ 2 → i+ 3 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

↓π(i+ 1)↓

↓π(i+ 2)↓

↓π(i+ 3)↓

· · ·· · · {} {φ} {φ} {ψ} {} · · ·

16

2.2.3 O Algoritmo MetateM

O algoritmo MetateM fornece um procedimento para a execucao de uma sen-tenca em LTP. A execucao de sentencas em LTP corresponde ao processo de geracaode um modelo, isto e, geracao de uma sequencia de conjuntos de sentencas propo-sicionais indexados por um ındice temporal discreto. Este processo de construcaoutiliza a abordagem de futuro imperativo, que consiste na construcao iterativa apartir do estado inicial.

Forma Normal Separada (FNS)

A Forma Normal Separada (FNS) e uma representacao de uma sentenca complexada LTP que consiste de uma conjuncao invariante de varias formulas mais simples.A FNS e escrita conforme a sentenca da Equacao 2.19.

�∧i

Ri (2.19)

Cada Ri e chamado de regra e possui um dos formatos a seguir:

start⇒r∨b=1

lb (regra de inıcio);

g∧a=1

ka ⇒ e r∨b=1

lb (regra de proximo instante);

g∧a=1

ka ⇒ ♦l (regra de eventualidade).

Uma sentenca na FNS e apresentada, por questoes de clareza, com as suas regraslistadas sequencialmente. Assim, a sentenca na FNS �(R1 ∧ . . . ∧Rn) e escrita:

R1

· · ·Rn.

Encadeamento Adiante: Regras de Estado Inicial

O MetateM utiliza um mecanismo de encadeamento adiante para executar umasentenca em LTP: se o conjunto de sımbolos verdadeiros no instante atual tornarverdadeira a sentenca do lado esquerdo da implicacao de alguma regra Ri da Equacao(2.19), entao a sentenca do lado direito desta regra e executada.

O procedimento continua, aplicando uma estrategia passo-a-passo, a partir doestado inicial, para a construcao do modelo. Assim, dada uma sentenca da LTPescrita na FNP, o primeiro passo e avaliar qual e o estado inicial do modelo, isto e,a partir das regras de inıcio da sentenca definir o que e verdadeiro no intante inicial.

17

Uma vez definido o estado inicial, o encadeamento e iniciado: todas as premissasdas regras restantes (de proximo instante e de enventualidade) que sao consequenciaslogicas do modelo no instante inicial tem suas consequencias executadas.

Encadeamento Adiante: Regras de Proximo Instante

Seja uma regra de proximo instante dada por

P ⇒ eC.Considerando que o ındice do tempo atual e i, se 〈M, i〉 |= P , entao 〈M, i〉 |= eC,o que, de acordo com a semantica do operador “ e”, equivale a 〈M, i + 1〉 |= C. Omodelo resultante e mostrado na Tabela 2.11.

Tabela 2.11: Modelo gerado pela execucao de uma sentenca de proximo instante.

· · · → i− 1 → i → i+ 1 → i+ 2 → i+ 3 → · · ·· · · ↓

π(i− 1)↓

↓π(i)↓

↓π(i+ 1)↓

↓π(i+ 2)↓

↓π(i+ 3)↓

· · ·· · · {} {P} {C} {} {} · · ·· · · P ⇒ eC · · ·

Exemplo 2.2.7. Seja a sentenca da LTP na FNS

inıcio⇒ domingo

domingo⇒ esegunda-feira

segunda-feira⇒ eterca-feira.

A execucao desta sentenca produz o estado inicial composto apenas pelo sımbolodomingo. Com isso, inicia-se o encadeamento. Tem-se que

〈M, 0〉 |= domingo,

logo〈M, 1〉 |= segunda-feira.

Esta ultima expressao, por sua vez, implica em

〈M, 2〉 |= terca-feira.

Encadeamento Adiante: Regras de Eventualidade

Um ponto crucial do algoritmo MetateM e o tratamento de regras de eventu-alidade. A estrategia adotada e uma vez que a premissa de uma regra de even-tualidade e satisfeita, a enventualidade na sua consequencia tambem devera se-lo

18

tao logo quanto possıvel. Isto e, dada uma regra P ⇒ ♦C e um modelo 〈N, π〉, seP ∈ π(i), C devera ser adicionado a π(t) no primeiro t ≥ i em que ¬C /∈ π(t). OExemplo 2.2.8, a seguir, demonstra a estrategia do MetateM para a execucao deeventualidades.

Exemplo 2.2.8. Sejam um modelo 〈N, π〉 e as regras a seguir:

inıcio⇒ domingo

inıcio⇒ ¬segunda-feira

inıcio⇒ ¬terca-feira

domingo⇒ ♦segunda-feira

domingo⇒ ♦terca-feira

domingo⇒ e¬terca-feira.

No tempo t = 0, tem-se

π(0) = {domingo,¬segunda-feira,¬terca-feira},

segundo as regras de inıcio. Assim, ainda em t = 0 as tres regras seguintes tem suaspremissas satisfeitas (pelo sımbolo domingo). As regras de eventualidade estabe-lecem que eventualmente os sımbolos segunda-feira e terca-feira serao verdadeiros.Mas em t = 0, tem-se as restricoes ¬segunda-feira e ¬terca-feira, logo as eventuali-dades nao podem ser imediatamente satisfeitas. Devido a regra de proximo instantedomingo⇒ e¬terca-feira, em t = 1, a restricao ¬terca-feira e mantida, mas a restri-cao sobre segunda-feira nao e, possibilitando a satisfacao de uma das eventualidades.Portanto:

π(1) = {segunda-feira,¬terca-feira}.

Por fim, em t = 2, a restricao sobre terca-feira nao e mais mantida (nenhuma regrapropaga a negacao ¬terca-feira), possibilitando a satisfacao da ultima eventualidade:

π(2) = {terca-feira}. (2.20)

Verificacao de Ciclo

Durante a execucao de fomulas em LTP pode ocorrer que, a partir de algumi ≥ 0, tenha-se sempre π(i) = π(i+ T ), onde T e um inteiro positivo. Isso significaque a execucao entrou em um ciclo. Ciclos nao sao necessariamente indesejaveis:eles podem fazer parte da execucao. Em geral, ciclos que impedem a satisfacaode eventualidades sao considerados indesejaveis, enquanto que ciclos que em algumponto satisfazem todas as eventualidades sao considerados como parte da execucao,ou desejaveis.

19

Retrocesso

Conforme se ve nas regras de inıcio e proximo instante da FNS na Equacao (2.19),estas podem conter disjuncoes em seus respectivos lados direitos (consequentes).Estas disjuncoes representam escolhas que devem ser feitas ao longo da execucaode uma formula. Assim, ao encontrar uma disjuncao no lado direito de uma regra,escolhe-se um dos disjuntos para adicionar ao conjunto de sımbolos verdadeiros doinstante correspondente. Mas os demais disjuntos sao guardados, pois se a escolhainicial conduzir a alguma inconsistencia, deve-se retroceder ao ponto da escolha eescolher outro disjunto. Se todas as escolhas falharem, significa que as regras saoinconsistentes.

Pseudo-Codigo do MetateM

O pseudo-codigo do MetateM e mostrado no Algoritmo 1. Neste algoritmoaplicase a seguinte simbologia:

• E e o conjunto de regras de eventualidade;

• P o conjunto de regras de proximo instante;

• I o conjunto de regras de inıcio;

• Si denota o conjunto de sımbolos verdadeiros em i; e

• Ei denota o conjunto de eventualidade nao-satisfeitas ate i.

Considera-se tambem que as eventualidades nao podem ser satisfeitas imediata-mente, isto e, utiliza-se a eventualidade estrita, representada pelo sımbolo “♦+”.

2.3 Quadros

Minsky (1974) propos um metodo de representacao de conhecimento baseado emestruturas de dados cujos nos mantinham entre si relacoes e informacoes que ajuda-vam a decidir como e quando explorar tais relacoes. Essas estruturas de dados foramdenominadas quadros, e foram utilizados pelo autor como descritores de situacoesestereotıpicas.

Exemplo 2.3.1. Conforme o proprio Minsky em um trabalho posterior (Minsky1984), um exemplo de situacao estereotıpica seria estar em um certo quarto ou umcerto tipo de festa: a situacao e inicialmente representada por um quadro generico,estereotıpico, que possui caracterısticas comuns a todos os tipos de quartos ou festas,mas a medida que as percepcoes vao sendo adquiridas, o quadro e atualizado paradescrever aquela situacao especıfica (estar em um quarto especıfico ou em um tipode festa especıfico).

20

Algoritmo 1 Algoritmo MetateM.Entrada: I, um conjunto de regras de inıcio;Entrada: P, um conjunto de regras de proximo instante;Entrada: E, um conjunto de regras de eventualidade;

1: funcao MetateM(I,P,E)2: S0 ← {F | (inıcio⇒ F ) ∈ I}3: Ei ← {}4: enquanto verdadeiro faca5: C ← {G | (P ⇒ eG) ∈ P ∧ P ∈ Si}6: Ei+1 ← Ei ∪ {H | (Q⇒ ♦+H) ∈ E ∧Q ∈ Si}7: para cada V ∈ Ei+1 faca8: se V ∧ C e consistente entao9: C ← C ∧ V

10: remove V de Ei+1

11: fim se12: fim para13: Si+1 ← escolha de atribuicao consistente com C14: se Si+1 ≡ {} ou ∧Nk=0 (V ∈ Ei+k) entao15: Retrocede ate escolha anterior16: fim se17: fim enquanto18: fim funcao

Segundo Bittencourt (2006), a estrutura dos quadros e formada por campos querecebem preenchedores (do ingles, “fillers”), que sao simplesmente valores que saoutilizados para descrever o objeto representado pelo quadro. Os valores dos quadrostambem possuem algumas propriedades, denominadas facetas, que sao usadas paradeterminar dados default, ou de excecao, o tipo de dados esperado e informacoespara calcular o valor do atributo. Adicionalmente, os valores dos quadros podemreceber outros quadros, gerando uma rede de dependencias.

Exemplo 2.3.2. Bittencourt (2006) da um exemplo de um quadro“Sala”que possuiuma relacao de heranca com o quadro “Comodo”. O autor apresenta os quadros esuas relacoes de uma forma grafica, que e apresentada aqui na Figura 2.1. Nafigura, o quadro e referido por sua denominacao original em ingles: “frame”. Ocampo super-frame e onde se indica o quadro de onde se herdaram propriedades,estabelecendo um relacionamento do tipo “e-um”; nesse exemplo, uma “Sala” e um“Comodo”. Assim, a partir do quadro “Sala” um procedimento de inferencia podededuzir o seu formato e altura, por exemplo. Informacoes na coluna “Se-necessario”estabelecem diretrizes para o calculo de valores de atributos.

Hayes (1979) ressalta que a utilizacao de quadros, alem da utilidade represen-tacional (a que o autor se refere como “metafısica”), possui tambem importancia

21

Figura 2.1: Exemplo de quadros (Bittencourt 2006).

pratica (“heurıstica” ou “de implementacao”, nas palavras do autor), uma vez quea representacao atraves de quadros facilitia o armazenamento e a recuperacao doconhecimento em um sistema computacional por ja possuir uma estrutura adequadaa este fim.

2.4 Sistemas Baseados em Conhecimento e Siste-

mas Especialistas

2.4.1 Sistemas de Producao

Os Sistemas de Producao sao sistemas que representam o conhecimento por meiode um conjunto de regras chamadas regras de producao. Os sistemas de producaoiniciaram-se com Post (1943), que propos um sistema consistindo de regras de mo-dificacao sintatica sobre uma memoria de trabalho (MT) composta de uma cadeiasde caracteres. Um interpretador era responsavel pela modificacao da memoria detrabalho de acordo com as regras de modificacao. A estrutura basica de sistemas deproducao e ilustrada na Figura 2.2 (Bittencourt 2006).

Figura 2.2: Estrutura generica de um sistema de producao de regras.

22

Exemplo 2.4.1. Para exemplificar a execucao de um sistema de producao de Post,sejam uma MT composta pela sequencia de caracteres “123” e as regras de modifi-cacao sintatica mostradas na Tabela 2.121. Os caracteres “-”, “•” e “*” representam,respectivamente, um caractere nulo, um caractere de fim de sequencia e um caractereespecial.

Tabela 2.12: Exemplo de regras de producao de um sistema de Post

Indice da Regra Regra

1 ∗ i j → j ∗ i2 ∗ i→ i ∗3 ∗ • → - •4 -→ ∗

Estas regras propoem modificacoes sintaticas em cadeias de caracteres. O inter-pretador e o elemento reponsavel pela realizacao das alteracoes, atuando da seguinteforma: se o padrao do lado esquerdo de uma regra e encontrado na memoria de tra-balho, entao o trecho da memoria de trabalho que correspondeu aquele padrao emodificado para corresponder agora ao lado direito da regra. A Tabela 2.13 mostraalgumas etapas da execucao do interpretador.

Tabela 2.13: Exemplo de Execucao de um Sistema de Post.

Regra Utilizadapelo Interpretador

Padrao do Lado EsquerdoCorresponde na

Memoria de Trabalho

Memoria de TrabalhoResultante

1: ∗ i j → j ∗ i Nao 123•2: ∗ i→ i ∗ Nao 123•3: ∗ • → - • Nao 123•4: -→ ∗ Sim ∗123•1: ∗ i j → j ∗ i Sim 2 ∗ 13•1: ∗ i j → j ∗ i Sim 23 ∗ 1•1: ∗ i j → j ∗ i Nao 23 ∗ 1•2: ∗ i→ i ∗ Sim 231 ∗ •1: ∗ i j → j ∗ i Nao 231 ∗ •2: ∗ i→ i ∗ Nao 231 ∗ •3: ∗ • → - • Sim 231•

1Exemplo extraıdo de http://www1.se.cuhk.edu.hk/ seem5750/Lecture 2.pdf; Acessado a10/06/2014, as 9:25

23

2.4.2 Sistemas Baseados em Conhecimento e Sistemas Es-pecialistas

Utilizando a estrutura funcional dos sistemas de Post, os sistemas de producaoganham generalidade quando passam a utilizar um metodo de representacao deconhecimento como linguagem formal para a criacao da sua base de regras e da suaMT. Nesse caso, segundo Bittencourt (2006), tem-se um Sistema Especialista (SE).Segundo o autor, um SE tem o proposito de mimetizar o atuacao de um especialistahumano em um domınio bastante especıfico. A base de regras e a MT compoem abase de conhecimento (BC) do SE e o interpretador e substituıdo por um Motor deInferencia (MI). Uma linguagem formal tıpica para representacao de conhecimentoem SE e a LPO. As regras consistem, nesse caso, de clausulas definidas da LPO que,segundo Russel e Norvig (2004), sao sentencas implicativas do tipo Condicao ⇒Acao. Assim, as premissas (ou condicoes) das regras devem ser comparadas com aMT a fim de decidir se a MT deve ser alterada de acordo com as consequencias daregra. Portanto, o interpretador agora funciona como um mecanismo de inferencialogica. Esse processo de inferencia e realizado em um ciclo do MI, que consiste detres etapas (Brachman e Levesque 2004):

• reconhecer: encontrar dentre as regras aquelas cujas premissas sao satisfeitaspela MT (gerando o conjunto de conflitos);

• resolver conflitos: escolher uma regra do conjunto de conflitos;

• agir: realizar as alteracoes na memoria de trabalho de acordo com a consequen-cia da regra selecionada.

Segundo Brachman e Levesque (2004), os Elementos da Memoria de Trabalho(EMT) de um SE consiste de tuplas contendo o tipo do elemento, seus atributos eos valores destes atributos. O formato geral de um EMT e dado na Figura 2.3, ondetipo, atributoi e valori, com 1 ≤ i ≤ n, sao sentencas atomicas de LPO.

Figura 2.3: Formato Geral de um EMT.

O autor ainda complementa afirmando que este formato equivale a sentenca com-plexa de LPO

∃x [tipo(x) ∧ atributo1(x) = valor1 ∧ . . . ∧ atributo1(x) = valor1],

com tipo sendo um predicado unario, os atributos sendo funcoes unarias e os valoressendo objetos.

O formato de EMT apresentado e util para ilustrar a estrutura generica de umEMT, similar a uma estrutura de dados utilizada em programacao de computadores.Mas diferentes implementacoes de SEs podem utilizar uma linguagem diferente paraexpressar esta estrutura.

24

Exemplo 2.4.2. Exemplos de EMT sao mostrados na Figura 2.4.

Figura 2.4: Exemplos de Elementos da Memoria de Trabalho.

Ainda conforme Brachman e Levesque (2004), a estrutura de uma regra da BC deum SE e aquela da Figura 2.5. A premissa das regras e mostrada nesta figura comosendo formada por uma conjuncao de elementos com estruturas que se assemelhambastante aquela dos EMT. A unica diferenca esta no fato de que aos atributos agorasao associadas especificacoes ao inves de valores. As especificacoes estabelecem asrestricoes que os atributos correspondentes nos EMT devem obedecer para que apremissa da regra seja satisfeita e a mesma possa ser incluıda no conjunto de conflito.

Figura 2.5: Estrutura de uma regra de producao logica: “n”, “m” e “k” sao interiospositivos quaisquer.

As especificacoes podem consistir de uma sentenca atomica, uma variavel, umaexpressao (escrita entre colchetes), um teste (uma lista de operadores relacionaise valores escrito entre chaves) ou de uma conjuncao de especificacoes. Conformeja foi mencionado anteriormente, o MI, na etapa de reconhecimento, pesquisa apremissa de cada regra na MT, testando se ha correspondencia com algum EMT.Esta correspondencia ocorre quando ha algum EMT com o mesmo tipo da premissa,e se os atributos desse EMT obedecem as restricoes impostas pelas especificacoes dapremissa em questao.

Supondo que houve uma correspondencia de tipo entre uma (ou parte de uma)premissa e um EMT, a verificacao prossegue de acordo com a natureza da especifi-cacao:

• se uma especificacao consiste de uma sentenca atomica ou de uma expressao,uma comparacao de igualdade e realizada com os atributos correspondentesdo EMT;

• caso a especificacao consista de um teste, compara-se o valor do atributo doEMT com os valores fornecidos pela especificacao de acordo com os operadoresrelacionais contidos nesta especificacao; e

• se a especificacao contiver uma variavel deve-se buscar uma substituicao talque, satisfeitos os itens anteriores, torne a premissa verdadeira apos sua aplica-cao (isto e, na presenca de variaveis deve-se executar um processo de unificacao,

25

aplicando a substituicao resultante na premissa) (Brachman e Levesque 2004,Russel e Norvig 2004).

Ja a estrutura da consequencia de uma regra de producao deve conter a alteracaoa ser realizada na memoria de trabalho. Existem tres possibilidades de alteracaopara uma regra:

• ADICIONA (tipo atributo1 : valor1 atributo2 : valor2 . . . atributon : valorn):adiciona um determina elemento a memoria de trabalho;

• REMOVE i: remove da memoria de trabalho o elemento que teve uma cor-respondencia positiva com a condicao da i-esima premissa;

• ATUALIZA i (atributon especificacaon): atualiza o atributo atributon deacordo com especificacaon do elemento da memoria de trabalho que teve umacorrespondencia positiva com a condicao da i-esima premissa.

Assim, como para os EMTs, as regras tambem sao escritas em diferentes sistemasespecialistas de acordo com uma linguagem propria, mas contendo a estrutura e oselementos aqui apresentados.

Exemplo 2.4.3. Sejam a MT da Figura 2.4 e a regra da Figura 2.6.

Figura 2.6: Exemplo de regra utilizado no Exemplo 2.4.3.

A primeira parte da premissa e pesquisada na MT e uma correspondencia detipo e encontrada: robo. Em seguida, a especificacao de atributo velocidade (umaexpressao), indica que o atributo velocidade do EMT deve ter o mesmo valor daespecificacao, o que de fato ocorre. Ja a especificacao para orientacao e um teste: ovalor deste atributo no EMT deve ser maior que 30o e menor que 90o, o que e obede-cido no EMT. Por fim, uma variavel e utilizada na especificacao de dist obstaculo.A substituicao {x/0.5} completa o processo. A segunda premissa tambem e imedi-atamente satisfeita. Assim, de acordo com a modificacao presente na consequencia,a meta e modificada na MT.

Este processo executado pelo interpretador corresponde ao algoritmo de inferen-cia em LPO de encadeamento adiante. O Algoritmo 2 apresenta o algoritmo deencadeamento adiante conforme Russel e Norvig (2004).

Os SEs foram o primeiro exemplo na historia da IA de um conjunto mais abran-gente de sistemas inteligentes: os Sistemas Baseados em Conhecimento (SBC). SBCssao sistemas que possuem um conhecimento mais geral sobre o domınio de aplica-cao, e o considera separado do restante do sitema. O SEs geralmente possuemconhecimento bastante especıfico, baseado no de um especialista, sendo aplicadosem domınios mais restritos (Mihaguti 1996). Esta distincao, embora nao seja muitorigorosa, sera aplicada neste trabalho ao se descrever o AAC no Capıtulo 3.

26

Algoritmo 2 Algoritmo de Encadeamento Adiante.Entrada: BC: base de conhecimento contendo regras e memoria de trabalho.

1: funcao ENCADEAMENTO-ADIANTE(BC )2: repita3: novo← {}4: para cada regra ∈ BC faca5: (p1 ∧ . . . ∧ pn)← regra6: subst← {σ∗|(p∗1, . . . , p∗n ∈ BC)∧ (p1 ∧ . . .∧ pn)σ∗ = (p∗1 ∧ . . .∧ p∗n)σ∗}7: para cada σ ∈ subst faca8: q∗ ← qσ9: se (∀S ∈ BC ∪ novo) UNIFICAR(q∗, S) ≡ ∅ entao

10: novo← novo ∪ q∗11: fim se12: fim para13: fim para14: BC ← BC ∪ novo15: ate que novo ≡ {}16: fim funcao

2.5 Conclusao

O capıtulo apresentou os metodos de representacao de conhecimento utilizadospelo AAC: a LPO, a LTP, os quadros e os SBCs. Alem disso, os procedimentosde raciocınio automatico utilizados pelo agente foram descritos. O encadeamentoadiante e utilizado por um sistema especialista com uma base de conhecimentocomposta por regras da LPO, e o algoritmo MetateM para uma BC que aplicaLTP. O capıtulo seguinte descrevera como o AAC utiliza estas representacoes ealgoritmos para a tomada de decisao em ambientes dinamicos.

27

Capıtulo 3

O Agente Autonomo Concorrente(AAC)

Este capıtulo apresentara o Agente Autonomo Concorrente (AAC). Sua arquite-tura cognitiva sera descrita, inicialmente em termos da sua implementacao original,com base no framework Expert-Coop++. Em seguida, serao apresentadas as ade-quacoes estruturais realizadas para implementar o agente embarcado na arquiteturade hardware proposta neste trabalho. Por fim, os metodos de representacao de co-nhecimento utilizados pelo agente serao abordados, fazendo sempre uma correlacaocom o conteudo do Capıtulo 2.

3.1 Modelo Generico para Agentes Cognitivos

A arquitetura do AAC foi inspirada no modelo generico para agentes cognitivos,proposto em (Bittencourt 1997). De acordo com esse modelo, um agente cognitivoe composto por tres nıveis: o nıvel reativo, o nıvel instintivo e o nıvel cognitivo. Omodelo e ilustrado na Figura 3.1.

O nıvel reativo, caracterizado por um rapido ciclo percepcao/acao, representa umambiente evolucionario composto por padroes retirados das percepcoes do ambiente,controles de efetuador utilizados para atuar no ambiente externo e um conjunto decomportamentos reativos atrelando percepcao e acao. Este nıvel modela animaissimples, como insetos.

O nıvel instintivo possui uma memoria que possibilita perceber quando situacoesse repetem na natureza e que grupo de agentes reativos pode ser utilizado nessassituacoes, aplicando-os novamente quando aquela situacao de repetir. Este nıvel,juntamente com o reativo, pode modelar animais mais complexos, como os mamıfe-ros.

O nıvel cognitivo se baseia no aprendizado de situacoes relevantes e a subsequentegeracao de novas estrategias de acao.

Segundo esse modelo, cada nıvel, juntamente com os seus hierarquicamente in-

28

Figura 3.1: O Modelo Generico de Agentes Cognitivos (Barbosa 2005).

feriores, pode modelar um agente completo, sendo que a complexidade do modelocresce com o numero de camadas.

3.2 Arquitetura Cognitiva do AAC

O AAC surgiu para superar as deficiencias encontradas no agente utilizado na pri-meira participacao do UFSC-Team na categoria de robos simulados da RoboCup’98.A arquitetura desse agente apresentava um processo decisorio centralizado, o quecomprometeu a comunicacao em tempo-real com o ambiente (Costa et al. 2011).

Com isso, o AAC foi incorporado na implementacao do framework Expert-Coop++,que entao passou a possibilitar a implementacao de agentes cognitivos com processodecisorio descentralizado, atraves de uma abordagem concorrente. A arquiteturado AAC e ilustrada na Figura 3.2, fazendo a correspondencia com os processos doExpert-Coop++“Interface”, “Coordinator”e“Expert”, onde os nıveis do AAC foramimplementados (Costa e Bittencourt 1999).

O nıvel reativo e responsavel pela resposta em tempo-real do agente. Em sua pri-meira implementacao foi executado pelo processo “Interface” do Expert-Coop++ econtem um conjunto de controladores nebulosos que implementam os comportamen-tos reativos do agente, os quais sao ativados em situacoes especıficas. Apenas umcontrolador nebuloso pode estar ativo por vez. Esse nıvel faz a leitura dos sensorese executa uma acao (isto e, executa o ciclo percepcao-acao do agente). A Figura 3.3ilustra a estrutura deste nıvel.

O nıvel instintivo detecta, apos cada ciclo percepcao-acao, mudancas nos estadosdo ambiente e do agente, atualiza as informacoes simbolicas utilizadas pelo nıvel

29

Figura 3.2: Arquitetura do AAC (Costa e Bittencourt 1999).

Figura 3.3: Nıvel reativo do AAC implementado no framework Expert-Coop++(da Costa et al. 2003).

cognitivo e coordena a selecao de comportamentos reativos. A Figura 3.4 ilustraa atuacao desse nıvel. Este nıvel executa planos que, se bem sucedidos, levam asatisfacao de metas locais. Quando uma meta local e satisfeita, uma mensageme enviada ao nıvel cognitivo, avisando ao mesmo. Um SBC, cuja base de regraspode ser selecionada dentre varias, cada uma correspondendo a um plano, executaa selecao de comportamentos reativos. A memoria de trabalho desse SBC (que, nocontexto do AAC, como se vera adiante neste capıtulo, e denominada base de fatos)armazena o estado atual do mundo.

O nıvel cognitivo e responsavel pela criacao das metas locais e globais atraves umSBC, e a comunicacao das mesmas para o nıvel instintivo (Figura 3.5). Este nıvelrecebe as informacoes simbolicas do nıvel instintivo (com a qual gera um modelo lo-

30

Figura 3.4: Nıvel instintivo do AAC implementado no framework Expert-Coop++(da Costa et al. 2003).

gico) e as mensagens dos outros agentes. O nıvel cognitivo nao interage diretamentecom o reativo. Um importante aspecto do AAC e que enquanto os nıveis instintivoe reativo trabalham no alcance de uma meta local, o nıvel cognitivo pode, concomi-tantemente, se dedicar a tarefas de planejamento, criacao de metas, etc. Assim, porpossuir um maior tempo de resposta, o sistema baseado em regras do nıvel cognitivopode ser bastante mais complexo que o do instintivo.

Figura 3.5: Nıvel cognitivo do AAC implementado no framework Expert-Coop++(da Costa et al. 2003).

Um componente importante presente em todos os nıveis apresentados acima, omailbox, tem um papel fundamental no funcionamento do agente. O mailbox consistede um objeto instanciado em cada processo do Expert-Coop++ que oferece uma

31

interface de comunicacao baseada em soquetes UNIX e uma estrutura de dados quefunciona como um buffer, armazenando as mensagens em uma fila de tamanho finito.Quando uma mensagem e lida, a mesma e removida da fila (Barbosa 2005).

3.3 Arquitetura do AAC Embarcado

Para embarcar o agente, a estrutura dos nıveis do AAC apresentada na secaoanterior foi modificada. No nıvel reativo os comportamentos serao implementadospor um sistema de controle classico, e consistirao de direcoes para onde o robo podeseguir. Conforme ilustrado na Figura 3.6, oito comportamentos serao utilizados pelonıvel reativo embarcado: norte (N), nordeste (NE), leste (L), sudeste (SE), sul (S),sudoeste (SO), oeste (O) e noroeste (NO). Quando um dos comportamentos lista-dos acima esta ativo (na figura, o comportamento NE e mostrado como ativo), orobo devera seguir na direcao correspondente. Adicionalmente, o comportamento“pare sucesso” e “pare falha” (nao ilustrados na Figura 3.6) serao implementadospara que o robo pare em caso de ter alcancado a meta ou de ter colidido, respecti-vamente.

Figura 3.6: Nıvel reativo embarcado.

A principal modificacao estrutural no caso do nıvel instintivo embarcado sera apresenca de dois Mailboxes, pois, como se estabelecera no Capıtulo 4, a arquitetura dehardware onde o AAC sera embarcado consiste de dois protocolos de comunicacaodiferentes, e decidiu-se dividir o Mailbox para cada barramento para reduzir aschances de problemas decorrentes do acesso a recursos compartilhados. A Figura3.7 mostra esta arquitetura.

32

Figura 3.7: Nıvel instintivo embarcado.

Finalmente, o nıvel cognitivo pode ou nao sofrer modificacoes. Isso porque, comose vera no Capıtulo 4, mesmo em um ambiente embarcado podera ser utilizadaa implementacao original do nıvel cognitivo, isto e, a implementacao do processo“Expert” do Expert-Coop++. Mas neste trabalho propoe-se a utilizacao de LTPneste nıvel, entao uma estrutura atualizada deste nıvel, levando em consideracaoambas as formas de representacao de conhecimento, e mostrada na Figura 3.8.

3.4 Representacao do Conhecimento no AAC

3.4.1 LPO e Quadros

A arquitetura original do AAC utiliza a LPO e quadros para compor a base de co-nhecimento de um sistema baseado em conhecimento. Os EMT, doravante referidossimplesmente como fatos, tem a estrutura mostrada na Figura 3.9 (de Santana Ju-nior e Costa 2007). A parte “a” da Figura 3.9 mostra um fato simples, que enunciaapenas um atributo de um dado objeto. A parte “b” dessa figura, representa o casode multiplos atributos (como aqueles da Figura 2.3).

33

Figura 3.8: Nıvel cognitivo embarcado.

Figura 3.9: Formato de um fato simples (a) e um composto (b).

Exemplo 3.4.1. O segundo exemplo da Figura 2.3 (Capıtulo 2, Secao 2.4) repre-sentado conforme a parte “b” da Figura 3.9 e mostrado na Figura 3.10.

Figura 3.10: Exemplo de uma base de fatos.

As regras no ACC possuem o formato mostrado na Figura 3.11. Na figura, “re-gra id” denota o identificador da regra, que deve ser unico na base de regras. As“condicoes”, como na Secao 2.4, tem a estrutura dos fatos com os valores dos atribu-tos substituıdos por especificacoes. Mas no AAC especificacoes contendo variaveissao complementadas por filtros, especificados no campo “filter”, que proveem asrestricoes condicionais as quais os valores das variaveis devem obedecer. As “con-sequencias”, por fim, expressam as acoes a serem tomadas (de Santana Junior eCosta 2007). Estas acoes nao sao apenas locais, isto e, apenas sobre a propria base

34

de fatos, mas tambem envolvem a troca de mensagens entre os nıveis do AAC. Oformato das mensagens adotado e o da linguagem de comunicacao entre agentescognitivos Parla (da Costa e Bittencourt 1997).

Figura 3.11: Formato de uma regra de producao.

Exemplo 3.4.2. A Figura 3.12 mostra um exemplo de base de regras para o nıvelinstintivo. A regra “regra 1” verifica se a meta atual foi atingida, isto e, se o roboesta a menos de 10cm de distancia da meta. Caso existam fatos na base de fatosque tornem essa condicao verdadeira, o nıvel instintivo envia para o cognitivo umamensagem informando que a meta local foi alcancada, e para o reativo uma men-sagem contendo o comportamento selecionado. A segunda regra (“regra 2”) verificase a distancia do robo a uma obstaculo e menor que o limiar de 5cm, caso em que orobo e considerado em zona de colisao.

Figura 3.12: Exemplo de uma base de regras com 2 regras.

Conforme ja foi mencionado, o AAC admite tambem a utilizacao de quadros narepresentacao do conhecimento do agente. A Figura 3.13 mostra como os quadrossao utilizados na linguagem do agente. Os “frame id” e uma identificador quepermite que o quadro seja fornecido como valor de atributo para outros quadros.

Figura 3.13: Formato dos quadros na linguagem do AAC.

A sintaxe completa da linguagem de representacao do conhecimento utilizada peloAAC e mostrada na Figura 3.14 (de Santana Junior e Costa 2007).

35

Figura 3.14: Sintaxe completa na forma de Backu-Naur (de Santana Junior eCosta 2007).

O motor de inferencia implementa o algoritmo de encadeamento adiante, mostradono Algoritmo 2. A BC dada como entrada para este algoritmo, neste caso, consistedas bases de fatos e de regras. Assim, a Figura 3.15 ilustra a arquitetura do SBCutilizado nos nıveis instintivo e cognitivo quando LPO e quadros sao os formalismosde representacao do conhecimento.

Figura 3.15: Diagrama do SBC do AAC (de Santana Junior e Costa 2007).

3.4.2 LTP

Alternativamente, o nıvel cognitivo pode utilizar a LTP como formalismo de re-presentacao de conhecimento. O algoritmo MetateM, utilizado para inferencia,consiste de um processo de encadeamento adiante caracterıstico de sistemas espe-cialistas. Neste contexto, para manter os metodos desta secao e da anterior dentro

36

de um mesmo padrao estrutural, pode-se fazer a correspondencia dos termos aliutilizados com a abordagem atual:

• dado um modelo 〈N, π〉, o mapeamento π constitui a base de fatos, isto e, oque e conhecido como verdadeiro;

• a base de regras consiste do conjunto de regras que formam um sentenca naFNS da LTP; e

• o motor de inferencia implementa o algoritmo MetateM.

A dinamica do sistema muda pelo fato de que agora a base de fatos nao mudaapenas como resultado dos ciclos de inferencia do MI e das mensagens recebidas,mas tambem ao longo do tempo.

Exemplo 3.4.3. A Figura 3.16 ilustra isso. O motor de inferencia utiliza o fato Aem t− 1 para inferir, com base na (unica) regra A⇒ eB, que B sera um fato em t,mas nenhuma regra conclui A. Assim, a propria passagem do tempo faz A“expirar”.

Figura 3.16: Inferencia com LTP.

Segundo Fisher (2011), o algoritmo MetateM pode ser utilizado para tarefasde planejamento atraves da adequada postergacao da satisfacao de eventualidades.Mais precisamente, deve-se assumir que as metas serao eventualmente alcancadas,mas tambem deve-se garantir que isso nao ocorra ate que os pre-requisito para aquelameta tenham sido alcancados. Isto e, uma meta possui n pre-requisitos, denotandoa meta pelo sımbolo meta e os pre-requisitos pelos sımbolos pr1, . . . , prn, a base de

37

regras do planejamento e dada por:

inıcio⇒ ♦meta

¬pr1 ⇒ e¬meta

. . .

¬prn ⇒ e¬meta.

De acordo com as regras acima, enquanto algum dos pre-requisitos nao for satisfeito,¬meta estara na base de fatos, impedindo a satisfacao da meta.

E possıvel tambem, atraves do uso de eventualidades e do exposto acima sobrepostergacao das suas satisfacoes, expressar o ordenamento de metas: se as metasmeta1, . . ., metam devem ser alcancadas nesta ordem, as sentenca

♦(meta1 ∧ ♦(...metam−1 ∧ ♦metam) . . .)

captura essa especificacao (Fainekos et al. 2009).

3.5 Conclusao

Neste capıtulo viu-se a arquitetura cognitiva do AAC e como esta foi herdadado modelo generico de agentes cognitivos. Tambem se explanou como esta arqui-tetura foi ajustada para ser embarcada em uma rede de microcontroladores, sendoo nıvel reativo, camada mais baixo do AAC, o nıvel que mais sofreu modificacoes.Mostrou-se como o agente utiliza LPO e quadros para representar conhecimento,e mostrou-se como a LTP pode tambem ser utilizada como metodo de represen-tacao de conhecimento e raciocınio (este ultimo procedimento implementado peloalgortimo MetateM).

38

Capıtulo 4

Arquitetura de Hardware

Para suprir a demanda de concorrencia do AAC, apresenta-se neste capıtulo umaarquitetura de hardware composta por uma rede de microcontroladores dedicada aexecucao deste agente. Este capıtulo compoe, pois, o nucleo do presente trabalho,trazendo a sua principal contribuicao. O proposito da arquitetura e embarcar o AACno robo movel omnidirecional AxeBot. A rede embarcada e proposta com o intuitode fazer o AAC funcionar como um sistema distribuıdo em que um comportamentointeligente emerge da interacao entre os tres nıveis do agente de forma transparente.

4.1 Visao Geral do Sistema Embarcado

Uma rede heterogenea consistindo de tres microcontroladores compoe o arquite-tura de hardware projetada para comportar o AAC. Os nos computacionais da redesao os seguintes:

• o DIL/NetPC (DNP) 2486, da SSV Embedded Systems;

• o ARM mbed ; e

• o PSoC 5LP, da Cypress Semiconductors.

A rede e heterogenea porque utiliza duas interface de comunicacao digital diferen-tes entre seus tres nos: uma rede CAN (sigle em ingles de Controller Area Network)conecta o mbed e o PSoC, e uma rede Ethernet conecta o mbed e o DNP.

A rede foi projetada desta forma para permitir que o AAC seja embarcado namesma. Ja foi visto anteriromente neste trabalho que o AAC requer concorrencia.Esta concorrencia so pode ser alcancada perfeitamente se cada nıvel tiver um nucleocomputacional dedicado a sua execucao. Alem disso, estes nucleos computacionaisdevem poder se comunicarem entre si, conforme a demanda de comunicacao entreos nıveis do AAC. A arquitetura da rede e mostrada na Figura 4.1.

39

Figura 4.1: Diagrama de Blocos da rede de Microcontroladores.

4.2 Protocolos de Comunicacao

4.2.1 O Protocolo CAN

O protocolo de comunicacao serial Controller Area Network (CAN) foi criado porRobert Bosch na decada de 1980 para ser utilizado na comunicacao entre diversossubsistemas de um veıculo automotivo, prescindindo de um sistema de controle cen-tral. Desde entao, o protocolo CAN passou a ser utilizado amplamente no contextode automacao industrial, ate que, em 1993, se tornou um padrao interncaional: oISO (International Standards Organization) 11898 (Zhang 2010).

O protocolo CAN e definido em termos do modelo de sete camadas OSI (OpenSystems Interconnected) como compostos das suas duas camadas mais baixas: ascamadas fısica e de enlace. A camada fısica trata de especificacoes do meio fısico. Acamada de enlace e responsavel, em termos gerais, pela manutencao de um enlacelogico entre os nos. A Figura 4.2 mostra as camadas OSI acima referidas e oselementos da rede CAN que as implementam (Zhang 2010).

Figura 4.2: Camadas OSI do protocolo CAN e os elementos que as implementam.

No caso da camada fısica, o protocolo CAN nao define um meio de transmissao,

40

apenas que os sinais devem ser transmitidos utilizando uma codificacao diferencial,o que significa que os valores logicos no barramento serao codificados de acordo coma diferenca de tensao entre duas linhas - CANH e CANL - conforme o ilustrado naFigura 4.3. Nessa figura ve-se que o nıvel logico alto e classificado como recessivo,e o baixo, como dominante. Isto significa que se um no tentar impor o nıvel logicoalto sobre o barramento, enquanto outro, ao mesmo tempo, tentar impor o nıvellogico baixo, o ultimo prevalecera (Ranjith 2013).

Figura 4.3: Codificacao diferencial dos sinais no protocolo CAN (Ranjith 2013).

A comunicacao em uma rede CAN ocorre por meio da difusao (broadcasting) demensagens em um barramento. A taxa de transmissao de dados numa rede CANpode chegar a 1 Mbps. A topologia deste barramento e ilustrada na Figura 4.4.Nesta figura e ressaltado o papel do transceiver como o elemento que e fisicamenteconectado ao barramento. Alem disso, fica explıcito que cada no deve possuir umtransceiver. O que a figura nao mostra e o controlador CAN, que tambem deveestar presente em cada no. O controlador CAN e mais frequentemente integrado aohardware dos nos da rede, enquanto que os transceivers sao geralmente externos aestes ultimos.

Figura 4.4: Barramento CAN (Barrenscheen 1998).

No entanto, quando o barramento e suficientemente curto (menor que 10cm),como em projetos em que este barramento e embarcado, a presenca dos transceiverspode ser prescindida em prol de uma topologia simplificada. Mas a velocidademaxima de transmissao em barramentos sem transceivers e limitada a 500 kbps(Barrenscheen 1998). Esta configuracao e mostrada na Figura 4.5.

41

Figura 4.5: Barramento CAN sem transceivers (Barrenscheen 1998).

Qualquer no conectado ao barramento, detectando que este ultimo se encontralivre, pode iniciar a transmissao de mensagens. Estas mensagens sao organizadas empacotes de dados denominados quadros. O protocolo CAN conta com quatro tiposde quadros: o quadro de dados, utilizado para transferir dados entre nos, o quadroremoto, utilizado para os nos fazerem requisicoes de dados, o quadro de erro, quepode ser transmitido por qualquer no quando um erro e detectado no barramento,e o quadro de sobrecarga, utilizado entre dois quadros de dados ou remotos paraprover um atraso adicional. O quadro de dados e mostrado na Figura 4.6. O

Figura 4.6: Quadro de dados do protocolo CAN (Ranjith 2013).

campo de arbitracao carrega o significado da mensagem, e cada no do barramentodecide, ao ler este campo, se deve aceitar essa mensagem. Tambem e utilizado paraarbitrar o acesso ao meio: em caso de colisao, o no cuja mensagem possui o menoridentificador de 11 bits tem a prioridade. O campo de controle contem o tamanhoda mensagem, o campo de dados contem os dados da mensagem e o campo CRC(Cyclic Redundancy Check) e utilizado pelos nos do barramento para verificar errosno quadro (Ranjith 2013).

Se referindo a Figura 4.2, a camada de enlace divide suas responsabilidades entrea subcamada de controle da ligacao logica (do ingles, Logical Link Control, LLC) e asubcamada de controle de acesso ao meio (do ingles, Medium Access Control, MAC).A subcamada LLC executa a aceitacao de mensagens atraves de um mecanismode filtragem, notificacao de sobrecarga e gestao de recuperacao. Ja as tarefas dedeteccao de erros, encapsulamento de dados em pacotes, confirmacao e gestao deacesso ao meio sao atribuicoes da subcamada MAC (Zhang 2010).

42

4.2.2 O Protocolo Ethernet

O protocolo Ethernet (IEEE 802.3) especifica uma camada de enlace de dados, quepossui (a exemplo do protocolo CAN, abordado na secao anterior) as subcamadasLLC e MAC, e uma camada fısica (abreviada como PHY) (IEEE 2012).

A camada fısica especifica que os sinais eletricos sao transmitidos atraves de doissinais diferenciais: um de recepcao, com linhas rotuladas de RX+ e RX-, e um detransmissao, com linhas TX+ e TX-, com valocidade maxima de transmissao dedados de 100 Gbits/s. A codificacao utilizada para estabelecer os nıveis logicos dosinal eletrico e a codificacao Manchester, que atribui um valor logico a uma transicaode estados dentro de um tempo de bit: uma transicao ascendente produz um nıvellogico alto, e uma transicao descendente, um nıvel logico baixo, conforme a Figura4.7 exemplifica (IEEE 2012).

Figura 4.7: Forma de onda correspondente a sequencia de bits “0011110” sob acodificacao Manchester (IEEE 2012).

A codificacao Manchester e utilizada sobre os quadros de dados do protocoloEthernet para torna-los apropriados a trasnmissao. Os quadros Ethernet tem aestrutura mostrada na Figura 4.8.

Figura 4.8: Estrutura de um quadro Ethernet (Toulson e Wilmshurst 2012).

O padrao IEEE 802.2 tambem especifica que a comunicacao com o protocoloEthernet pode ocorrer nos modos half-duplex (apenas um no pode utilizar o meiopor vez) ou full-duplex (os dois nos podem utilizar o meio concomitantemente, massomente para comunicacoes ponto-a-ponto entre dois nos). No primeiro caso um me-canismo de contencao e necessario para detectar quando dois nos estao transmitindoao mesmo tempo. O mecanismo especificado no padrao e o algoritmo Carrier SenseMultiple Access with Collision Detection (CSMA/CD). Este algoritmo consiste emfazer os nos “escutarem” o meio enquanto transmitem para detectar colisoes commensagens de outros nos. Se uma colisao e detectada, os nos mantem a colisao pormais algum tempo para que os demais nos a percebam, e entao cessam a transmissao,tentando novamente depois de um intervalo de tempo aleatorio (IEEE 2012).

43

4.3 Nıvel Reativo: PSoC 5LP

4.3.1 O PSoC 5LP

O PSoC (Programmable System-on-Chip) 5LP e o microcontrolador que compoe ono da rede onde o nıvel reativo do AAC foi embarcado. As principais caracterısticasdo PSoC 5LP sao mostradas na Tabela 4.1.

Tabela 4.1: Principais caracterısticas do PSoC 5LP

Recurso PSoC 5LP

CPU ARM Cortex-M3, 1.25 DMIPS/MHzFlash 256KB

SRAM 64KBEEPROM 2KB

A Figura 4.9 mostra a arquitetura do PSoC 5LP. Nesta figura pode ser notadoque o PSoC 5LP tem quatro subsistemas principais:

• o subsistema da CPU, que utiliza o processador ARM Cortex-M3, com peri-fericos de comunicacao dedicados;

• o subsistema digital, consistindo de blocos digitais denominados UDBs (Uni-versal Digital Blocks), que implementam recursos digitais no hardware, inde-pendentes da atuacao da CPU;

• o subsistema analogico, que prove recursos analogicos tambem de maneiraindependente da CPU; e

• o subsistema de roteamento programavel, que permite determinar funcoes depinos em tempo de projeto.

Ressalta-se a conveniencia de se utilizar o PSoC 5LP como plataforma para em-barcar o nıvel reativo, devido ao fato de que este microcontrolador possui uma arqui-tetura adequada ao carater evolutivo do nıvel reativo proposto no modelo genericopara agentes cognitivos. Ou seja, a versao embarcada do nıvel reativo apresentadaaqui pode, em implementacoes futuras, ser estendida para mimetizar a arquiteturado nıvel reativo mostrado na Figura 3.1 atraves do uso mais intenso dos subsistemasdigital e analogico do PSoC nas tarefas de aquisicao e controle. Os controladoresdifusos, por exemplo, poderiam ser implementados nos UDBs do PSoC, liberando oprocessador para tarefas de comunicacao e computacao evolutiva.

44

Figura 4.9: Arquitetura do PSoC 5LP.

4.3.2 O Sistema Operacional de Tempo Real

Para a correta performance do nıvel reativo, o PSoC deve realizar uma serie detarefas:

• comunicacao CAN com o mbed (nıvel instintivo);

• comunicacao UART com um PC para supervisao e simulacao;

• executar o controle cinematico; e

• executar o controle dos atuadores.

O gerenciamento destas tarefas foi realizado com a utilizacao de um Sistema Ope-racional de Tempo Real (SOTR), dado que, conforme (Stankovic e Rajkumar 2004),um SOTR e capaz de gerenciar e capaz de gerenciar multiplas tarefas atraves demecanismos de sincronizacao envolvendo priorizacao de tarefas e escalonamento,provendo uma camada de abstracao no projeto do software.

O SOTR utilizado aqui foi o FreeRTOS. No FreeRTOS as tarefas podem estar emum dos seguintes estados:

• executando, quando a tarefa esta executando;

• bloqueada, quando a tarefa nao esta apta a executar ate que algum eventoocorra;

• pronta, quando nao esta executando, mas pode estar; e

• suspensa, quando nao esta executando e nao pode estar.

A Figura 4.10 mostra os estados listados acima e as possıveis transicoes entreeles. Quando uma tarefa e criada o estado dela e “pronta”, e um escalonador detarefas decide se ela pode ou nao estar no estado “executando” com base na sua

45

prioridade: se alguma tarefa com prioridade superior ja esta executando, a tarefarecem criada espera (no estado “bloqueada”) ate que a tarefa que esta executandoseja bloqueada ou suspensa; se a tarefa executando tem prioridade inferior a criada,esta ultima passa a executar e a primeira vai para o estado “bloqueada”. Caso naohaja uma tarefa no estado “executando”, a nova tarefa passa automaticamente paraeste estado.

Figura 4.10: Diagrama de estados das tarefas no FreeRTOS.

As tarefas criadas no nıvel reativo sao mostradas na Tabela 4.2. Nesta tabela,a terafa inativa corresponde a tarefa que e posta no estado “executando” pelo es-calonador de tarefas quando nao ha tarefas neste estado, nem no estado “pronta”.

Tabela 4.2: Tarefas implementadas.

Tarefa Prioridade

Controle Cinematico 3Controle de Atuadores* 2

Recepcao de Mensagens CAN 2Envio de Mensagens CAN 3

Tarefa Inativa 1* = Inativa em alguns experimentos (ver Capıtulo 5)

4.3.3 Encapsulamento de Sistema de Controle no Nıvel Re-ativo

Na Figura 3.6 (Capıtulo 3, Secao 3.3) e mostrado o conjunto de comportamen-tos reativos a serem implementados na versao embarcada do nıvel reativo do AAC.Mencionou-se, quando da apresentacao da supracitada figura, que um sistema decontrole classico seria utilizado para a construcao dos comportamentos no nıvelreativo, e nesta secao se descrevera como o modelo cinematico do robo movel om-nidirecional AxeBot sera utilizado no nıvel reativo para o desenvolvimento de umcontrolador cinematico que, por sua vez, devera servir de base para a implementacaodos comportamentos.

46

Modelo Cinematico

O modelo cinematico de uma robo movel omnidirecional e dado pela relacao ma-tematica entre as velocidades angulares dos seus atuadores e a velocidade do seucentro de massa. E obtido a partir da relacao geometrica entre sistemas de refe-rencia locais (aqueles “fixados” na base movel do robo) e um sistema de referenciaglobal (com relacao ao qual os sistemas de referencia locais se movem). A Figura4.11 mostra estes sistemas de referencia para o robo AxeBot. Nesta figura, SR e osistema de referencia da base do robo e os SCi sao sistemas de coordenadas fixadosa cada roda i, com i = 1, 2 e 3 (Bitencourt et al. 2008).

Figura 4.11: Sistemas de coordenadas no AxeBot para modelagem cinematica(Bitencourt et al. 2008).

A Equacao (4.1) apresenta a matriz da cinematica direta do AxeBot.

P (θ) =

−2 cos θ

3

√3 cos θ−3 sin θ

3√3

√3 cos θ+3 sin θ

3√3

−2 sin θ3

√3 sin θ+3 cos θ

3√3

√3 sin θ−3 cos θ

3√3

13 l

13 l

13 l

(4.1)

O modelo cinematico direto completo e apresentado na Equacao (4.2).vxI

vyI

θ

= P (θ)

φ1x

φ2x

φ3x

. (4.2)

47

Na Equacao (4.2), vxI , vxI e θ representam, respectivamente, as velocidades nasdirecoes x e y, e a velocidade angular do centro de massa do robo no sistema decoordenadas SI , φix representa a velocidade angular da roda i com relacao ao eixox do sistema de coordenadas SCi e R e o raio das rodas.

Controlador Cinematico

Uma vez de posse do modelo cinematico do robo e possıvel utilizar este modelopara projetar um controlador que o possibilite estabilizar em uma dada posicao de-sejada (ponto-a-ponto) ou seguir uma trajatoria dada (rastreamento de trajetoria).A este controlador, por se basear em um modelo cinematico, da-se o nome de con-trolador cinematico. Com o controlador cinematico e possıvel implementar controlede posicao ou de velocidade. Aqui sera descrito o controle de posicao, apontando nofinal como modificar este controlador para executar o controle de velocidade.

A entrada do controlador de posicao e a posicao ou trajetoria desejada, isto e,o set-point. O controlador entao calcula o vetor de diferenca entre a posicao dereferencia (xRI , yRI e θR) e a posicao real do centro do robo (xI , yI e θ). Estaoperacao produz o vetor de erro, como na Equacao (4.3). (4.3).

e(t) =

xRI

yRI

θR

−xI(t)

yI(t)

θ(t)

(4.3)

Este vetor de erro e utilizado para calcular uma acao de de controle Proporcional-Integral (PI). Para o controle ponto-a-ponto, segundo Tsai et al. (2005), a acao decontrole e calculada de acordo com a Equacao (4.4), onde KP e KI sao matrizes3× 3 simetricas e positivamente definidas.

u(t) = KP e(t) +KI

t∫0

e(τ) dτ (4.4)

Para o rastreamento de trajetoria o vetor referencia pT (t) =

[xRI (t) yRI (t) θR(t)

]e agora dependente do tempo, e a acao de controle e modificada pela adicao daderivada do vetor de referencia, conforme a Equacao (4.5).

u(t) = KP e(t) +KI

t∫0

e(τ) dτ + p(t) (4.5)

O vetor da acao de controle e entao aplicado na Equacao (4.6) (cinematica in-versa) para a obtencao das velocidades angulares desejadas dos atuadores. Estas

48

Figura 4.12: Diagrama de blocos do controlador cinematico.

velocidades angulares, por sua vez, sao os set-points de outro controlador, em umnıvel mais baixo: o controlador dos atuadores. As velocidades das rodas devemser ajustadas aos valores dados para que a posicao da base seja corrigida. Ribeiro(2010) projetou e implementou este controlador de baixo nıvel para os atuadores doAxeBot, e os seus resultados serao utilizados aqui.

φ1x

φ2x

φ3x

=1

RP−1(θ) u(t). (4.6)

Por fim, a velocidade real das rodas e lida atraves de encoders e aplicadas naEquacao (4.2) (cinematica direta), tendo como resultado as velocidades linearese angular da base. A integracao deste resultado prove a posicao da base, que erealimentada no controlador para novo calculo de erros e continuar o laco. A Figura4.12 mostra um diagrama do controlador.

O controlador cinematico foi utilizado no PSoC 5LP para implementar os com-portamentos do nıvel reativo. Estes comportamentos consistiram simplesmente domovimento nas direcoes cardeais: norte, nordeste, leste, sudeste, sul, sudoeste, oestee noroeste. Nessa caso um controlador de velocidades e mais adequado, pois pode-sefixar uma velocidade linear e alterar apenas a orientacao para intercambiar entre oscomportamentos. A mudanca com relacao ao expostos ate aqui, no entanto, e mı-nima. Primeiro, o set-point agora e um vetor de velocidades, na mais uma posicaoou uma trajetoria. Depois, realimenta-se a velocidade da base (obtida pelo aplicacaoda valocidade real das rodas na cinematica direta), isto e, nao executa a integracaomencionada no paragrafo anterior.

4.4 Nıvel Instintivo: o mbed

O mbed e na realidade um modulo microcontrolado, baseado no microcontroladorNXP LPC1768. Este ultimo, por sua vez, tambem utiliza o micriprocessador ARMCortex-M3 como CPU, a exemplo do PSoC 5LP. O mbed e mostrado na Figura4.13(a) com os seus 40 pinos dispostos em duas linhas de 20. Na parte (b) damesma figura, os elementos do modulo sao apontados, e um diagrama completo dosseus recursos de comunicacao constam na parte (c).

49

Figura 4.13: ARM mbed (Toulson e Wilmshurst 2012).

A Figura 4.14 apresenta um diagrama de blocos do mbed. As entradas e saıdasdigitais do mbed, assim como os perifericos que este disponibiliza, sao os do micro-controlador LPC 1768. Mas devido ao fato de o LPC 1768 possuir mais de 100 pinose o mbed so possuir 40, limita este ultimo a utilizacao de apenas um subconjuntodas funcoes do primeiro. O mbed utiliza um microcontrolador de interface para ge-renciar a comunicacao USB com o PC. Este microcontrolador faz o PC reconhceer ombed como um dispositivo de armazenamento, e gerencia a transferencia do arquivoexecutavel para uma memoria flash de 16 MBits. Quando o botao de reset e pressi-onado, o microcontrolador de interface transfere para a memoria flash do LPC 1768o arquivo executavel mais recente, e inicia a execucao (Toulson e Wilmshurst 2012).

Uma das interfaces CAN e utilizada para a comunicacao com o PSoC 5LP. Esteultimo envia para o mbed informacoes referentes ao estado do ambiente e do agente,e recebe comandos de selecao de comportamentos. A interface Ethernet e utilizadapara comunicacao com o no computacional correspondente ao nıvel cognitivo (o DNP2486 ).

O mbed possui uma API (Application Program Interface) que consiste em umaabstracao da CMSIS (do ingles, Cortex Microcontrollers System Interface Standard),que por sua vez e um padrao de interface de software em linguagem C, desenvolvidapela ARM, para a programacao de microcontroladores baseados em microprocessa-dores da famılias Cortex. A abstracao utilizada pelo mbed corresponde a uma API

50

Figura 4.14: Diagrama de blocos do mbed (Toulson e Wilmshurst 2012).

desenvolvida em C++ que encapsula uma implementacao da CMSIS para o LPC1768, abstraindo-a do desenvolvedor.

A partir da sua versao 3, a CMSIS passou a contar com a CMSIS RTOS, queoferece uma API padronizada para SOTR. Assim, a API do mbed implementa ombed RTOS, totalmente baseado na CMSIS RTOS. Este e o SOTR utilizado para aimplementacao do nıvel instintivo. AS tarefas neste SOTR sao chamadas de threads,e possuem estados similares as tarefas do FreeRTOS (Figura 4.10).

As cinco tarefas utilizadas na implementacao do nıvel instintivo foram:

• Envio de mensagens pela rede CAN;

• Recepcao de mensagens pela rede CAN;

• Envio de mensagens pela rede Ethernet;

• Recepcao de mensagens pela rede Ethernet;

• Motor de inferencia.

Neste no, um sistema baseado em conhecimento com regras em LPO teve que serimplementado, pois o mbed mostrou-se incapaz de executar o processo“Interface”doExpert-Coop++ (responsavel por executar o nıvel instintivo) mesmo para pequenasbases de regras. Assim, utilizou-se estruturas de dados estaticas para armazenar as

51

regras. Alem disso, um mailbox foi implementado para a comunicacao CAN com oPSoC 5LP e outro separado para a comunicacao Ethernet.

4.5 Nıvel Cognitivo: o DNP 2486

O nıvel cognitivo e implementado no DIL/NetPC 2486 : um modulo baseado nomicrocontrolador Vortex86SX SoC (System on Chip) de 300MHz, com 1GB de me-moria Flash NAND e 64MB de memoria SDRAM DDR2. O DNP 2486 utiliza umadistribuicao embarcada do sistema operacional Linux, o que faz com que o nıvelcognitivo embarcado nesta plataforma corresponda a uma aplicacao de usuario exe-cutando neste sistema. Este no tinha que ser bastante robusto computacionalmentepois executara as tarefas mais complexas de raciocınio simbolico do AAC. A Figura4.15 mostra o DNP 2486 juntamente com um diagrama de blocos simplificado domesmo.

Figura 4.15: DIL/NetPC 2486.

Conforme mencionado no Capıtulo 3, o nıvel cognitivo implementa um sistemabaseado em conhecimento com um motor de inferencia que pode utilizar tanto oalgoritmo de encadeamento adiante da LPO, como o algoritmo MetateM da LTP.No primeiro caso, uma implementacao do processo “Expert” do framework Expert-Coop++ e utilizada para o nıvel cognitivo embarcado. Isso porque este frameworkse mostrou portavel para o sistema operacional do DNP.

No caso da base de conhecimento utilizando LTP, com exececao do mailbox, quetambem utilizou a implementacao do Expert-Coop++, um novo sistema baseadoem conhecimento teve que ser desenvolvido. O diagrama de classes da Figura 4.16mostra as classes implementadas e o relacionamento entre elas. A classe “Symbol”representa um sımbolo proposicional, que pode ser positivo ou negativo (sem ou comnegacao, respectivamente), e possui um rotulo identificador. Um conjunto de umou mais objetos da classe “Symbol” interconectados por conjuncoes ou disjuncoes,passados como argumentos para um operador temporal unario compoe um objetoda classe “Logic”. A base de fatos e representada pela classe “FactsBase”, que podeconter uma lista de objetos da classe “Logic” desprovidos de operadores temporais(isto e, sentencas classica conjuntivas ou disjuntivas) que, por sua vez, representam

52

Figura 4.16: Diagrama de classes do sistema baseado em conhecimento de nıvelcognitivo com LTP.

os fatos. Uma regra e um objeto da classe “Rule”, e contem dois objetos da classe“Logic” para representar a sua premissa e a sua consequencia. A classe “RulesBase”permite instanciar uma base de regras com um ou mais objetos da classe “Rule”.Um objeto da classe “InferenceEngine”, entao, implementa o algoritmo MetateM,que consulta as bases de regras e de fatos, atualizando o modelo logico proposicionalcontido nesta ultima.

4.6 Operacao do Sistema

Na Figura 4.17 o diagrama de sequencia do sistema e mostrado, ilustrando como omesmo funciona. Esta figura mostra a troca de mensagens entre os nıveis do AAC eentre este utimo e o ambiente. O agente inicia com um comportamento B1 ativo nonıvel reativo, e este envia ao instintivo as leituras dos sensores. Este nıvel converteas percepcoes recebidas em informacao simbolica a respeito dos estados do agentee do ambiente. A informacao simbolica e usada pelo motor de inferencia do nıvelinstintivo, para decidir se deve mudar o comportamento ativo no reativo, e enviadaao nıvel cognitivo. Este, por sua vez, utiliza a informacao simbolica no seu motorde inferencia para gerar uma nova meta local, caso necessario.

Toda vez que o nıvel instintivo decide que o comportamento atual nao deve sermudado, ele simplesmente nao envia nenhuma mensagem ao reativo, como se ve emI2. De maneira similar, o nıvel cognitivo pode decidir nao atualizar a meta local(especialmente se a informacao simbolica recebida do nıvel instintivo nao informaque a meta local atual foi cumprida). Isso e mostrado em C2 e C3, e e independenteda decisao do nıvel instintivo de mudar ou nao o comportamento reativo atual.

4.7 Conclusao

Neste capıtulo apresentou-se uma rede de microcontroladores concebida especial-mente para embarcar o AAC no robo movel omnidirecional AxeBot. Os tres nos da

53

Figura 4.17: Diagrama de sequencia esperado do sistema.

rede (um para cada nıvel da arquitetura do AAC), isto e, o PSoC 5LP (nıvel reativo),o mbed (nıvel instintivo) e o DNP 2486 (nıvel cognitivo), se comunicam atraves dedois protocolos de comunicacao: CAN (entre o PSoC e o mbed) e Ethernet (entre ombed e o DNP).

Conforme discorreu-se no Capıtulo 3, o nıvel cognitivo do AAC pode executarum sistema baseado em regras com LPO e quadros para representar o conhecimentosimbolico do agente, de acordo com a sua implementacao original (com o Expert-Coop++), como tambem pode utilizar LTP e o algoritmo MetateM para este fim.Mas a utilizacao de LTP pelo cognitivo e uma extensao a arquitetura original doAAC, e o fato de que a arquitetura de hardware proposta permite a utilizacao deambas mostra que, nao obstante o seu proposito especıfico, a arquitetura propostaainda permite o desenvolvimento de outras tecnicas no AAC.

54

Capıtulo 5

Resultados

Os resultados de experimentos realizados com a arquitetura de hardware descritano Capıtulo 4 sao agora apresentados. Inicialmente um esquematico da arquiteturaresultante e mostrado. Depois os experimentos sao descritos e seus resultados expos-tos. O primeiro experimento utiliza apenas o nıvel reativo, e os dois experimentosseguintes com todos os nıveis, apenas alterando a estrategia de representacao deconhecimento e inferencia no nıvel cognitivo.

5.1 Nıvel Reativo: Controlador Cinematico

Nesta secao serao apresentados resultados referentes a experimentos de estabiliza-cao ponto-a-ponto e rastreamento de trajetoria utilizando o controlador cinematicoembarcado no microcontrolador PSoC 5LP.

5.1.1 Configuracao dos Experimentos

A configuracao do experimento com o controlador cinematico difere da dos expe-rimentos subsequentes, pois neste caso foi possıvel utilizar o robo AxeBot real, porutilizar apenas um microcontrolador (nos demais experimentos, como se constatara,utilizou-se um simulador). Assim, utilizou-se a arquitetura da Figura 4.12 completa.

O loop do controlador cinematico foi implementado com um perıodo TCin = 50ms.Para realizar esse ciclo, uma interrupcao de um temporizador do PSoC 5LP foi uti-lizada, liberando a cada 50ms, um semaforo para a tarefa do controlador cinematicoque, por sua vez, executa o correspondente ao ramo direto do diagrama de blo-cos da Figura 4.12. As matrizes KP e KI sao dadas conforme Tsai et al. (2005):KP = 3 I[3x3] e KI = 0.002 I[3x3], onde I[3x3] e a matriz identidade de 3x3.

Ja a tarefa de controle proporcional-integral de velocidade dos motores (os con-troladores de baixo nıvel) foi executado em um perıodo mais curto de TMot = 10ms.Isto significa que este controlador executara cinco iteracoes a cada iteracao do con-trolador cinematico, o que e suficiente para estabilizacao com erro pequeno segundo

55

?. Destes trabalhos foram tambem retirados os valores das constantes proporcionale integral: kp = 0.239 e ki = 0.051, respectivamente.

5.1.2 Resultados

Estabilizacao Ponto-a-Ponto

Como foi dito anteriormente, na estabilizacao ponto-a-ponto uma pose desejada oude referencia e dada como entrada ao controlador e o robo precisa estabilizar naquela

pose. No presente experimento, a pose de referencia foi dada por

[xRI yRI θRI

]T=[

2m 3m 4 rad

]T. A Figura 5.1 mostra o resultado.

Figura 5.1: Resultado para estabilizacao ponto a ponto.

56

Rastreamento de Trajetoria

No problema de rastreamento de trajetoria a referencia e dinamica. A referenciautilizada neste experimento foi uma circunferencia com raio de 2m, cujos pontos fo-ram gerados internamente pela tarefa do controlador cinematico atraves da equacaoparametrica do cırculo, enquanto a orientacao foi fixada em π/2 rad e a velocidadeangular da trajetoria de referencia foi ωR = 0.2 rad

s. A Equacao 5.1 da a expressao

parametrica da trajetoria.xRI (t)

yRI (t)

θRI (t)

=

2 cos (θRI (t) + ωR t)

2 cos (θRI (t) + ωR t)

π/2

(5.1)

Os resultados sao mostrados na Figura 5.2.

Figura 5.2: Resultados para rastreamento de trajetoria.

57

5.2 Nıveis Reativo, Instintivo e Cognitivo: Pla-

nejamento

Os resultados doravante apresentados correspondem a experimentos realizadoscom a rede de microcontroladores completa, isto e, contendo os tres nos correspon-dentes aos nıveis do AAC. A arquitetura dos experimentos, conforme sera mencio-nado logo em seguida, difere da do anterior.

5.2.1 Configuracao dos Experimentos

Um diagrama de circuito da rede e mostrado na Figura 5.3. Neste diagrama ve-seque o barramento CAN, entre o PSoC e o mbed, nao utilizou transceivers, o que eaceitavel para barramentos com comprimento inferior a 10cm.

Figura 5.3: Diagrama de circuito da rede de microcontroladores.

A topologia da rede Ethernet e mostrada na Figura 5.4, onde nota-se que to-dos os nos possuem um conector RJ45 com isolamento magnetico, exceto o mbed.Isto ocorre porque o mbed nao possui uma interface fısica RJ45 nem o isolamentomagnetico em sua placa, entao optou-se por implementar o isolamento magneticoatraves de um banco de capacitores, conforme Ben-Josef (2011), e fazer a conexaopino-a-pino com um cabo CAT5 (par trancado e sem blindagem).

Reiterando o que se afirmou no inıcio desta secao, os experimentos com a redecompleta utilizaram uma configuracao diferente daquela dos experimentos com ocontrolador cinematico: nao se utilizou o robo AxeBot real, mas sim um simuladonos softwares Player 3.0.2 e Stage 3.2.2. O Player e um servidor para robos quefornece interfaces para sensores e atuadores, permitindo uma maior abstracao nodesenvolvimento de aplicacoes envolvendo robos equipados com estes elementos. Osimulador, na realidade, e apenas o Stage, que funciona sobre o Player simulandorobos, sensores e objetos.

58

Figura 5.4: Diagrama da Rede Ethernet.

A despeito da utilizacao de um simulador, o raciocınio automatico do AAC seda inteiramente embarcado na rede de microcontroladores. A arquitetura e aquelada Figura 5.5. Assim, o simulador recebe os comandos do controlador cinematico eenvia as leituras do ambiente de acordo com os seus sensores.

Figura 5.5: Configuracao dos experimentos de planejamento de movimento.

No Capıtulo 3.2 viu-se que o nıvel cognitivo do AAC pode utilizar tanto a LPOquanto a LTP como mecanismos de representacao de conhecimento e inferencia.Sendo assim, dois experimentos serao realizados, cada um utilizando uma dessasvariantes de representacao no nıvel cognitivo. Um aspecto comum a ambos os expe-rimentos e a estrategia de reducao do numero de estados do mundo (ambiente), queconsiste de uma leve modificacao daquela apresentada por Cerqueira et al. (2013).Esta representacao e mostrada na Figura 5.6. Os estados do ambiente sao caracteri-zados pela posicao relativa dos obstaculos e da meta com relacao ao robo. Segmenta-se o espaco, no referencial do robo, em regioes: 4 para a meta (parte (a) da Figura5.6) e 8 para os obstaculos (parte (b) da Figura 5.6). Dessa forma, o estado do

59

ambiente resume-se a determinacao das regioes onde estao a meta (r1, r2, r3 ou r4)e os obstaculos (r1, ... , r7 ou r8).

Figura 5.6: Segmentacao do espaco (a) para a posicao relativa da meta e (b) paraas localizacoes relativas dos obstaculos.

5.2.2 Resultados

Planejamento com LPO

Com o nıvel cognitivo utilizando LPO, a tarefa utilizada no experimento foi: ini-ciando na posicao (−7,−4), o robo deve ir a posicao (3,−3), passando pelo ponto(2, 2). Tem-se, pois, duas metas locais:

• ir do ponto (−7,−4) ao ponto (2, 2);

• ir do ponto (2, 2) ao ponto (3,−3).

Na Figura 5.7 aparece a base de regras utilizada para este experimento. Nestafigura nota-se a utilizacao da sintaxe da linguagem do sistema de producao do AAC(que consta na Figura 3.14).

Figura 5.7: Base de regras para o nıvel cognitivo utilizando LPO.

60

O unico objeto presente e o “meta local”, cujos atributos e respectivos possıveisvalores sao listados abaixo:

• o atributo “atual” pode receber os valores “ir para ponto1”, correspondente aexecucao da primeira meta local, “ir para ponto2”, correspondente a execucaoda segunda meta local ou “nenhuma”; e

• o atributo “status”, por sua vez, tem como possıveis valores “ativa” (indi-cando uma meta em execucao), “sucesso” (indicando uma meta alcancada) ou“falha” (para uma meta que nao pode ser alcancada).

O resultado e mostrado na Figura 5.9.

Figura 5.8: Resultado para planejamento utilizando LPO.

Planejamento com LTP

No caso do nıvel cognitivo utilizando a LTP como mecanismo de representacao deconhecimento, alterou-se apenas a meta global, que agora e chegar ao ponto (6,−2).

O alfabeto de sımbolos proposicionais utilizado foi o seguinte:

• G1: alcancou meta 1.

• G2: alcancou meta 2.

• going to none: agente nao esta indo a nenhuma meta.

• going to G1: agente em direcao a meta 1.

61

• going to G2: agente em direcao a meta 2.

• x1 and x2: variaveis auxiliares para deixar as regras na FNS.

As regras utilizadas sao listadas nas Tabelas 5.1 (regras de inıcio e de eventuali-dade) e 5.2 (regras de proximo instante), acompanhadas por uma descricao.

Tabela 5.1: Regras de inıcio e de eventualidade

Regra Descricao

inıcio⇒ going to noneInicialmente o robo nao esta indo

a nenhuma meta.inıcio⇒ ¬G1 ∧ ¬G2 Inicialmente nenhuma meta foi alcancada.

inıcio⇒ x1 ∧ x2Inicialmente as variaveis auxiliares

sao verdadeirasx1⇒ ♦G1 x1 faz ♦G1 valida inicialmente.

x2⇒ ♦G2 x2 faz ♦G2 valida inicialmente.

going to none⇒ going to G1 Vai para G1.

Tabela 5.2: Regras de proximo instante

Regra Descricao

¬G1 ⇒ e(¬G2) G2 nao pode ocorrer se G1 nao ocorreu.

¬G1 ∧ going to G1 ⇒ egoing to G1Mantem-se indo a G1 se meta 1 nao foi

alcancada

going to G1 ⇒ e(¬G1)Se ainda esta indo a G1 neste instante,

nao tera alcancado no proximo.

¬going to G1 ⇒ egoing to G2Se nao esta mais indo a G1, deve estar

indo a G2.

going to G2 ∧ ¬G2 ⇒ egoing to G2Mantem-se indo a G2 se meta 2 nao foi

alcancada.

going to G2 ⇒ e(¬G2)Se ainda esta indo a G2 neste instante,

nao tera alcancado no proximo.

O resultado e mostrado na Figura 5.9.

5.3 Placa de Circuito Impresso

O presente trabalho tambem produziu como resultado o projeto de uma placa decircuito impresso com a rede de microcontroladores para o AxeBot. O projeto e

62

Figura 5.9: Resultado para navegacao com LTP: em verde o ponto inicial, e emamarelo as metas.

mostrado na Figura 5.10. Esta placa encontra-se em processo de confeccao e porisso nao foi utilizada para a realizacao dos experimentos.

Figura 5.10: Placa de circuito impresso da rede de microcontroladores.

Nessa placa, o barramento CAN completo (isto e, com os transceivers) foi uti-lizado. O circuito resultante e mostrado na Figura 5.11, onde “IC4” e “IC5” cor-

63

respondem aos CIs (Circuitos Integrados) dos transceivers do lado do PSoC e dombed, respectivamente. O CI escolhido para a funcao foi o SN65HVD255D da Te-xas Instruments, que possui tensao nominal de entrada de 5V e suporta taxas detransmissao de ate 1Mbps.

Figura 5.11: Esquematico do barramento CAN.

O diagrama de blocos da rede Ethernet na placa se assemelha aquele da Figura5.4, com a diferenca que o transceiver Ethernet do mbed e tambem ligado a umaporta RJ45 com isolamento magnetico na placa. Alem disso, a placa conta cominterfaces para os seguintes sensores:

• CMPS03 (compasso magnetico): possui uma precisao de 0,1o, e a leitura dovalor medido pode ser feita via I2C (Inter-Integrated Circuit) ou PWM (PulseWidth Modulation);

• GP2D02 (sensor de distancia infravermelho): muito bom para medidas entre10 e 80cm, e a leitura do valor medido e realizada de atraves do envio de umasequencia de pulsos para o sensor, o qual retorna sincronamente os 8 bits dovalor medido;

• DE-ACCM5G (acelerometro): acelerometro com dois eixos e uma saıda ana-logica para cada eixo; possui escala completa de ±5g.

5.4 Conclusao

No presente capıtulo foram descritos os resultados de exprimentos utilizando oAAC embarcado em uma rede de microcontroladores. Os experimentos com o nıvelreativo utilizaram o robo AxeBot, enquanto que os demais foram realizados comum robo simulado. Adicionalmente, uma placa de circuito impresso contendo estarede e mostrada no final da secao. Esta placa encontra-se em processo de confeccao.Com os resultados apresentados neste capıtulo, mostrou-se que o AAC pode utilizara arquitetura de hardware proposta para tarefas de navegacao e planejamento emrobotica movel.

64

Capıtulo 6

Conclusao

Neste trabalho uma rede de microcontroladores foi projetada para comportar aarquitetura cognitiva do AAC. A rede foi concebida mimetizando a estrutura funci-onal do AAC: os tres nıveis deste ultimo (a saber, o nıvel reativo, o nıvel instintivo eo nıvel cognitivo) foram embarcados em cada no da rede, cujas interfaces de comu-nicacao foram utilizadas para implementar a troca de mensagens entre estes nıveis.

O nıvel reativo, responsavel pela resposta em tempo real do agente, foi embarcadono PSoC 5LP, e consistiu basicamente de um controlador cinematico de posicaobaseado no modelo do robo omnidirecional AxeBot. Este no se comunica atraves deum barramento CAN com o mbed, um modulo microcontrolado onde foi embarcadoo nıvel instintivo. Um sistema baseado em conhecimento com uma base de regras emLPO foi implementado neste nıvel para coordenar a selecao de comportamentos nonıvel reativo. O nıvel cognitivo do AAC foi embarcado no DIL-Net PC 2486. Este nose comunica com o mbed atraves de uma rede Ethernet. Na implementacao originaldo AAC, o nıvel cognitivo implementou um sistema baseado em conhecimento comometodo de raciocınio automatico que utilizava LPO e quadros como formalismos paraa composicao da base de conhecimento. Outrossim, neste trabalho foi implementadoum motor de inferencia baseado no algoritmo MetateM para execucao de uma basede regras em LTP.

Os primeiros experimentos para validacao desta arquitetura de hardware envolve-ram apenas o nıvel reativo, onde se comprovou o correto funcionamento do controla-dor cinematico de posicao, seja para estabilizacao em um ponto ou para rastreamentode trajetorias. Em seguida, experimentos com a rede completa confirmaram a per-formance do sistema completo, com o nıvel cognitivo utilizando LPO e em seguidaLTP como formalismos de representacao do conhecimento.

Com isso, este trabalho mostrou que a arquitetura de hardware concorrente pro-posta atende satisfatoriamente as demandas de concorrencia e comunicacao do AAC.Adicionalmente, a arquitetura mostrou-se flexıvel e modular, pois permitiu que umnovo metodo de inferencia pudesse ser utilizado em um dos nıveis da arquiteturacognitiva, fato este importante para pesquisas posteriores em IA que utilizem oAAC.

65

Nao obstante o sucesso obtido nos experimentos, o mbed mostrou severas limi-tacoes em termos de recursos computacionais, o que sugere que em pesquisas pos-teriores este seja substituıdo por um no computacional mais robusto. Alem disso,para usufruir inteiramente das vantagens de se utilizar uma logica temporal, a LTPpode ser substituıda pela logica temporal de primeira ordem, para a qual o algo-ritmo MetateM possui uma extensao. Por fim, os experimentos que fizeram usoda arquitetura completa utilizaram um robo simulado; a placa de circuito impressoprojetada neste trabalho possibilitara testes futuros com robos reais, o que devefortalecer ainda mais o uso desta arquitetura de hardware com o AAC.

66

Referencias Bibliograficas

Ainsworth, M. (n.d.). Application Note 61290: PSoC 3 and PSoC 5 Hardware Design

Considerations. 1 ed.. Cypress Semiconductor.

Barbosa, L. (2005). Um sistema multiagente para monitoramento atmosferico. Dis-

sertacao de Mestrado, UNIFACS.

Barr, A. e E. Feigenbaum (1981). (1982) the handbook of artificial intelligence. Vol.

II. Pitman, London.

Barrenscheen, Jens (1998). AP2921 - On Board Communication Using CAN Without

Transceiver. Siemens.

Barringer, Howard, Michael Fisher, Dov Gabbay, Graham Gough e Richard Owens

(1990). Metatem: A framework for programming in temporal logic. Em:

Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness.

Springer. pp. 94–129.

Barry, Richard (2010). Using the FreeRTOS(tm) Real Time Kernel. Real Time En-

gineers Ltd.

Ben-Josef, Ofir (2011). TLK100 - Ethernet PHY Transformerless Operation. Texas

Instruments.

Bitencourt, Andrea C. P., Alexandre da C. e S. Franco, Marcelo E. de Souza, Cristi-

ano H. de O. Fontes e Augusto C. P. L. da Costa (2008). Internal model control

for trajectory tracking of an omni-directional robot. 3, 363–372.

Bittencourt, G. (1990). An architecture for hybrid knowledge representation. Tese

de Doutorado, Universidade de Karlsruhe.

67

Bittencourt, G. (1997). In the quest of the missing link. International Joint Confe-

rence of Artificial Intelligence.

Bittencourt, G. e A. L. da Costa (2001). Hybrid cognitive model. Em: The Third

International Conference on Cognitive Science ICCS’2001 Workshop on Cog-

nitive Angents and Agent Interaction.

Bittencourt, Guilherme (2006). Inteligencia artificial: ferramentas e teorias. Editora

da UFSC.

Brachman, Ronald e Hector Levesque (2004). Knowledge representation and reaso-

ning. Elsevier.

Cerqueira, R. G., A. L. da Costa, S. G. McGill, Daniel Lee e G. Pappas (2013).

From reactive to cognitive agents: Extending reinforcement learning to generate

symbolic knowledge bases. Em: Simposio Brasileiro de Automacao Inteligente

2013.

Costa, A. L. da e G. Bittencourt (1999). From a concurrent architecture to a con-

current autonomous agents architecture. Lecture Notes in Artificial Inteligence

1856, 85–90.

Costa, P. J., A. G. S. Conceicao, T. T. Ribeiro e J. Junior (2011). Embarcando

o agente autonomo concorrente no robo movel omnidirecional axebot: Nıvel

reativo. Em: X Simposio Brasileiro de Automacao Inteligente (SBAI), 2011.

Proceedings of the 2011. Vol. X.

Cordoba-Montiel, F., S. F. Hernandez-Machuca e D. Hernandez-Ventura (2004).

Hybrid microcontrollers network for distributed instrumentation. Journal of

Applied Research and Technology 2(2), 179–188.

Cyp (2013). PSoC R© 5LP Architecture TRM (Technical Refrence Manual).

da Costa, Augusto Cesar Pinto Loureiro e Guilherme Bittencourt (1997). Parla:

A cooperation language for cognitive multi-agent systems. Em: Progress in

Artificial Intelligence. pp. 207–215. Springer.

68

da Costa, Augusto Loureiro, Guilherme Bittencourt, Luciano Rottava da Silva e

Eder Mateus Nunes Goncalves (2003). Expert–coop++: Ambiente para desen-

volvimento de sistemas multiagente.. ENIA-Encontro Nacional de Inteligencia

Artificial.

da Costa, Augusto Loureiro e Guilherme Bittencourt (2000). From a concurrent

architecture to a concurrent autonomous agents architecture. Em: RoboCup-

99: Robot Soccer World Cup III. pp. 274–285. Springer.

da Costa; G. Bittencourt; L. R. Silva; E. M. N. Goncalves, A. L. (2003).

Expert-coop++: Ambiente para desenvolvimento de sistemas multiagente.

http://www.expert-coop.ufba.br/,.

de Santana Junior, OV e AL Costa (2007). Mecateam 2006: Um sistema multiagente

reativo para futebol de robos simulados. VII Escola Regional de Computacao

Bahia-Alagoas-Sergipe.

Dixon, Clare, Michael Fisher e Mark Reynolds (2000). Execution and proof in a

horn-clause temporal logic. Em: Advances in Temporal Logic. pp. 413–433.

Springer.

E. Aguirre, A. Gonzales (2000). Fuzzy behaviors for mobile robot navigation: design,

coordination and fusion. International Journal of Approximate Reasoning.

Fainekos, Georgios E, Antoine Girard, Hadas Kress-Gazit e George J Pappas (2009).

Temporal logic motion planning for dynamic robots. Automatica 45(2), 343–

352.

Fainekos, Georgios E, Hadas Kress-Gazit e George J Pappas (2005). Temporal lo-

gic motion planning for mobile robots. Em: Robotics and Automation, 2005.

ICRA 2005. Proceedings of the 2005 IEEE International Conference on. IEEE.

pp. 2020–2025.

Fisher, Michael (1991). A resolution method for temporal logic.. Em: IJCAI. Vol. 91.

pp. 99–104.

Fisher, Michael (1996). An introduction to executable temporal logics. The Kno-

wledge Engineering Review 11(01), 43–56.

69

Fisher, Michael (2006). Metatem: The story so far. Em: Programming multi-agent

systems. pp. 3–22. Springer.

Fisher, Michael (2011). An Introduction to Practical Formal Methods Using Tempo-

ral Logic. John Wiley and Sons, Ltd.

Fitting, Melvin (1996). First-order logic and automated theorem proving. Springer.

Fosler, Ross M. (2012). An77759 - getting started with psoc R© 5lp.

Furbach, Ulrich, Gerhard Dirlich e Christian Freksa (1984). Towards a theory of

knowledge representation systems. Em: Artificial Intelligence: Methodology,

Systems and Applications. pp. 77–84.

Gabbay, Dov, Amir Pnueli, Saharon Shelah e Jonathan Stavi (1980). On the tempo-

ral analysis of fairness. Em: Proceedings of the 7th ACM SIGPLAN-SIGACT

symposium on Principles of programming languages. ACM. pp. 163–173.

Hayes, Patrick J (1979). The logic of frames. Frame conceptions and text understan-

ding 46, 61.

IEEE (2012). IEEE Standard for Ethernet. IEEE. Section 1.

Kitano, H., Asada M., I. Noda e H. Matsubara (1998). Robocup: robot world cup.

IEEE Robotics Automation Magazine 5(3), 30–36.

Kitano, H., Asada M., K. Kunyioshi, E. Osawa, I. Noda e H. Matsubara (1997).

Robocup: A challenge problem for artificial intelligence. AI Magazine.

Konur, Savas (2010). A survey on temporal logics. arXiv preprint arXiv:1005.3199.

Lamport, Leslie (1983). What good is temporal logic?. Em: IFIP congress. Vol. 83.

pp. 657–668.

M. Asada, Karl F. MacDormanb, Hiroshi Ishiguro Yasuo Kuniyoshi (2001). Cog-

nitive developmental robotics as a new paradigm for the design of humanoid

robots. Robotics and Autonomous Systems.

Micrel (n.d.). Application Note 120: Capacitive Coupling Ethernet Transceivers

Without Using Transformers. 1 ed.. Micrel.

70

Mihaguti, Eliza Hitomi Fukushigue (1996). Sistemas baseados em conhecimentos:

aplicacoes, tendencias e implicacoes - um estudo exploratorio em empresas bra-

sileiras. Dissertacao de Mestrado, EAESP/FGV.

Minsky, Marvin (1974). A framework for representing knowledge.

Minsky, Marvin (1984). Jokes and the logic of the cognitive unconscious. Springer.

Mohan, A. (2009). Implementing CAN Bus Communication using PSoC. 1 ed.. Cy-

press Semiconductor.

Mohan, A. (2013). Application Note 52701: Implementing CAN Bus Communication

using PSoC 3 and PSoC 5. 1 ed.. Cypress Semiconductor.

Murphy, Robin R. (2000). Introduction to AI Robotics. Massachussets Institute of

Technology Press.

Nascimento, T. P. (2009). Controle de trajetoria de robos omni-direcionais: Uma

abordagem multivariavel. Dissertacao de Mestrado, UFBA.

Oudeyer, P. Y. (2010). On the impact of robotics in behavioral and cognitive sciences:

From insect navigation to human cognitive development. IEEE Transactions

On Autonomous Mental Development 2(1), 2–16.

Pnueli, Amir (1977). The temporal logic of programs. Em: Foundations of Computer

Science, 1977., 18th Annual Symposium on. IEEE. pp. 46–57.

Post, Emil L (1943). Formal reductions of the general combinatorial decision pro-

blem. American journal of mathematics pp. 197–215.

Prado, S. (2012). Mbed - Integrando o FreeRTOS em um Cortex-M3.

Ranjith, M. (2013). Application Note 52701: Getting Started with Controller Area

Network (CAN). Cypress Semiconductor.

Ribeiro, T. T. (2010). Sistema de controle em tempo real aplicado a robotica movel.

Trabalho Final de Graduacao, UFBA.

Ribeiro, Tiago T., Jovelino T. dos Santos, Andre G. S. Conceicao e Augusto L.

da Costa (2011). Sistema microprocessado para controle em tempo real de robos

71

moveis ominidrecionais. Em: X SBAI Simposio Brasileiro de Automacao Inte-

ligente.

Russel, Stuart e Peter Norvig (2004). Inteligencia Artificial. Elsevier.

Santos, J. T. (2010). Projeto e desenvolvimento de um sistema microprocessado

aplicado a robotica movel. Trabalho Final de Graduacao, UFBA.

Stankovic, John A. e A. Rajkumar (2004). Real-Time Operating Systems. Vol. 28.

Kluwer Academic Publishers.

Systems, SSV Embedded (2009). The DNP/2486 MIN-Linux Features. 1 ed.. SSV

Embedded Systems.

Thagard, Paul (1984). Frames, knowledge, and inference. Synthese 61(2), 233–259.

Toulson, Rob e Tim Wilmshurst (2012). Fast and effective embedded systems design:

applying the ARM mbed. Elsevier.

Tsai, Ching-Chih, Li-Bin Jiang, Tai-Yu Wang e Tung-Sheng Wang (2005). Kinema-

tics control of an omnidirectional mobile robot. Em: Proceedings of 2005 CACS

Automatic Control Conference.

Wiznet (n.d.). WIZ610wi User’s Manualt. 1.7 ed.. Wiznet.

Zhang, Peng (2010). Advanced Industrial Control Technology. William Andrew.

72