do arquivo

Transcrição

do arquivo

Universidade Federal da Bahia
Escola Politécnica
Programa de Pós-Graduação em Engenharia
Elétrica
Dissertação De Mestrado
Embarcando o Agente Autônomo
Concorrente em uma Rede de
Microcontroladores de um Robô Móvel
Omnidirecional
Mestrando:
Diego Stéfano Fonseca Ferreira
Orientador:
Prof. Dr. Augusto Cesar Pinto Loureiro da Costa
Salvador
Agosto - 2014
Resumo
Neste trabalho, uma rede heterogênea de microcontroladores é proposta para embarcar o agente autônomo concorrente. A rede foi projetada para comportar os
requisitos de concorrência do modelo cognitivo do supracitado agente. A arquitetura do agente é composta por três nı́veis, a saber, o nı́vel reativo, o nı́vel instintivo
e o nı́vel cognitivo, que são executados concorrentemente. O nı́vel reativo foi embarcado em um PSoC 5LP, e consistiu de comportamentos criados sobre um controlador
cinemático. O nı́vel instintivo é executado em um mbed, que recebe percepções e seleciona comportamentos do nı́vel reativo através de um barramento CAN. A seleção
de comportamentos reativos é realizada por um sistema baseado em conhecimento
(SBC) que utiliza lógica de primeira ordem (LPO) e quadros como formalismos de
representação do conhecimento. O nı́vel cognitivo, embarcado em um DNP 2486,
recebe informações simbólicas do nı́vel instintivo e envia para este último metas
locais através de uma rede Ethernet. Também utiliza um SBC para implementar
o seu processo decisório, mas pode usar tanto LPO e quadros para representação
de conhecimento, como lógica temporal proposicional (LTP). Experimentos com o
nı́vel reativo isolado (utilizando um robô real), e com a rede de microcontroladores
completa (em um ambiente simulado) validaram a arquitetura de hardware proposta. Uma placa de circuito impresso com a rede de microcontroladores também é
apresentada.
Palavras Chave: Robótica móvel, Navegação de Robôs, Agentes Autônomos,
Sistemas Baseados em Conhecimento, Redes de Microcontroladores.
i
Abstract
In this paper, a microcontroller heterogeneous network is proposed to embed a concurrent autonomous agent. The network was designed to fit the concurrency requirements of the cognitive model of the aforementioned agent. The architecture of
the agent comprises three levels, namely, the reactive level, instinctive level and the
cognitive level, which runs concurrently. The reactive level is embedded in a PSoC
5LP, consisting of behaviours created over a embedded kinematic controller. The
instinctive level runs in a ARM mbed, which receives perceptions from and sends the
active behaviour to the reactive level through a CAN bus. The behaviour selection
is executed by a knowledge-based system (KBS) that uses first-order logic (FOL)
and frames as knowledge representation formalisms. And The cognitive level runs
on a DNP/2486 which, in turn, receives symbolic information from and sends new
local goals to instinctive level through an Ethernet network. It also uses a KBS to
implement its reasoning mechanism, but it can use either FOL and frames or propositional temporal logic (PTL) as knowledge representation method. Experiments
with the reactive level isolated (using a real robot), and with the complete network
(in a simulated environment) validated the proposed architecture. A printed circuit
board with the microcontrollers network is also presented.
Keywords: Mobile Robots, Robot Navigation, Autonomous Agents,
Knowledge-Based Systems, Microcontrollers Network.
ii
Índice
Resumo
i
Abstract
ii
Índice
iii
Lista de Figuras
v
Lista de Tabelas
vii
1 Introdução
1
2 Representação de Conhecimento
2.1 Lógica de Primeira Ordem (LPO) . . . . . . . . . . . . . . . . . . . .
2.1.1 Sintaxe da LPO . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Semântica da LPO . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Lógica Temporal Proposicional (LTP) . . . . . . . . . . . . . . . . . .
2.2.1 Sintaxe da LTP . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 Semântica da LTP . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 O Algoritmo MetateM . . . . . . . . . . . . . . . . . . . . .
2.3 Quadros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Sistemas Baseados em Conhecimento e Sistemas Especialistas . . . .
2.4.1 Sistemas de Produção . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Sistemas Baseados em Conhecimento e Sistemas Especialistas
2.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
4
5
7
9
10
12
17
20
22
22
24
27
3 O Agente Autônomo Concorrente (AAC)
3.1 Modelo Genérico para Agentes Cognitivos
3.2 Arquitetura Cognitiva do AAC . . . . . .
3.3 Arquitetura do AAC Embarcado . . . . .
3.4 Representação do Conhecimento no AAC .
3.4.1 LPO e Quadros . . . . . . . . . . .
3.4.2 LTP . . . . . . . . . . . . . . . . .
3.5 Conclusão . . . . . . . . . . . . . . . . . .
28
28
29
32
33
33
36
38
iii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Arquitetura de Hardware
4.1 Visão Geral do Sistema Embarcado . . . . . . . . . . . . . . . . .
4.2 Protocolos de Comunicação . . . . . . . . . . . . . . . . . . . . .
4.2.1 O Protocolo CAN . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 O Protocolo Ethernet . . . . . . . . . . . . . . . . . . . . .
4.3 Nı́vel Reativo: PSoC 5LP . . . . . . . . . . . . . . . . . . . . . .
4.3.1 O PSoC 5LP . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2 O Sistema Operacional de Tempo Real . . . . . . . . . . .
4.3.3 Encapsulamento de Sistema de Controle no Nı́vel Reativo .
4.4 Nı́vel Instintivo: o mbed . . . . . . . . . . . . . . . . . . . . . . .
4.5 Nı́vel Cognitivo: o DNP 2486 . . . . . . . . . . . . . . . . . . . .
4.6 Operação do Sistema . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Resultados
5.1 Nı́vel Reativo: Controlador Cinemático . . . . . . . .
5.1.1 Configuração dos Experimentos . . . . . . . .
5.1.2 Resultados . . . . . . . . . . . . . . . . . . . .
5.2 Nı́veis Reativo, Instintivo e Cognitivo: Planejamento
5.2.1 Configuração dos Experimentos . . . . . . . .
5.2.2 Resultados . . . . . . . . . . . . . . . . . . . .
5.3 Placa de Circuito Impresso . . . . . . . . . . . . . . .
5.4 Conclusão . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39
39
40
40
43
44
44
45
46
49
52
53
53
.
.
.
.
.
.
.
.
55
55
55
56
58
58
60
62
64
6 Conclusão
65
Referências Bibliográficas
67
iv
Lista de Figuras
2.1
2.2
2.3
2.4
2.5
2.6
3.1
3.2
3.3
Exemplo de quadros (Bittencourt 2006). . . . . . . . . . . . . . . .
Estrutura genérica de um sistema de produção de regras. . . . . . .
Formato Geral de um EMT. . . . . . . . . . . . . . . . . . . . . . .
Exemplos de Elementos da Memória de Trabalho. . . . . . . . . . .
Estrutura de uma regra de produção lógica: “n”, “m” e “k” são interios
positivos quaisquer. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplo de regra utilizado no Exemplo 2.4.3. . . . . . . . . . . . .
.
.
.
.
22
22
24
25
. 25
. 26
29
30
3.15
3.16
O Modelo Genérico de Agentes Cognitivos (Barbosa 2005). . . . . . .
Arquitetura do AAC (Costa e Bittencourt 1999). . . . . . . . . . . .
Nı́vel reativo do AAC implementado no framework Expert-Coop++
(da Costa et al. 2003). . . . . . . . . . . . . . . . . . . . . . . . . . .
Nı́vel instintivo do AAC implementado no framework Expert-Coop++
(da Costa et al. 2003). . . . . . . . . . . . . . . . . . . . . . . . . . .
Nı́vel cognitivo do AAC implementado no framework Expert-Coop++
(da Costa et al. 2003). . . . . . . . . . . . . . . . . . . . . . . . . . .
Nı́vel reativo embarcado. . . . . . . . . . . . . . . . . . . . . . . . . .
Nı́vel instintivo embarcado. . . . . . . . . . . . . . . . . . . . . . . .
Nı́vel cognitivo embarcado. . . . . . . . . . . . . . . . . . . . . . . . .
Formato de um fato simples (a) e um composto (b). . . . . . . . . . .
Exemplo de uma base de fatos. . . . . . . . . . . . . . . . . . . . . .
Formato de uma regra de produção. . . . . . . . . . . . . . . . . . . .
Exemplo de uma base de regras com 2 regras. . . . . . . . . . . . . .
Formato dos quadros na linguagem do AAC. . . . . . . . . . . . . . .
Sintaxe completa na forma de Backu-Naur (de Santana Júnior e
Costa 2007). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Diagrama do SBC do AAC (de Santana Júnior e Costa 2007). . . .
Inferência com LTP. . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1
4.2
4.3
4.4
Diagrama de Blocos da rede de Microcontroladores. . . . . . . . . . .
Camadas OSI do protocolo CAN e os elementos que as implementam.
Codificação diferencial dos sinais no protocolo CAN (Ranjith 2013). .
Barramento CAN (Barrenscheen 1998). . . . . . . . . . . . . . . . . .
40
40
41
41
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14
v
30
31
31
32
33
34
34
34
35
35
35
36
36
37
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
4.14
4.15
4.16
4.17
Barramento CAN sem transceivers (Barrenscheen 1998). . . . . . . . 42
Quadro de dados do protocolo CAN (Ranjith 2013). . . . . . . . . . . 42
Forma de onda correspondente à sequência de bits “0011110” sob a
codificação Manchester (IEEE 2012). . . . . . . . . . . . . . . . . . . 43
Estrutura de um quadro Ethernet (Toulson e Wilmshurst 2012). . . . 43
Arquitetura do PSoC 5LP. . . . . . . . . . . . . . . . . . . . . . . . . 45
Diagrama de estados das tarefas no FreeRTOS. . . . . . . . . . . . . 46
Sistemas de coordenadas no AxéBot para modelagem cinemática (Bitencourt
et al. 2008). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Diagrama de blocos do controlador cinemático. . . . . . . . . . . . . . 49
ARM mbed (Toulson e Wilmshurst 2012). . . . . . . . . . . . . . . . 50
Diagrama de blocos do mbed (Toulson e Wilmshurst 2012). . . . . . . 51
DIL/NetPC 2486. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Diagrama de classes do sistema baseado em conhecimento de nı́vel
cognitivo com LTP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Diagrama de sequência esperado do sistema. . . . . . . . . . . . . . . 54
5.1
5.2
5.3
5.4
5.5
5.6
Resultado para estabilização ponto a ponto. . . . . . . . . . . . . .
Resultados para rastreamento de trajetória. . . . . . . . . . . . . .
Diagrama de circuito da rede de microcontroladores. . . . . . . . . .
Diagrama da Rede Ethernet. . . . . . . . . . . . . . . . . . . . . . .
Configuração dos experimentos de planejamento de movimento. . .
Segmentação do espaço (a) para a posição relativa da meta e (b) para
as localizações relativas dos obstáculos. . . . . . . . . . . . . . . . .
5.7 Base de regras para o nı́vel cognitivo utilizando LPO. . . . . . . . .
5.8 Resultado para planejamento utilizando LPO. . . . . . . . . . . . .
5.9 Resultado para navegação com LTP: em verde o ponto inicial, e em
amarelo as metas. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.10 Placa de circuito impresso da rede de microcontroladores. . . . . . .
5.11 Esquemático do barramento CAN. . . . . . . . . . . . . . . . . . .
vi
.
.
.
.
.
56
57
58
59
59
. 60
. 60
. 61
. 63
. 63
. 64
Lista de Tabelas
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
Sintaxe da LPO na forma de Backu-Naur. . . . . . . . . . . . . . .
Sintaxe da LTP na forma de Backu-Naur. . . . . . . . . . . . . . .
Modelo em LTP simplificado. . . . . . . . . . . . . . . . . . . . . .
Representação de um modelo em LTP. . . . . . . . . . . . . . . . .
Representação da semântica do operador de inı́cio. . . . . . . . . . .
Representação da semântica do operador de próximo instante. . . .
Representação da semântica do operador de eventualidade. . . . . .
Representação da semântica do operador de invariância. . . . . . . .
Representação da semântica do operador “até que”. . . . . . . . . .
Representação da semântica do operador “até que”. . . . . . . . . .
Modelo gerado pela execução de uma sentença de próximo instante.
Exemplo de regras de produção de um sistema de Post . . . . . . .
Exemplo de Execução de um Sistema de Post. . . . . . . . . . . . .
4.1
4.2
Principais caracterı́sticas do PSoC 5LP . . . . . . . . . . . . . . . . 44
Tarefas implementadas. . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.1
5.2
Regras de inı́cio e de eventualidade . . . . . . . . . . . . . . . . . . . 62
Regras de próximo instante . . . . . . . . . . . . . . . . . . . . . . . 62
vii
.
.
.
.
.
.
.
.
.
.
.
.
.
6
12
12
13
14
14
15
15
16
16
18
23
23
Lista de Siglas
AAC
Agente Autônomo 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 Memória de Trabalho
FNS
Forma Normal Separada
LLC
Logical Link Control
LPC
Lógica Proposicional Clássica
LPO
Lógica de Primeira Ordem
LTL
Lógica Temporal Linear
LTP
Lógica Temporal Proposicional
MAC
Medium Access Control
MI
Motor de Inferência
viii
MT
Memória 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
Introdução
O homem sempre sonhou com a possibilidade de criação uma máquina que pudesse
executar seus afazeres de maneira completamente autônoma. Esse sonho deu origem
ao ramo multidisciplinar conhecido como robótica, que se iniciou com máquinas de
comando numérico e braços mecânicos teleoperados, e desenvolveu-se a ponto de
contemplar máquinas móveis completamente autônomas nos dias atuais.
O grau de autonomia conferida a um robô varia de acordo com a complexidade
da tarefa que o mesmo deve executar. Em uma linha de montagem industrial, por
exemplo, o comportamento do robô pode ser implementado por uma máquina de
estados discretos, que determinaria exatamente a(s) ação(ões) disponı́vel(is) para
executar em um dado estado. Para tarefas mais complexas, o mecanismo de tomada
de decisão utilizado deve ser mais robusto, atribuindo ao robô versatilidade para
suficiente para agir eficazmente mesmo em circunstâncias não previstas inicialmente.
Neste útlimo caso, a entidade que encarna o mecanismo de ação inteligente é o agente
autônomo.
Existem diversas arquiteturas de agentes autônomos, oriundas principalmente de
estudos da psicologia cognitiva. Essa derivação é explicitada por Murphy (2000),
onde o autor afirma que o paradigma reativo de construção de agentes autônomos
surgiu exatamente de idéias provenientes da etologia, ciência que estuda o comportamento de animais.
Essa influência da psicologia cognitiva no estudo de agentes autônomos é reforçada em (Oudeyer 2010), e ainda a correlação inversa é estudada, isto é, como a
robótica cognitiva está ajudando compreender aspectos comportamentais e cognitivos dos animais. Neste trabalho, exemplos paradigmáticos são apresentados, como a
modelagem do comportamento de insetos, a auto-organização de linguagens em sociedades robóticas, uso de robôs de forma terapêutica para crianças com problemas
de desenvolvimento, entre outros.
Em (M. Asada 2001) vê-se o desenvolvimento de um modelo de cognição para
robôs móveis humanóides. Neste caso, os autores utilizam a RoboCup como plataforma de desenvolvimento. Um agente autônomo para robôs é proposto em (E. Aguirre
2000), cuja arquitetura utiliza lógica nebulosa para coordenar seus comportamen1
tos, e com isso consegue navegar livre de colisões em um ambiente com obstáculos,
alcançando uma meta estabelecida.
Bittencourt (1997) propõe um modelo genérico de agentes cognitivos. Esse modelo consiste em uma arquitetura cognitiva geral utilizada para modelar agentes
de qualquer natureza. O modelo genérico de agentes cognitivos é utilizado como
base por Costa e Bittencourt (1999) para a proposta de uma arquitetura de agente
autônomo chamada Agente Autônomo Concorrente (AAC), utilizado na RoboCup.
A RoboCup, competição internacional de futebol de robôs, é uma plataforma bastante utilizada para a realização de pesquisas em robótica móvel, conforme visto em
(Kitano et al. 1997) e em (Kitano et al. 1998), onde os autores enfatizam a multidisciplinaridade do futebol de robôs e os desafios enfrentados na implementação de
um AAI robótico para este escopo de aplicação.
Mas o AAC possui uma arquitetura cognitiva composta por nı́veis decisórios que
devem executar concomitantemente. Isto implica em uma importante restrição sobre
o hardware computacional onde o AAC será executado: uma arquitetura computacional centrada em um único núcleo computacional não é suficiente. Além disso,
o AAC utiliza originalmente como método de representação de conhecimento a lógica de primeira ordem (LPO). Mas a adição de capacidade de raciocı́nio temporal
traz vantagens importantes, principalmente no que concerne ao planejamento em
ambientes dinâmicos, como é o caso do futebol de robôs.
Assim, de modo a possibilitar a um robô móvel a execução autônoma de tarefas, a
sua inteligência deve ser implementada por meio de um agente autônomo em consonância com as demandas de hardware do mesmo. O objetivo precı́puo deste trabalho
é o projeto de uma rede de microcontroladores para o robô móvel omnidirecional
AxéBot que possibilite o embarque do Agente Autônomo Concorrente (AAC) e que
seja flexı́vel o suficiente para a utilzação de mais de uma forma de representação de
conhecimento.
Para lograr o supramencionado objetivo geral, os seguintes objetivos especı́ficos
são estabelecidos:
• desenvolver um controlador cinemático para a movimentação do robô;
• projeto de uma rede de microcontroladores com nós dedicados para cada nı́vel
do AAC; e
• desenvolver uma estratégia de planejamento de movimento utilizando lógica
temporal.
Este trabalho justifica-se, pois, pela geração de uma arquitetura de hardware dedicada para o AAC, permitindo-o ser utilizado em aplicações de robótica móvel, além
de estender o seu arcabouço de métodos de raciocı́nio automático com a utilização
de lógica temporal.
É verdade também que conceber uma arquitetura de hardware multiprocessada
funcional é de grande utilidade acadêmica não só para o embarque do AAC, mas
2
também para fornecer uma plataforma experimental para implementação dos mais
diversos algoritmos de inteligência artificial, arquiteturas cognitivas e controle, orientados à robótica móvel, gozando da concorrência e rica instrumentação dessa arquitetura.
O restante deste trabalho divide-se da seguinte forma:
• o Capı́tulo 2 fornece uma fundamentação teórica sobre os métodos de representação de conhecimento utilizados no AAC;
• o AAC é descrito no Capı́tulo 3, onde se explicita como os métodos expostos
no Capı́tulo 2 são utilizados no AAC;
• no Capı́tulo 4 a arquiteura de hardware proposta é descrita: cada nó computacional utilizado é descrito, assim como os protocolos de comunicação utilizados
para conectá-los;
• os resultados de experimentos são expostos no Capı́tulo 5; e
• o Capı́tulo 6 apresenta uma conclusão, onde constam propostas para trabalhos
futuros.
3
Capı́tulo 2
Representação de Conhecimento
De acordo com a definição de Barr e Feigenbaum (1981), citados por Bittencourt
(1990), chama-se de representação de conhecimento o conjunto de métodos formais
compreendendo estruturas de dados e relações interpretativas que, se utilizadas
apropriadamente em um programa, levariam-no a apresentar um comportamento
inteligente. Bittencourt (2006) cita Furbach et al. (1984) para afirmar que uma
representação é composta por três itens, a saber:
• o mundo externo;
• a representação propriamente dita; e
• a relação entre os dois itens acima.
O mundo externo e a representação devem possuir operadores que possibilitem a
manipulação dos seus elementos, e a relação entre estes corpos de conhecimento,
como o autor os denomina, compõe a semântica da representação.
Neste capı́tulo, serão abordados os métodos de representação de conhecimento
utilizados pelo AAC. A primeira representação abordada será a Lógica de Primeira
Ordem (LPO). Em seguida, a Lógica Proposicional Temporal (LTP) é descrita, com
uma subseção dedicada ao algoritmo MetateM para execução fórmulas em LTP.
Depois, o formalismo de representação de quadros será apresentado. Finalmente, os
sistemas especialistas e sistemas baseados em conhecimento serão abordados.
2.1
Lógica de Primeira Ordem (LPO)
A Lógica de Primeira Ordem (LPO), ou Lógica de Predicados estende a Lógica
Proposicional Clássica (LPC) com a introdução de objetos e relações, permitindo
um maior poder de expressão. Assim, o compromisso ontológico (relação entre a
linguagem lógica e a estrutura da realidade que a linguagem pretende representar)
da LPO passa a ser com objetos e a existência de relações entre eles, enquanto a
LPC se compromete ontologicamente apenas com a existência de fatos (Russel e
Norvig 2004).
4
2.1.1
Sintaxe da LPO
A sintaxe da LPO engloba os operadores da LPC, “∧” (e), “∨” (ou), “¬” (negação),
“⇒” (implicação) e “⇔” (equivalência), além das constantes “V” (verdadeiro) e “F”
(falso). A LPO também conta com variáveis e com os quantificadores universal
“∀” e existencial “∃”. Por fim, a sintaxe da LPO inclui sı́mbolos para representar
objetos, relações entre objetos e funções (Bittencourt 2006, Fitting 1996, Russel e
Norvig 2004).
Uma linguagem LPO L pode então ser definida como consistindo de uma tupla
dos seguintes conjuntos (Bittencourt 2006, Fitting 1996):
• C, um conjunto finito ou contável de sı́mbolos de constante;
• P, um conjunto finito ou contável de sı́mbolos de predicado (ou demrelação),
utilizados para representar relações entre os objetos. Todo P ∈ P possui um
número inteiro associado, chamado aridade, que determina a quantidade de
elementos na relação;
• F, um conjunto finito ou contável de sı́mbolos de funções. Todos os F ∈ F
também possuem uma aridade, aqui determinando o número de argumentos
de F ; e
• V, um conjunto de variáveis.
Exemplo 2.1.1. Seja uma linguagem Lparentesco composta pelos conjuntos:
• C parentesco = {Paulo, Maria, Pedro};
• P parentesco = {Cônjuge, Filho, Avó} (todos com aridade dois); e
• F parentesco = {Mãe} (de aridade um).
As seguintes sentenças poderiam ser escritas:
• Filho(Paulo, Maria) ∧ Filho(Paulo, Pedro);
• Cônjuge(Maria, Pedro).
• Avó(Mãe(Maria), Paulo) ⇔ Filho(Paulo, Maria)
A despeito do fato de as sentenças guardarem alguma semelhança com a linguagem
natural e fazerem sentido, nenhuma relação foi feita com a realidade, e portanto,
formalmente, ainda não é possı́vel dizer se são verdadeiras ou falsas.
Outro conceito importante que emerge das definições até aqui apresentadas é a
noção de termo. Segundo Fitting (1996), o conjunto de termos de uma linguagem
lógica 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 não contém variáveis, ele é
dito fechado; caso contrário, ele é aberto).
Uma sentença na LPO que possui apenas um predicado de aridade qualquer ou
que enunciam a igualdade entre dois termos é chamada de sentença atômica, e é a
unidade formadora de qualquer sentença em LPO. A sintaxe da LPO é resumida na
Tabela 2.1 (Russel e Norvig 2004).
Tabela 2.1: Sintaxe da LPO na forma de Backu-Naur.
Sentença
SentençaAtômica
SentençaComplexa
Termo
OperadorBinário
Quantificador
Constante
Predicado
Função
Variável
→ SentençaAtômica | SentençaComplexa
→ Predicado | Predicado( Termo, ... ) | Termo = Termo
→ ( Sentença ) | [ Sentença ]
| ¬ Sentença
| Sentença OperadorBinário Sentença
| Quantificador Variável, ... Sentença
→ Função( Termo, ... )
| Constante
| Variável
→ ∨|∧|⇒|⇔
→ ∀|∃
→ C∈C
→ P ∈P
→ F ∈F
→ v∈V
Quando uma sentença em LPO contém termos abertos aplica-se um mapeamento
σ : V 7→ T , onde T denota o conjunto de termos, que substitui uma ou mais
variáveis da sentença por termos. Este mapeamento é chamado de substituição.
Denota-se a aplicação de uma substituição σ sobre uma sentença S por Sσ. A
despeito do fato de ter como domı́nio o conjunto de variáveis, considera-se possı́vel aplicar uma substituição a um sı́mbolo de constante, tendo como resultado o
próprio sı́mbolo, isto é, para c ∈ C, cσ = c. Para uma função f de aridade n,
[f (t1 , t2 , ..., tn )]σ = f (t1 σ, t2 σ, ..., tn σ). Uma outra notação permite especificar explicitamente as substituições realizadas. Por exemplo, se uma substituição σ substitui
as variáveis x1 , x2 , ..., xn pelos termos t1 , t2 , ..., tn , respectivamente, em uma sentença S, denota-se Sσ alternativamente por S{x1 /t1 , x2 /t2 , ..., x3 /t3 }. Quando uma
substituição σ deve manter inalterada uma determinada variável x, escreve-se tal
substituição como σx (Fitting 1996, Bittencourt 2006).
Para a aplicação de substituições a sentenças quaisquer algumas propriedades
devem ser obedecidas. São elas:
6
• sejam P ∈ P um predicado de aridade n e t1 , t2 , ..., tn um conjunto de termos,
então [P (t1 , t2 , ...tn )]σ = P (t1 σ, t2 σ, ...tn σ);
• para os sı́mbolos “V ” e “F ”, V σ = V e F σ = F ;
• dada uma sentença S, [¬S]σ = ¬Sσ;
• denotando por “” um dos operadores binários “∨”, “∧”, “⇒”, “⇔”, se S1 e S2
são sentenças, então [S1 S2 ]σ = S1 σ S2 σ.
• para uma sentença S, [(∀x)S]σ = [(∀x)(Sσx )];
• para uma sentença S, [(∃x)S]σ = [(∃x)(Sσx )].
Exemplo 2.1.2. Considerando a sentença S = Cônjuge(x, y), a aplicação de uma
substituição σ = {x/Pedro, y/Maria} nesta expressão (escrita Sσ) produz a sentença
atômica Cônjuge(Pedro, Maria).
2.1.2
Semântica da LPO
A semântica de uma linguagem lógica corresponde ao estabelecimento de diretrizes para a atribuição de valores-verdade (verdadeiro ou falso) para expressões
nessa linguagem de acordo com a sua relação com a realidade. Com este fim, os elementos relevantes da realidade devem ser representados dentro do arcabouço formal
da linguagem. A estrututura formal que possibilita esta inclusão na LPO é o modelo.
Um modelo consiste de um conjunto de objetos do mundo real e um mapeamento
que relaciona os elementos da liguagem lógica desenvolvida com estes objetos. Este
mapeamento recebe o nome de interpretação e o conjunto de objeto, de domı́nio
(Russel e Norvig 2004).
Formalmente, de acordo com Fitting (1996), um modelo é uma tupla M = hD, Ii,
onde D é um conjunto não-vazio representando o domı́nio de M e I uma interpretação, que realiza os seguintes mapeamentos:
• todo c ∈ C em um cI ∈ D;
• todo f ∈ F com aridade n em um mapeamento f I : Dn 7→ D; e
• todo p ∈ P com aridade n em uma relação pI ⊆ Dn .
Após o estabelecimento do coneceito de modelo, Fitting (1996) prossegue com a
construção da semântica da LPO através da definição de atribuições, que são mapeamentos do tipo A : V 7→ D, do conjunto de variáveis sobre o domı́nio do modelo.
Cada atribuição A possui um mapeamento B associado chamado de variante-x de
A, que executa a atribuição denotada por A mantendo a variável x inalterada. O
autor ressalta que as definições de atribuição e substituição são similares, porém
geralmente não idênticas, exceto no caso em que o domı́nio D é exatamente o conjunto de termos fechados de L, caso em que o modelo M é denominado modelo de
7
Herbrand. Aqui se considerará este último caso, e portanto, no procedimento de
determinação de valores-verdade a seguir, substituições serão utilizadas no lugar das
atribuições originalmente utilizadas pelo autor.
Assim, se M = hD, Ii é um modelo de Herbrand da linguagem L = hC, P, F, Vi,
e σ é uma substituição, então a atribuição de valores verdadeiro ou falso para
uma sentença (Sσ)I é realizada de acordo com o seguinte (Fitting 1996):
• para as constantes “V ” e “F ”, tem-se, respectivamente, (V σ)I = verdadeiro
e (F σ)I = falso;
• sejam P ∈ P e t1 , t2 , ..., tn termos de L, {[P (t1 , t2 , ..., tn )]σ}I = verdadeiro
se e somente se h(t1 σ)I , (t2 σ)I , ..., (tn σ)I i ∈ P I ;
• se S é uma sentença, [¬(Sσ)]I = ¬(Sσ)I ;
• se S1 e S2 são sentenças e “” representa qualquer operador binário, [(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 sentença S em LPO e uma substituição σ, pode-se definir um mapeamento da dupla hM, Sσi sobre o conjunto
{verdadeiro, falso} chamado de consequência lógica, e escrito como na Equação
(2.1). Esta equação (lida “S é consequencia lógica 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 linguagem
Lparentesco , agora já se dispõe de recursos para avaliar o valor das sentenças apresentadas naquele exemplo. É importante observar que, pela definição recursiva dos
termos, a presença de um sı́mbolo de função gera um domı́nio infinito. Considere-se
um modelo de Herbrand M que consiste de um domı́nio
D = C parentesco ∪ {Mãe(c) | c ∈ C parentesco } ∪ {Mãe(Mãe(c)) | c ∈ C parentesco } ∪ . . . ,
e de uma intrepretação I que produz os seguintes conjuntos:
• CônjugeI = {(P edro, M aria), (M aria, P edro)};
• FilhoI = {(P aulo, P edro), (P aulo, M aria), (P edro, Mãe(P edro)),
(Mãe(P edro), Mãe(Mãe(P edro))), . . . , (M aria, Mãe(M aria)),
(Mãe(M aria), Mãe(Mãe(M aria))), . . .};
8
• AvóI = {(Mãe(M aria), P aulo), (Mãe(P edro), P aulo),
(Mãe(Mãe(M aria)), M aria), . . . , (Mãe(Mãe(P edro)), P edro)}.
Assim a sentença
Avó(Mãe(Maria), Paulo) ⇔ Filho(Paulo, Maria)
é verdadeira, pois (Mãe(Maria), Paulo) ∈ AvóI , o que faz o lado esquerdo da equivalência ser verdadeiro, e (Paulo, Maria) ∈ FilhoI fazendo o lado direito também
verdadeiro, portanto o resultado da operação bicondicional é verdadeiro.
Dadas duas sentenças diferentes tais que pelo menos uma possui uma variável,
chama-se de unificação o procedimento utilizado para encontrar uma substituição
que, quando aplicada a ambas, as torne logicamente idênticas. Esta substituição, por
sua vez, é denominada unificadora das duas sentenças. A unificação pode também
falhar, caso não haja uma substituição que torne as sentenças logicamente idênticas.
Isso pode ocorrer devido a uma nomeação inadequada de variáveis, conforme o
Exemplo 2.1.4 ilustra. Para evitar esta última ocasião deve-se realizar um processo
de padronização de variáveis, que renomeia variáveis antes da aplicação da unificação
de modo que tenham um nome único (Fitting 1996, Russel e Norvig 2004).
Exemplo 2.1.4. Utilizando a notação de Russel e Norvig (2004), tem-se
UNIFICAR(Filho(Paulo, x), Filho(y, Pedro)) = {x/Maria, y/Paulo}
Caso as variáveis da expressão acima tivessem o mesmo nome, teria-se
UNIFICAR(Filho(Paulo, x), Filho(x, Pedro)) = f alha,
pois não há uma substituição que atribua um elemento do domı́nio a x e unifique as
sentenças.
2.2
Lógica Temporal Proposicional (LTP)
A Lógica Temporal Proposicional (LTP) é também uma extensão à LPC. O compromisso ontológico da LTP é com os fatos que são verdadeiros em instantes de
tempo tomados relativamente ao tempo atual.
A LTP tem sua origem no trabalho de Pnueli (1977), quando este apresentou um
sistema formal de raciocı́nio temporal aplicado à verificação de programas. Este
sistema formal foi chamado de Lógica Temporal Linear (LTL). Segundo o autor,
esta é uma abordagem unificada, uma vez que pode ser aplicada tanto à verificação de programas sequenciais, quanto à de programas paralelos. E para lograr tal
unificação, Pnueli introduz duas definições:
• Invariância: utilizada para expressar propriedades dos programas que se mantém válidas durante toda a execução.
9
• Eventualidade: definição mais importante, segundo o próprio autor, a eventualidade representa uma implicação temporal, isto é, uma dada situação A
assegura que eventualmente uma outra situação B irá ocorrer.
No trabalho de Gabbay et al. (1980) a LTP foi proposta como uma forma proposicional da LTL sobre modelos em tempo discreto, contando com os operadores de
próximo instante “X” (que permite expressar o que é ou não verdadeiro no próximo
instante) e “até que”“U ” (que possibilita escrever expressões do tipo, “a propriedade
A é verdadeira até que B torne-se verdadeira”) (Konur 2010).
Esta seção se dedicará à descrição da LTP seguindo o formato da seção anterior: primeiro a sintaxe da LTP será definida, e então a semântica. Finalmente,
o algoritmo MetateM será apresentado, fornecendo as diretrizes para a execução
de fórmulas em LTP. O restante da seção utilzou como referências os trabalhos de
Michael Fisher (Fisher 2011), (Fisher 1996) e (Fisher 2006). Para evitar citações
repetitivas ao longo do texto, estas foram omitidas.
2.2.1
Sintaxe da LTP
A sintaxe da LTP contém os operadores da LPC (“∧”, “∨”, “¬”, “⇒” e “⇔”)
e as constantes “V ” e “F ”. Em adição a estes, operadores temporiais estendem a
expressividade da LPC, incorporando o tempo na estrutura da linguagem. Estes
operadores temporais são:
• o operador “inı́cio”;
• os operadores unários de próximo instante “ e”, de invariância “” e de eventualidade “♦”; e
• os operadores binários “U” e “W”.
Um conjunto de sı́mbolos proposicionais P determina o alfabeto disponı́vel para a
criação de sentenças 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 sentenças de LTP a
serem desenvolvidas devem descrever as relações temporais entre os dias da semana,
o conjunto de sı́mbolos proposicionais é formado por {segunda-feira, terça-feira,
quarta-feira, quinta-feira, sexta-feira, sábado, domingo}. O operador de inı́cio pode
ser utilizado nesse contexto para estabelecer um dia inicial a ser considerado no
restante da análise. Por exemplo, se o dia inicial é segunda-feira, a sentença em
LTP correspondente é mostrada na Equação (2.2).
inı́cio ⇒ segunda-feira
10
(2.2)
O operador de próximo instante (“ e”) é utilizado para se expressar algo sobre
o próximo instante de tempo. A base temporal não é determinada na sintaxe da
linguagem, isto é, o operador pode se referir tanto ao próximo segundo, como ao
próximo ano, dependendo do problema.
Exemplo 2.2.2. A expressão“amanhã será domingo”é escrita utilizando o operador
de próximo instante conforme a sentença
edomingo
Exemplo 2.2.3. Pode-se estender o exemplo anterior para ilustrar a criação de
regras em LTP. A sentença “se hoje é sábado então amanhã é domingo” pode ser
expressa em LTP como na sentença abaixo:
sábado ⇒ edomingo
A invariância mantém na LTP a sua utilidade original de representar fatos que
conservarão um estado lógico ao longo de todos os instantes futuros.
Exemplo 2.2.4. Utilizando como base o Exemplo (2.2.3), gera-se a Equação (2.3),
que expressa a sentença “sempre que hoje for sábado, amanhã será domingo”.
(sábado ⇒ edomingo)
(2.3)
O operador de eventualidade, conforme mencionado no inı́cio desta seção, é também um operador unário. Ele é utilizado para expressar situações que irão certamente ocorrer em algum instante futuro, mas não se especifica esse instante.
Exemplo 2.2.5. Expressa-se “sempre que hoje for quinta-feira então eventualmente
será domingo” em LTP como na Equação (2.4).
(quinta-feira ⇒ ♦domingo)
(2.4)
Para completar a descrição da sintaxe da LTP, restam os dois operadores binários
“U” (até que) e “W” (a menos que). O operador “U” é utilizado quando uma situação
é verdadeira até que uma outra ocorra. O operador “W” difere sutilmente do “U”:
o “a menos que” é aplicado em casos onde não é garantido que o segundo operando
venha a ser tornar verdadeiro. Assim, “W” pode ser utilizado para substituir “U”,
mas a recı́proca não é válida.
Exemplo 2.2.6. A expressão “hoje é sábado até que seja domingo”, por exemplo,
é escrita com este operador conforme a Equação (2.5).
sábado U domingo
Um resumo da sintaxe da LTP é mostrado na Tabela 2.2.
11
(2.5)
Tabela 2.2: Sintaxe da LTP na forma de Backu-Naur.
Sı́mbolo
Sentença
OperadorUnário
OperadorBinário
2.2.2
→
→
|
|
|
→
→
Elemento de um conjunto de sı́mbolos proposicionais.
( Sentença ) | [ Sentença ]
V | F | inı́cio | Sı́mbolo
OperadorUnário Sentença
Sentença OperadorBinário Sentença
¬ | | e| ♦
∨|∧|⇒|⇔|U |W
Semântica da LTP
Assim como na LPO, a semântica na LTP também depende do conceito de modelo. Um modelo em LTP é dado por uma seqüência de mundos, indexados por
instantes discretos, em cada um dos quais um determinado conjunto de sı́mbolos
proposicionais (subconjunto de P) é verdadeiro. A Tabela 2.3 ilustra esta definição.
Nesta tabela vê-se que no instante i − 1, os sı́mbolos p, s, t e w são verdadeiros. No
instante i, apenas s e w são verdadeiros, e em i + 1 nenhum sı́mbolo é verdadeiro.
Tabela 2.3: Modelo em LTP simplificado.
Índice Temporal
Sı́mbolos Verdadeiros
···
···
i−1
p, s, t, w
i
s, w
i+1
···
···
Formalmente, um modelo M consiste de uma tripla, como a mostrada na Equação
(2.6), onde S denota o conjunto de ı́ndices temporais, R uma relação de acessibilidade temporal que realize a serialização de S e π uma aplicação de S sobre 2P .
M = hS, R, πi
(2.6)
Uma estrutura deste tipo é chamada Estrutura de Kripke. A relação π : S 7→ 2P
deve ser definida para sentenças em LTP de modo a associar um ı́ndice temporal de
i ∈ S a um subconjunto de P se, e somente se, este subconjunto for inteiramente
composto por sı́mbolos verdadeiros no tempo i. Assim, para a definição da semântica
das sentenças em LTP, este mapeamento deve ser definido para cada tipo de sentença
presente na Tabela 2.2.
Conforme se verificou no desenvolvimento da sintaxe da LTP, os operadores aqui
definidos referem-se apenas ao futuro. Portanto, o conjunto S é dado como o conjunto dos números naturais, e a relação de serialização R em S deve ser tal que os
ı́ndices temporais sejam serializados em ordem crecente. Todavia, por simplicidade,
a relação R é omitida da expressão do modelo, e este é dado, então, pela Equação
(2.7).
M = hN, πi
(2.7)
12
Uma visualização dessa concepção mais formal de um modelo é mostrada na
Tabela 2.4.
Tabela 2.4: Representação de um modelo em LTP.
···
···
···
→
i−1
→
i
→ i+1
↓
π(i − 1)
↓
↓
π(i)
↓
↓
π(i + 1)
↓
{p, s, t, w}
{s, w}
{}
→
···
···
···
A atribuição efetiva de valores-verdade a sentenças da LTP ocorre então através
de um mapeamento similiar ao definido na Equação (2.1) para sentenças 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 modelo
M = hN, πi, um instante i e uma sentença da LTP, o mapeamento
|=: hM, i, Si 7→ {verdadeiro, falso}
é escrito como na Equação (2.8).
hM, ii |= S
(2.8)
O restante desta subseção será dedicado a construir a semântica das expressões
da Tabela 2.2.
Sentenças Atômicas
Sentenças atômicas em LTP são sentenças compostas por apenas um sı́mbolo
proposicional. A semântica de uma sentença atômica p ∈ P é dada pela Equação
(2.9).
hM, ii |= p se, e somente se, p ∈ π(i)
(2.9)
Sentenças com Operadores Clássicos
Sejam S1 e S2 duas sentenças da LTP. A semântica de sentenças com operadores
clássicos é dada na Equação (2.10) (onde “sse” é uma abreviação de “se, e somente
se”).
hM, ii |= ¬S1
hM, ii |= S1 ∧ S2
hM, ii |= S1 ∨ S2
hM, ii |= S1 ⇒ S2
hM, ii |= S1 ⇔ S2
sse
sse
sse
sse
sse
hM, ii |= S1 e
hM, ii |= S1 ou
se hM, ii |= S1 então
hM, ii |= S1 sse
13
hM, ii 2 S1
hM, ii |= S2
hM, ii |= S2
hM, ii |= S2
hM, ii |= S2
(2.10)
Sentenças com Operadores Temporais
Para sentenças com operadores temporais, a atribuição de valores-verdade é realizada através da manipulação do ı́ndice temporal de acordo com a função do operador
temporal, seguido da verificação, no instante resultante, de se a sentença é ou não
consequência lógica do modelo. A seguir, a semântica de cada operador temporal
será apresentada e ilustrada.
• Operador de Inı́cio (“inı́cio”)
Em qualquer modelo, o operador “inı́cio” é satisfeito apenas no marco zero,
conforme a Equação (2.11).
hM, ii |= inı́cio sse i = 0
(2.11)
A Tabela 2.5 ilustra o exposto acima.
Tabela 2.5: Representação da semântica do operador de inı́cio.
inı́cio ⇒ φ
0
↓
π(0)
↓
{φ}
→
→
1
↓
π(1)
↓
{}
→
2
↓
π(2)
↓
{}
3
↓
π(3)
↓
→
{}
4
↓
π(4)
↓
→
{}
5
↓
π(5)
↓
→
{}
···
···
···
···
• Operador de Próximo Instante (“ e”)
Uma sentença “ eS” é verdadeira em um modelo M se, e somente se, ela for
consequência lógica do modelo no próximo instante. Isso está formalmente
representado na Equação (2.12) e ilustrado na Tabela 2.6.
hM, ii |= eS sse hM, i + 1i |= S
(2.12)
Tabela 2.6: Representação da semântica do operador de próximo instante.
···
···
···
···
→ i−1 →
eφ
i
→ i+1
→ i+2
↓
π(i − 1)
↓
↓
π(i)
↓
↓
π(i + 1)
↓
↓
π(i + 2)
↓
{}
{}
{φ}
{}
→ i+3
↓
π(i + 3)
↓
{}
→
···
···
···
···
• Operador de Eventualidade (“♦”)
Uma eventualidade representa um indeterminismo sobre em que instante de
tempo o seu operando será satisfeito. Ela representa uma restrição: a sentença
14
do seu único argumento será satisfeita em algum momento do futuro (Tabela
2.7). A Equação (2.13) representa este indeterminismo através do operador
“∃”.
hM, ii |= ♦S sse, existe j ∈ N tal que (j ≥ i) ∧ hM, ji |= S
(2.13)
Tabela 2.7: Representação da semântica do operador de eventualidade.
···
···
···
···
♦φ
→ i−1 →
i
↓
π(i − 1)
↓
↓
π(i)
↓
{}
{}
→
···
···
···
→ i+j
→ i+j+1
↓
π(i + j)
↓
↓
π(i + j + 1)
↓
{φ}
{}
→
···
···
···
···
Quando a desigualdade da Equação (2.13) é estrita, denota-se o operador de
eventualidade por ♦+ , e a sua semântica é levemente alterada, produzindo a
Equação (2.14).
hM, ii |= ♦+ S sse, existe j ∈ N tal que (j > i) ∧ hM, ji |= S
(2.14)
• Operador de Invariância (“”)
A Equação (2.15) estabelece a semântica do operador de invariância. Em
palavras, a expressão “S” é consequência lógica do modelo M no instante
i se, e somente se, “S” for consequência lógica de M para todos os instantes
posteriores a i (inclusive) (Tabela 2.8).
hM, ii |= S sse, para todo j ∈ N, (j ≥ i) ∧ hM, ji |= S
(2.15)
Tabela 2.8: Representação da semântica do operador de invariância.
···
···
···
···
→ i−1 →
φ
i
↓
π(i − 1)
↓
↓
π(i)
↓
↓
π(i + 1)
↓
↓
π(i + 2)
↓
{}
{φ}
{φ}
{φ}
→ i+1
→ i+2
→ i+3
→
↓
π(i + 3)
↓
{φ}
···
···
···
···
De maneira similar ao operador de eventualidade, o operador de invariãncia
também possui uma variante para a utilização de uma desigualdade estrita
na Equação 2.15. Esta variante é denotada por “+ ”, e é dada pela Equação
(2.16).
hM, ii |= + S sse, para todo j ∈ N, (j > i) ∧ hM, ji |= S
15
(2.16)
• Operador “Até Que” (“U”)
Se em um dado modelo certa sentença “S1 ” é verdadeira até que uma outra
sentença “S2 ” se torne verdadeira, fazendo a primeira deixar de sê-lo e assim
se mantenha (Tabela 2.9), então a expressão hM, ii |= S1 US2 é consequência
lógica do modelo (ver Equação (2.17)).
hM, ii |= S1 US2 sse, (existe j ∈ N tal que j ≥ i ∧ hM, ji |= S2 ∧
(para todo k ∈ N, se i ≤ k < j então hM, ki |= S1 )
(2.17)
Tabela 2.9: Representação da semântica do operador “até que”.
···
···
···
···
→ i−1 →
φU ψ
i
↓
π(i − 1)
↓
↓
π(i)
↓
↓
π(i + 1)
↓
↓
π(i + 2)
↓
{}
{φ}
{φ}
{ψ}
→ i+1
→ i+2
→ i+3
→
↓
π(i + 3)
↓
{}
···
···
···
···
• Operador “A Menos Que” (“W”)
Muito proximamente relacionado ao operador “U”, o operador “W” tem sua
semântica mostrada na Equação (2.18) em termos deste operador.
hM, ii |= S1 WS2 sse, (hM, ii |= S1 US2 ∨ S1 )
(2.18)
A Tabela 2.10 ilustra dois casos possı́veis para o operador “a menos que”: um
em que a expressão do seu segundo argumento nunca se torna verdadeira e
outro em que isso ocorre (caso em que a semântica é idêntica à do operador
“U”).
Tabela 2.10: Representação da semântica do operador “até que”.
···
···
···
···
···
···
···
···
→ i−1
→
φWψ
i
→
i+1
→
i+2
→ i+3
↓
π(i − 1)
↓
↓
π(i)
↓
↓
π(i + 1)
↓
↓
π(i + 2)
↓
{}
{φ}
{φ}
{φ}
→ i−1 →
{φ}
φWψ
i
→ i+1
→ i+2
↓
π(i)
↓
↓
π(i + 1)
↓
↓
π(i + 2)
↓
→ i+3
↓
π(i − 1)
↓
{}
{φ}
{φ}
{ψ}
16
↓
π(i + 3)
↓
↓
π(i + 3)
↓
{}
···
···
···
···
···
→ ···
···
···
→
2.2.3
O Algoritmo MetateM
O algoritmo MetateM fornece um procedimento para a execução de uma sentença em LTP. A execução de sentenças em LTP corresponde ao processo de geração
de um modelo, isto é, geração de uma sequência de conjuntos de sentenças proposicionais indexados por um ı́ndice temporal discreto. Este processo de construção
utiliza a abordagem de futuro imperativo, que consiste na construção iterativa a
partir do estado inicial.
Forma Normal Separada (FNS)
A Forma Normal Separada (FNS) é uma representação de uma sentença complexa
da LTP que consiste de uma conjunção invariante de várias fórmulas mais simples.
A FNS é escrita conforme a sentença da Equação 2.19.
^
Ri
(2.19)
i
Cada Ri é chamado de regra e possui um dos formatos a seguir:
start ⇒
g
^
a=1
g
^
r
_
lb
b=1
r
_
ka ⇒ e
(regra de inı́cio);
lb
(regra de próximo instante);
b=1
ka ⇒ ♦l
(regra de eventualidade).
a=1
Uma sentença na FNS é apresentada, por questões de clareza, com as suas regras
listadas sequencialmente. Assim, a sentença na FNS (R1 ∧ . . . ∧ Rn ) é escrita:
R1
···
Rn .
Encadeamento Adiante: Regras de Estado Inicial
O MetateM utiliza um mecanismo de encadeamento adiante para executar uma
sentença em LTP: se o conjunto de sı́mbolos verdadeiros no instante atual tornar
verdadeira a sentença do lado esquerdo da implicação de alguma regra Ri da Equação
(2.19), então a sentença do lado direito desta regra é executada.
O procedimento continua, aplicando uma estratégia passo-a-passo, a partir do
estado inicial, para a construção do modelo. Assim, dada uma sentença da LTP
escrita na FNP, o primeiro passo é avaliar qual é o estado inicial do modelo, isto é,
a partir das regras de inı́cio da sentença definir o que é verdadeiro no intante inicial.
17
Uma vez definido o estado inicial, o encadeamento é iniciado: todas as premissas
das regras restantes (de próximo instante e de enventualidade) que são consequências
lógicas do modelo no instante inicial têm suas consequências executadas.
Encadeamento Adiante: Regras de Próximo Instante
Seja uma regra de próximo instante dada por
P ⇒ eC.
Considerando que o ı́ndice do tempo atual é i, se hM, ii |= P , então hM, ii |= eC,
o que, de acordo com a semântica do operador “ e”, equivale a hM, i + 1i |= C. O
modelo resultante é mostrado na Tabela 2.11.
Tabela 2.11: Modelo gerado pela execução de uma sentença de próximo instante.
···
···
···
···
→ i−1 →
i
↓
π(i − 1)
↓
↓
π(i)
↓
→ i+1
↓
π(i + 1)
↓
→ i+2
↓
π(i + 2)
↓
{}
{P }
P ⇒ eC
{C}
{}
→ i+3
↓
π(i + 3)
↓
{}
→
···
···
···
···
Exemplo 2.2.7. Seja a sentença da LTP na FNS
inı́cio ⇒ domingo
domingo ⇒ esegunda-feira
segunda-feira ⇒ eterça-feira.
A execução desta sentença produz o estado inicial composto apenas pelo sı́mbolo
domingo. Com isso, inicia-se o encadeamento. Tem-se que
hM, 0i |= domingo,
logo
hM, 1i |= segunda-feira.
Esta última expressão, por sua vez, implica em
hM, 2i |= terça-feira.
Encadeamento Adiante: Regras de Eventualidade
Um ponto crucial do algoritmo MetateM é o tratamento de regras de eventualidade. A estratégia adotada é uma vez que a premissa de uma regra de eventualidade é satisfeita, a enventualidade na sua consequência também deverá sê-lo
18
tão logo quanto possı́vel. Isto é, dada uma regra P ⇒ ♦C e um modelo hN, πi, se
P ∈ π(i), C deverá ser adicionado a π(t) no primeiro t ≥ i em que ¬C ∈
/ π(t). O
Exemplo 2.2.8, a seguir, demonstra a estratégia do MetateM para a execução de
eventualidades.
Exemplo 2.2.8. Sejam um modelo hN, πi e as regras a seguir:
inı́cio ⇒ domingo
inı́cio ⇒ ¬segunda-feira
inı́cio ⇒ ¬terça-feira
domingo ⇒ ♦segunda-feira
domingo ⇒ ♦terça-feira
domingo ⇒ e¬terça-feira.
No tempo t = 0, tem-se
π(0) = {domingo, ¬segunda-feira, ¬terça-feira},
segundo as regras de inı́cio. Assim, ainda em t = 0 as três regras seguintes têm suas
premissas satisfeitas (pelo sı́mbolo domingo). As regras de eventualidade estabelecem que eventualmente os sı́mbolos segunda-feira e terça-feira serão verdadeiros.
Mas em t = 0, tem-se as restrições ¬segunda-feira e ¬terça-feira, logo as eventualidades não podem ser imediatamente satisfeitas. Devido à regra de próximo instante
domingo ⇒ e¬terça-feira, em t = 1, a restrição ¬terça-feira é mantida, mas a restrição sobre segunda-feira não é, possibilitando a satisfação de uma das eventualidades.
Portanto:
π(1) = {segunda-feira, ¬terça-feira}.
Por fim, em t = 2, a restrição sobre terça-feira não é mais mantida (nenhuma regra
propaga a negação ¬terça-feira), possibilitando a satisfação da última eventualidade:
π(2) = {terça-feira}.
(2.20)
Verificação de Ciclo
Durante a execução de fómulas em LTP pode ocorrer que, a partir de algum
i ≥ 0, tenha-se sempre π(i) = π(i + T ), onde T é um inteiro positivo. Isso significa
que a execução entrou em um ciclo. Ciclos não são necessariamente indesejáveis:
eles podem fazer parte da execução. Em geral, ciclos que impedem a satisfação
de eventualidades são considerados indesejáveis, enquanto que ciclos que em algum
ponto satisfazem todas as eventualidades são considerados como parte da execução,
ou desejáveis.
19
Retrocesso
Conforme se vê nas regras de inı́cio e próximo instante da FNS na Equação (2.19),
estas podem conter disjunções em seus respectivos lados direitos (consequentes).
Estas disjunções representam escolhas que devem ser feitas ao longo da execução
de uma fórmula. Assim, ao encontrar uma disjunção no lado direito de uma regra,
escolhe-se um dos disjuntos para adicionar ao conjunto de sı́mbolos verdadeiros do
instante correspondente. Mas os demais disjuntos são guardados, pois se a escolha
inicial conduzir a alguma inconsistência, deve-se retroceder ao ponto da escolha e
escolher outro disjunto. Se todas as escolhas falharem, significa que as regras são
inconsistentes.
Pseudo-Código do MetateM
O pseudo-código do MetateM é mostrado no Algoritmo 1. Neste algoritmo
aplicase a seguinte simbologia:
• E é o conjunto de regras de eventualidade;
• P o conjunto de regras de próximo 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 não-satisfeitas até i.
Considera-se também que as eventualidades não podem ser satisfeitas imediatamente, isto é, utiliza-se a eventualidade estrita, representada pelo sı́mbolo “♦+ ”.
2.3
Quadros
Minsky (1974) propôs um método de representação de conhecimento baseado em
estruturas de dados cujos nós mantinham entre si relações e informações que ajudavam a decidir como e quando explorar tais relações. Essas estruturas de dados foram
denominadas quadros, e foram utilizados pelo autor como descritores de situações
estereotı́picas.
Exemplo 2.3.1. Conforme o próprio Minsky em um trabalho posterior (Minsky
1984), um exemplo de situação estereotı́pica seria estar em um certo quarto ou um
certo tipo de festa: a situação é inicialmente representada por um quadro genérico,
estereotı́pico, que possui caracterı́sticas comuns a todos os tipos de quartos ou festas,
mas à medida que as percepções vão sendo adquiridas, o quadro é atualizado para
descrever aquela situação especı́fica (estar em um quarto especı́fico ou em um tipo
de festa especı́fico).
20
Algoritmo 1 Algoritmo MetateM.
Entrada: I, um conjunto de regras de inı́cio;
Entrada: P, um conjunto de regras de próximo instante;
Entrada: E, um conjunto de regras de eventualidade;
1: função MetateM(I,P,E)
2:
S0 ← {F | (inı́cio ⇒ F ) ∈ I}
3:
Ei ← {}
4:
enquanto verdadeiro faça
5:
C ← {G | (P ⇒ eG) ∈ P ∧ P ∈ Si }
6:
Ei+1 ← Ei ∪ {H | (Q ⇒ ♦+ H) ∈ E ∧ Q ∈ Si }
7:
para cada V ∈ Ei+1 faça
8:
se V ∧ C é consistente então
9:
C ←C ∧V
10:
remove V de Ei+1
11:
fim se
12:
fim para
13:
Si+1 ← escolha de atribuição consistente com C
14:
se Si+1 ≡ {} ou ∧N
k=0 (V ∈ Ei+k ) então
15:
Retrocede até escolha anterior
16:
fim se
17:
fim enquanto
18: fim função
Segundo Bittencourt (2006), a estrutura dos quadros é formada por campos que
recebem preenchedores (do inglês, “fillers”), que são simplesmente valores que são
utilizados para descrever o objeto representado pelo quadro. Os valores dos quadros
também possuem algumas propriedades, denominadas facetas, que são usadas para
determinar dados default, ou de exceção, o tipo de dados esperado e informações
para calcular o valor do atributo. Adicionalmente, os valores dos quadros podem
receber outros quadros, gerando uma rede de dependências.
Exemplo 2.3.2. Bittencourt (2006) dá um exemplo de um quadro “Sala” que possui
uma relação de herança com o quadro “Cômodo”. O autor apresenta os quadros e
suas relações de uma forma gráfica, que é apresentada aqui na Figura 2.1. Na
figura, o quadro é referido por sua denominação original em inglês: “frame”. O
campo 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
“Cômodo”. Assim, a partir do quadro “Sala” um procedimento de inferência pode
deduzir o seu formato e altura, por exemplo. Informações na coluna “Se-necessário”
estabelecem diretrizes para o cálculo de valores de atributos.
Hayes (1979) ressalta que a utilização de quadros, além da utilidade representacional (a que o autor se refere como “metafı́sica”), possui também importância
21
Figura 2.1: Exemplo de quadros (Bittencourt 2006).
prática (“heurı́stica” ou “de implementação”, nas palavras do autor), uma vez que
a representação através de quadros facilitia o armazenamento e a recuperação do
conhecimento em um sistema computacional por já possuir uma estrutura adequada
a este fim.
2.4
2.4.1
Sistemas Baseados em Conhecimento e Sistemas Especialistas
Sistemas de Produção
Os Sistemas de Produção são sistemas que representam o conhecimento por meio
de um conjunto de regras chamadas regras de produção. Os sistemas de produção
iniciaram-se com Post (1943), que propôs um sistema consistindo de regras de modificação sintática sobre uma memória de trabalho (MT) composta de uma cadeias
de caracteres. Um interpretador era responsável pela modificação da memória de
trabalho de acordo com as regras de modificação. A estrutura básica de sistemas de
produção é ilustrada na Figura 2.2 (Bittencourt 2006).
Figura 2.2: Estrutura genérica de um sistema de produção de regras.
22
Exemplo 2.4.1. Para exemplificar a execução de um sistema de produção de Post,
sejam uma MT composta pela sequência de caracteres “123” e as regras de modificação sintática mostradas na Tabela 2.121 . Os caracteres “-”, “•” e “*” representam,
respectivamente, um caractere nulo, um caractere de fim de sequência e um caractere
especial.
Tabela 2.12: Exemplo de regras de produção de um sistema de Post
Índice da Regra
Regra
1
∗ij → j ∗ i
2
∗i → i∗
3
∗• → -•
4
-→∗
Estas regras propõem modificações sintáticas em cadeias de caracteres. O interpretador é o elemento reponsável pela realização das alterações, atuando da seguinte
forma: se o padrão do lado esquerdo de uma regra é encontrado na memória de trabalho, então o trecho da memória de trabalho que correspondeu àquele padrão é
modificado para corresponder agora ao lado direito da regra. A Tabela 2.13 mostra
algumas etapas da execução do interpretador.
Tabela 2.13: Exemplo de Execução de um Sistema de Post.
Padrão do Lado Esquerdo
Regra Utilizada
Corresponde na
pelo Interpretador
Resultante
1: ∗ i j → j ∗ i
Não
123•
2: ∗ i → i ∗
Não
123•
3: ∗ • → - •
Não
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
Não
23 ∗ 1•
2: ∗ i → i ∗
Sim
231 ∗ •
1: ∗ i j → j ∗ i
Não
231 ∗ •
2: ∗ i → i ∗
Não
231 ∗ •
3: ∗ • → - •
Sim
231•
1
Exemplo extraı́do de http://www1.se.cuhk.edu.hk/ seem5750/Lecture 2.pdf; Acessado a
10/06/2014, às 9:25
23
2.4.2
Sistemas Baseados em Conhecimento e Sistemas Especialistas
Utilizando a estrutura funcional dos sistemas de Post, os sistemas de produção
ganham generalidade quando passam a utilizar um método de representação de
conhecimento como linguagem formal para a criação da sua base de regras e da sua
MT. Nesse caso, segundo Bittencourt (2006), tem-se um Sistema Especialista (SE).
Segundo o autor, um SE tem o propósito de mimetizar o atuação de um especialista
humano em um domı́nio bastante especı́fico. A base de regras e a MT compõem a
base de conhecimento (BC) do SE e o interpretador é substituı́do por um Motor de
Inferência (MI). Uma linguagem formal tı́pica para representação de conhecimento
em SE é a LPO. As regras consistem, nesse caso, de cláusulas definidas da LPO que,
segundo Russel e Norvig (2004), são sentenças implicativas do tipo Condição ⇒
Ação. Assim, as premissas (ou condições) das regras devem ser comparadas com a
MT a fim de decidir se a MT deve ser alterada de acordo com as consequências da
regra. Portanto, o interpretador agora funciona como um mecanismo de inferência
lógica. Esse processo de inferência é realizado em um ciclo do MI, que consiste de
três etapas (Brachman e Levesque 2004):
• reconhecer: encontrar dentre as regras aquelas cujas premissas são satisfeitas
pela MT (gerando o conjunto de conflitos);
• resolver conflitos: escolher uma regra do conjunto de conflitos;
• agir: realizar as alterações na memória de trabalho de acordo com a consequência da regra selecionada.
Segundo Brachman e Levesque (2004), os Elementos da Memória de Trabalho
(EMT) de um SE consiste de tuplas contendo o tipo do elemento, seus atributos e
os valores destes atributos. O formato geral de um EMT é dado na Figura 2.3, onde
tipo, atributoi e valori , com 1 ≤ i ≤ n, são sentenças atômicas de LPO.
Figura 2.3: Formato Geral de um EMT.
O autor ainda complementa afirmando que este formato equivale à sentença complexa de LPO
∃x [tipo(x) ∧ atributo1 (x) = valor1 ∧ . . . ∧ atributo1 (x) = valor1 ],
com tipo sendo um predicado unário, os atributos sendo funções unárias e os valores
sendo objetos.
O formato de EMT apresentado é útil para ilustrar a estrutura genérica de um
EMT, similar a uma estrutura de dados utilizada em programação de computadores.
Mas diferentes implementações de SEs podem utilizar uma linguagem diferente para
expressar esta estrutura.
24
Exemplo 2.4.2. Exemplos de EMT são mostrados na Figura 2.4.
Figura 2.4: Exemplos de Elementos da Memória de Trabalho.
Ainda conforme Brachman e Levesque (2004), a estrutura de uma regra da BC de
um SE é aquela da Figura 2.5. A premissa das regras é mostrada nesta figura como
sendo formada por uma conjunção de elementos com estruturas que se assemelham
bastante àquela dos EMT. A única diferença está no fato de que aos atributos agora
são associadas especificações ao invés de valores. As especificações estabelecem as
restrições que os atributos correspondentes nos EMT devem obedecer para que a
premissa da regra seja satisfeita e a mesma possa ser incluı́da no conjunto de conflito.
Figura 2.5: Estrutura de uma regra de produção lógica: “n”, “m” e “k” são interios
positivos quaisquer.
As especificações podem consistir de uma sentença atômica, uma variável, uma
expressão (escrita entre colchetes), um teste (uma lista de operadores relacionais
e valores escrito entre chaves) ou de uma conjunção de especificações. Conforme
já foi mencionado anteriormente, o MI, na etapa de reconhecimento, pesquisa a
premissa de cada regra na MT, testando se há correspondência com algum EMT.
Esta correspondência ocorre quando há algum EMT com o mesmo tipo da premissa,
e se os atributos desse EMT obedecem às restrições impostas pelas especificações da
premissa em questão.
Supondo que houve uma correspondência de tipo entre uma (ou parte de uma)
premissa e um EMT, a verificação prossegue de acordo com a natureza da especificação:
• se uma especificação consiste de uma sentença atômica ou de uma expressão,
uma comparação de igualdade é realizada com os atributos correspondentes
do EMT;
• caso a especificação consista de um teste, compara-se o valor do atributo do
EMT com os valores fornecidos pela especificação de acordo com os operadores
relacionais contidos nesta especificação; e
• se a especificação contiver uma variável deve-se buscar uma substituição tal
que, satisfeitos os itens anteriores, torne a premissa verdadeira após sua aplicação (isto é, na presença de variáveis deve-se executar um processo de unificação,
25
aplicando a substituição resultante na premissa) (Brachman e Levesque 2004,
Russel e Norvig 2004).
Já a estrutura da conseqüência de uma regra de produção deve conter a alteração
a ser realizada na memória de trabalho. Existem três possibilidades de alteração
para uma regra:
• ADICIONA (tipo atributo1 : valor1 atributo2 : valor2 . . . atributon : valorn ):
adiciona um determina elemento à memória de trabalho;
• REMOVE i: remove da memória de trabalho o elemento que teve uma correspondência positiva com a condição da i-ésima premissa;
• ATUALIZA i (atributon especificaçãon ): atualiza o atributo atributon de
acordo com especificaçãon do elemento da memória de trabalho que teve uma
correspondência positiva com a condição da i-ésima premissa.
Assim, como para os EMTs, as regras também são escritas em diferentes sistemas
especialistas de acordo com uma linguagem própria, mas contendo a estrutura e os
elementos 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 correspondência de
tipo é encontrada: robo. Em seguida, a especificação de atributo velocidade (uma
expressão), indica que o atributo velocidade do EMT deve ter o mesmo valor da
especificação, o que de fato ocorre. Já a especificação para orientação é um teste: o
valor deste atributo no EMT deve ser maior que 30o e menor que 90o , o que é obedecido no EMT. Por fim, uma variável é utilizada na especificação de dist obstaculo.
A substituição {x/0.5} completa o processo. A segunda premissa também é imediatamente satisfeita. Assim, de acordo com a modificação presente na consequência,
a meta é modificada na MT.
Este processo executado pelo interpretador corresponde ao algoritmo de inferência em LPO de encadeamento adiante. O Algoritmo 2 apresenta o algoritmo de
encadeamento adiante conforme Russel e Norvig (2004).
Os SEs foram o primeiro exemplo na história da IA de um conjunto mais abrangente de sistemas inteligentes: os Sistemas Baseados em Conhecimento (SBC). SBCs
são sistemas que possuem um conhecimento mais geral sobre o domı́nio de aplicação, e o considera separado do restante do sitema. O SEs geralmente possuem
conhecimento bastante especı́fico, baseado no de um especialista, sendo aplicados
em domı́nios mais restritos (Mihaguti 1996). Esta distinção, embora não seja muito
rigorosa, 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 memória de trabalho.
1: função ENCADEAMENTO-ADIANTE(BC )
2:
repita
3:
novo ← {}
4:
para cada regra ∈ BC faça
5:
(p1 ∧ . . . ∧ pn ) ← regra
6:
subst ← {σ ∗ |(p∗1 , . . . , p∗n ∈ BC) ∧ (p1 ∧ . . . ∧ pn )σ ∗ = (p∗1 ∧ . . . ∧ p∗n )σ ∗ }
7:
para cada σ ∈ subst faça
8:
q ∗ ← qσ
9:
se (∀S ∈ BC ∪ novo) U N IF ICAR(q ∗ , S) ≡ ∅ então
10:
novo ← novo ∪ q ∗
11:
fim se
12:
fim para
13:
fim para
14:
BC ← BC ∪ novo
15:
até que novo ≡ {}
16: fim função
2.5
Conclusão
O capı́tulo apresentou os métodos de representação de conhecimento utilizados
pelo AAC: a LPO, a LTP, os quadros e os SBCs. Além disso, os procedimentos
de raciocı́nio automático utilizados pelo agente foram descritos. O encadeamento
adiante é utilizado por um sistema especialista com uma base de conhecimento
composta por regras da LPO, e o algoritmo MetateM para uma BC que aplica
LTP. O capı́tulo seguinte descreverá como o AAC utiliza estas representações e
algoritmos para a tomada de decisão em ambientes dinâmicos.
27
Capı́tulo 3
O Agente Autônomo Concorrente
(AAC)
Este capı́tulo apresentará o Agente Autônomo Concorrente (AAC). Sua arquitetura cognitiva será descrita, inicialmente em termos da sua implementação original,
com base no framework Expert-Coop++. Em seguida, serão apresentadas as adequações estruturais realizadas para implementar o agente embarcado na arquitetura
de hardware proposta neste trabalho. Por fim, os métodos de representação de conhecimento utilizados pelo agente serão abordados, fazendo sempre uma correlação
com o conteúdo do Capı́tulo 2.
3.1
Modelo Genérico para Agentes Cognitivos
A arquitetura do AAC foi inspirada no modelo genérico para agentes cognitivos,
proposto em (Bittencourt 1997). De acordo com esse modelo, um agente cognitivo
é composto por três nı́veis: o nı́vel reativo, o nı́vel instintivo e o nı́vel cognitivo. O
modelo é ilustrado na Figura 3.1.
O nı́vel reativo, caracterizado por um rápido ciclo percepção/ação, representa um
ambiente evolucionário composto por padrões retirados das percepções do ambiente,
controles de efetuador utilizados para atuar no ambiente externo e um conjunto de
comportamentos reativos atrelando percepção e ação. Este nı́vel modela animais
simples, como insetos.
O nı́vel instintivo possui uma memória que possibilita perceber quando situações
se repetem na natureza e que grupo de agentes reativos pode ser utilizado nessas
situações, aplicando-os novamente quando aquela situação de repetir. Este nı́vel,
juntamente com o reativo, pode modelar animais mais complexos, como os mamı́feros.
O nı́vel cognitivo se baseia no aprendizado de situações relevantes e a subsequente
geração de novas estratégias de ação.
Segundo esse modelo, cada nı́vel, juntamente com os seus hierarquicamente in28
Figura 3.1: O Modelo Genérico de Agentes Cognitivos (Barbosa 2005).
feriores, pode modelar um agente completo, sendo que a complexidade do modelo
cresce com o número de camadas.
3.2
Arquitetura Cognitiva do AAC
O AAC surgiu para superar as deficiências encontradas no agente utilizado na primeira participação do UFSC-Team na categoria de robôs simulados da RoboCup’98.
A arquitetura desse agente apresentava um processo decisório centralizado, o que
comprometeu a comunicação em tempo-real com o ambiente (Costa et al. 2011).
Com isso, o AAC foi incorporado na implementação do framework Expert-Coop++,
que então passou a possibilitar a implementação de agentes cognitivos com processo
decisório descentralizado, através de uma abordagem concorrente. A arquitetura
do AAC é ilustrada na Figura 3.2, fazendo a correspondência com os processos do
Expert-Coop++ “Interface”, “Coordinator ” e “Expert”, onde os nı́veis do AAC foram
implementados (Costa e Bittencourt 1999).
O nı́vel reativo é responsável pela resposta em tempo-real do agente. Em sua primeira implementação foi executado pelo processo “Interface” do Expert-Coop++ e
contém um conjunto de controladores nebulosos que implementam os comportamentos reativos do agente, os quais são ativados em situações especı́ficas. Apenas um
controlador nebuloso pode estar ativo por vez. Esse nı́vel faz a leitura dos sensores
e executa uma ação (isto é, executa o ciclo percepção-ação do agente). A Figura 3.3
ilustra a estrutura deste nı́vel.
O nı́vel instintivo detecta, após cada ciclo percepção-ação, mudanças nos estados
do ambiente e do agente, atualiza as informações simbólicas 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 seleção de comportamentos reativos. A Figura 3.4 ilustra
a atuação desse nı́vel. Este nı́vel executa planos que, se bem sucedidos, levam à
satisfação de metas locais. Quando uma meta local é satisfeita, uma mensagem
é enviada ao nı́vel cognitivo, avisando ao mesmo. Um SBC, cuja base de regras
pode ser selecionada dentre várias, cada uma correspondendo a um plano, executa
a seleção de comportamentos reativos. A memória de trabalho desse SBC (que, no
contexto 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́ responsável pela criação das metas locais e globais através um
SBC, e a comunicação das mesmas para o nı́vel instintivo (Figura 3.5). Este nı́vel
recebe as informações simbólicas 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++
gico) e as mensagens dos outros agentes. O nı́vel cognitivo não interage diretamente
com o reativo. Um importante aspecto do AAC é que enquanto os nı́veis instintivo
e reativo trabalham no alcance de uma meta local, o nı́vel cognitivo pode, concomitantemente, se dedicar a tarefas de planejamento, criação de metas, etc. Assim, por
possuir um maior tempo de resposta, o sistema baseado em regras do nı́vel cognitivo
pode ser bastante mais complexo que o do instintivo.
Figura 3.5: Nı́vel cognitivo do AAC implementado no framework Expert-Coop++
Um componente importante presente em todos os nı́veis apresentados acima, o
mailbox, tem um papel fundamental no funcionamento do agente. O mailbox consiste
de um objeto instanciado em cada processo do Expert-Coop++ que oferece uma
31
interface de comunicação baseada em soquetes UNIX e uma estrutura de dados que
funciona 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 seção
anterior foi modificada. No nı́vel reativo os comportamentos serão implementados
por um sistema de controle clássico, e consistirão de direções para onde o robô pode
seguir. Conforme ilustrado na Figura 3.6, oito comportamentos serão utilizados pelo
nı́vel reativo embarcado: norte (N), nordeste (NE), leste (L), sudeste (SE), sul (S),
sudoeste (SO), oeste (O) e noroeste (NO). Quando um dos comportamentos listados acima está ativo (na figura, o comportamento NE é mostrado como ativo), o
robô deverá seguir na direção correspondente. Adicionalmente, o comportamento
“páre sucesso” e “páre falha” (não ilustrados na Figura 3.6) serão implementados
para que o robô páre em caso de ter alcançado a meta ou de ter colidido, respectivamente.
Figura 3.6: Nı́vel reativo embarcado.
A principal modificação estrutural no caso do nı́vel instintivo embarcado será a
presença de dois Mailboxes, pois, como se estabelecerá no Capı́tulo 4, a arquitetura de
hardware onde o AAC será embarcado consiste de dois protocolos de comunicação
diferentes, e decidiu-se dividir o Mailbox para cada barramento para reduzir as
chances de problemas decorrentes do acesso a recursos compartilhados. A Figura
3.7 mostra esta arquitetura.
32
Figura 3.7: Nı́vel instintivo embarcado.
Finalmente, o nı́vel cognitivo pode ou não sofrer modificações. Isso porque, como
se verá no Capı́tulo 4, mesmo em um ambiente embarcado poderá ser utilizada
a implementação original do nı́vel cognitivo, isto é, a implementação do processo
“Expert” do Expert-Coop++. Mas neste trabalho propõe-se a utilização de LTP
neste nı́vel, então uma estrutura atualizada deste nı́vel, levando em consideração
ambas as formas de representação de conhecimento, é mostrada na Figura 3.8.
3.4
3.4.1
Representação do Conhecimento no AAC
LPO e Quadros
A arquitetura original do AAC utiliza a LPO e quadros para compor a base de conhecimento de um sistema baseado em conhecimento. Os EMT, doravante referidos
simplesmente como fatos, têm 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 enuncia
apenas um atributo de um dado objeto. A parte “b” dessa figura, representa o caso
de múltiplos 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, Seção 2.4) representado 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, “regra id” denota o identificador da regra, que deve ser único na base de regras. As
“condições”, como na Seção 2.4, tem a estrutura dos fatos com os valores dos atributos substituı́dos por especificações. Mas no AAC especificações contendo variáveis
são complementadas por filtros, especificados no campo “filter”, que proveem as
restrições condicionais às quais os valores das variáveis devem obedecer. As “consequências”, por fim, expressam as ações a serem tomadas (de Santana Júnior e
Costa 2007). Estas ações não são apenas locais, isto é, apenas sobre a própria base
34
de fatos, mas também envolvem a troca de mensagens entre os nı́veis do AAC. O
formato das mensagens adotado é o da linguagem de comunicação entre agentes
cognitivos Parla (da Costa e Bittencourt 1997).
Figura 3.11: Formato de uma regra de produção.
Exemplo 3.4.2. A Figura 3.12 mostra um exemplo de base de regras para o nı́vel
instintivo. A regra “regra 1” verifica se a meta atual foi atingida, isto é, se o robo
está a menos de 10cm de distãncia da meta. Caso existam fatos na base de fatos
que tornem essa condição verdadeira, o nı́vel instintivo envia para o cognitivo uma
mensagem informando que a meta local foi alcançada, e para o reativo uma mensagem contendo o comportamento selecionado. A segunda regra (“regra 2”) verifica
se a distância do robô a uma obstáculo é menor que o limiar de 5cm, caso em que o
robô é considerado em zona de colisão.
Figura 3.12: Exemplo de uma base de regras com 2 regras.
Conforme já foi mencionado, o AAC admite também a utilização de quadros na
representação do conhecimento do agente. A Figura 3.13 mostra como os quadros
são utilizados na linguagem do agente. Os “f rame id” é uma identificador que
permite 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 representação do conhecimento utilizada pelo
AAC é mostrada na Figura 3.14 (de Santana Júnior e Costa 2007).
35
Figura 3.14: Sintaxe completa na forma de Backu-Naur (de Santana Júnior e
Costa 2007).
O motor de inferência implementa o algoritmo de encadeamento adiante, mostrado
no Algoritmo 2. A BC dada como entrada para este algoritmo, neste caso, consiste
das bases de fatos e de regras. Assim, a Figura 3.15 ilustra a arquitetura do SBC
utilizado nos nı́veis instintivo e cognitivo quando LPO e quadros são os formalismos
de representação do conhecimento.
Figura 3.15: Diagrama do SBC do AAC (de Santana Júnior e Costa 2007).
3.4.2
LTP
Alternativamente, o nı́vel cognitivo pode utilizar a LTP como formalismo de representação de conhecimento. O algoritmo MetateM, utilizado para inferência,
consiste de um processo de encadeamento adiante caracterı́stico de sistemas especialistas. Neste contexto, para manter os métodos desta seção e da anterior dentro
36
de um mesmo padrão estrutural, pode-se fazer a correspondência dos termos ali
utilizados com a abordagem atual:
• dado um modelo hN, πi, o mapeamento π constitui a base de fatos, isto é, o
que é conhecido como verdadeiro;
• a base de regras consiste do conjunto de regras que formam um sentença na
FNS da LTP; e
• o motor de inferência implementa o algoritmo MetateM.
A dinâmica do sistema muda pelo fato de que agora a base de fatos não muda
apenas como resultado dos ciclos de inferência do MI e das mensagens recebidas,
mas também ao longo do tempo.
Exemplo 3.4.3. A Figura 3.16 ilustra isso. O motor de inferência utiliza o fato A
em t − 1 para inferir, com base na (única) regra A ⇒ eB, que B será um fato em t,
mas nenhuma regra conclui A. Assim, a própria passagem do tempo faz A “expirar”.
Figura 3.16: Inferência com LTP.
Segundo Fisher (2011), o algoritmo MetateM pode ser utilizado para tarefas
de planejamento através da adequada postergação da satisfação de eventualidades.
Mais precisamente, deve-se assumir que as metas serão eventualmente alcançadas,
mas também deve-se garantir que isso não ocorra até que os pré-requisito para aquela
meta tenham sido alcançados. Isto é, uma meta possui n pré-requisitos, denotando
a 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 não for satisfeito,
¬meta estará na base de fatos, impedindo a satisfação da meta.
É possı́vel também, através do uso de eventualidades e do exposto acima sobre
postergação das suas satisfações, expressar o ordenamento de metas: se as metas
meta1 , . . ., metam devem ser alcançadas nesta ordem, as sentença
♦(meta1 ∧ ♦(...metam−1 ∧ ♦metam ) . . .)
captura essa especificação (Fainekos et al. 2009).
3.5
Conclusão
Neste capı́tulo viu-se a arquitetura cognitiva do AAC e como esta foi herdada
do modelo genérico de agentes cognitivos. Também se explanou como esta arquitetura foi ajustada para ser embarcada em uma rede de microcontroladores, sendo
o nı́vel reativo, camada mais baixo do AAC, o nı́vel que mais sofreu modificações.
Mostrou-se como o agente utiliza LPO e quadros para representar conhecimento,
e mostrou-se como a LTP pode também ser utilizada como método de representação de conhecimento e raciocı́nio (este último procedimento implementado pelo
algortimo MetateM).
38
Capı́tulo 4
Arquitetura de Hardware
Para suprir a demanda de concorrência do AAC, apresenta-se neste capı́tulo uma
arquitetura de hardware composta por uma rede de microcontroladores dedicada à
execução deste agente. Este capı́tulo compõe, pois, o núcleo do presente trabalho,
trazendo a sua principal contribuição. O propósito da arquitetura é embarcar o AAC
no robô móvel omnidirecional AxéBot. A rede embarcada é proposta com o intuito
de fazer o AAC funcionar como um sistema distribuı́do em que um comportamento
inteligente emerge da interação entre os três nı́veis do agente de forma transparente.
4.1
Visão Geral do Sistema Embarcado
Uma rede heterogênea consistindo de três microcontroladores compõe o arquitetura de hardware projetada para comportar o AAC. Os nós computacionais da rede
são os seguintes:
• o DIL/NetPC (DNP) 2486, da SSV Embedded Systems;
• o ARM mbed ; e
• o PSoC 5LP, da Cypress Semiconductors.
A rede é heterogênea porque utiliza duas interface de comunicação digital diferentes entre seus três nós: uma rede CAN (sigle em inglês 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 na
mesma. Já foi visto anteriromente neste trabalho que o AAC requer concorrência.
Esta concorrência só pode ser alcançada perfeitamente se cada nı́vel tiver um núcleo
computacional dedicado à sua execução. Além disso, estes núcleos computacionais
devem poder se comunicarem entre si, conforme a demanda de comunicação entre
os 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
4.2.1
Protocolos de Comunicação
O Protocolo CAN
O protocolo de comunicação serial Controller Area Network (CAN) foi criado por
Robert Bosch na década de 1980 para ser utilizado na comunicação entre diversos
subsistemas de um veı́culo automotivo, prescindindo de um sistema de controle central. Desde então, o protocolo CAN passou a ser utilizado amplamente no contexto
de automação industrial, até que, em 1993, se tornou um padrão interncaional: o
ISO (International Standards Organization) 11898 (Zhang 2010).
O protocolo CAN é definido em termos do modelo de sete camadas OSI (Open
Systems Interconnected ) como compostos das suas duas camadas mais baixas: as
camadas fı́sica e de enlace. A camada fı́sica trata de especificações do meio fı́sico. A
camada de enlace é responsável, em termos gerais, pela manutenção de um enlace
lógico entre os nós. A Figura 4.2 mostra as camadas OSI acima referidas e os
elementos 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 não define um meio de transmissão,
40
apenas que os sinais devem ser transmitidos utilizando uma codificação diferencial,
o que significa que os valores lógicos no barramento serão codificados de acordo com
a diferença de tensão entre duas linhas - CANH e CANL - conforme o ilustrado na
Figura 4.3. Nessa figura vê-se que o nı́vel lógico alto é classificado como recessivo,
e o baixo, como dominante. Isto significa que se um nó tentar impor o nı́vel lógico
alto sobre o barramento, enquanto outro, ao mesmo tempo, tentar impor o nı́vel
lógico baixo, o último prevalecerá (Ranjith 2013).
Figura 4.3: Codificação diferencial dos sinais no protocolo CAN (Ranjith 2013).
A comunicação em uma rede CAN ocorre por meio da difusão (broadcasting) de
mensagens em um barramento. A taxa de transmissão de dados numa rede CAN
pode 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́ fisicamente
conectado ao barramento. Além disso, fica explı́cito que cada nó deve possuir um
transceiver. O que a figura não mostra é o controlador CAN, que também deve
estar presente em cada nó. O controlador CAN é mais frequentemente integrado ao
hardware dos nós da rede, enquanto que os transceivers são geralmente externos a
estes últimos.
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 presença dos transceivers
pode ser prescindida em prol de uma topologia simplificada. Mas a velocidade
máxima de transmissão em barramentos sem transceivers é limitada a 500 kbps
(Barrenscheen 1998). Esta configuração é mostrada na Figura 4.5.
41
Figura 4.5: Barramento CAN sem transceivers (Barrenscheen 1998).
Qualquer nó conectado ao barramento, detectando que este último se encontra
livre, pode iniciar a transmissão de mensagens. Estas mensagens são organizadas em
pacotes de dados denominados quadros. O protocolo CAN conta com quatro tipos
de quadros: o quadro de dados, utilizado para transferir dados entre nós, o quadro
remoto, utilizado para os nós fazerem requisições de dados, o quadro de erro, que
pode 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 para
prover 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 arbitração carrega o significado da mensagem, e cada nó do barramento
decide, ao ler este campo, se deve aceitar essa mensagem. Também é utilizado para
arbitrar o acesso ao meio: em caso de colisão, o nó cuja mensagem possui o menor
identificador de 11 bits tem a prioridade. O campo de controle contém o tamanho
da mensagem, o campo de dados contém os dados da mensagem e o campo CRC
(Cyclic Redundancy Check ) é utilizado pelos nós do barramento para verificar erros
no quadro (Ranjith 2013).
Se referindo à Figura 4.2, a camada de enlace divide suas responsabilidades entre
a subcamada de controle da ligação lógica (do inglês, Logical Link Control, LLC) e a
subcamada de controle de acesso ao meio (do inglês, Medium Access Control, MAC).
A subcamada LLC executa a aceitação de mensagens através de um mecanismo
de filtragem, notificação de sobrecarga e gestão de recuperação. Já as tarefas de
detecção de erros, encapsulamento de dados em pacotes, confirmação e gestão de
acesso ao meio são atribuições 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, que
possui (a exemplo do protocolo CAN, abordado na seção anterior) as subcamadas
LLC e MAC, e uma camada fı́sica (abreviada como PHY) (IEEE 2012).
A camada fı́sica especifica que os sinais elétricos são transmitidos através de dois
sinais diferenciais: um de recepção, com linhas rotuladas de RX+ e RX-, e um de
transmissão, com linhas TX+ e TX-, com valocidade máxima de transmissão de
dados de 100 Gbits/s. A codificação utilizada para estabelecer os nı́veis lógicos do
sinal elétrico é a codificação Manchester, que atribui um valor lógico a uma transição
de estados dentro de um tempo de bit: uma transição ascendente produz um nı́vel
lógico alto, e uma transição descendente, um nı́vel lógico baixo, conforme a Figura
4.7 exemplifica (IEEE 2012).
Figura 4.7: Forma de onda correspondente à sequência de bits “0011110” sob a
codificação Manchester (IEEE 2012).
A codificação Manchester é utilizada sobre os quadros de dados do protocolo
Ethernet para torná-los apropriados à trasnmissão. Os quadros Ethernet têm a
estrutura mostrada na Figura 4.8.
Figura 4.8: Estrutura de um quadro Ethernet (Toulson e Wilmshurst 2012).
O padrão IEEE 802.2 também especifica que a comunicação com o protocolo
Ethernet pode ocorrer nos modos half-duplex (apenas um nó pode utilizar o meio
por vez) ou full-duplex (os dois nós podem utilizar o meio concomitantemente, mas
somente para comunicações ponto-a-ponto entre dois nós). No primeiro caso um mecanismo de contenção é necessário para detectar quando dois nós estão transmitindo
ao mesmo tempo. O mecanismo especificado no padrão é o algoritmo Carrier Sense
Multiple Access with Collision Detection (CSMA/CD). Este algoritmo consiste em
fazer os nós “escutarem” o meio enquanto transmitem para detectar colisões com
mensagens de outros nós. Se uma colisão é detectada, os nós mantêm a colisão por
mais algum tempo para que os demais nós a percebam, e então cessam a transmissão,
tentando novamente depois de um intervalo de tempo aleatório (IEEE 2012).
43
4.3
4.3.1
Nı́vel Reativo: PSoC 5LP
O PSoC 5LP
O PSoC (Programmable System-on-Chip) 5LP é o microcontrolador que compôe o
nó da rede onde o nı́vel reativo do AAC foi embarcado. As principais caracterı́sticas
do PSoC 5LP são mostradas na Tabela 4.1.
Tabela 4.1: Principais caracterı́sticas do PSoC 5LP
Recurso
CPU
Flash
SRAM
EEPROM
PSoC 5LP
ARM Cortex-M3, 1.25 DMIPS/MHz
256KB
64KB
2KB
A Figura 4.9 mostra a arquitetura do PSoC 5LP. Nesta figura pode ser notado
que o PSoC 5LP tem quatro subsistemas principais:
• o subsistema da CPU, que utiliza o processador ARM Cortex-M3, com periféricos de comunicação dedicados;
• o subsistema digital, consistindo de blocos digitais denominados UDBs (Universal Digital Blocks), que implementam recursos digitais no hardware, independentes da atuação da CPU;
• o subsistema analógico, que provê recursos analógicos também de maneira
independente da CPU; e
• o subsistema de roteamento programável, que permite determinar funções de
pinos em tempo de projeto.
Ressalta-se a conveniência de se utilizar o PSoC 5LP como plataforma para embarcar o nı́vel reativo, devido ao fato de que este microcontrolador possui uma arquitetura adequada ao caráter evolutivo do nı́vel reativo proposto no modelo genérico
para agentes cognitivos. Ou seja, a versão embarcada do nı́vel reativo apresentada
aqui pode, em implementações futuras, ser estendida para mimetizar a arquitetura
do nı́vel reativo mostrado na Figura 3.1 através do uso mais intenso dos subsistemas
digital e analógico do PSoC nas tarefas de aquisição e controle. Os controladores
difusos, por exemplo, poderiam ser implementados nos UDBs do PSoC, liberando o
processador para tarefas de comunicação e computação 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 série de
tarefas:
• comunicação CAN com o mbed (nı́vel instintivo);
• comunicação UART com um PC para supervisão e simulação;
• executar o controle cinemático; e
• executar o controle dos atuadores.
O gerenciamento destas tarefas foi realizado com a utilização de um Sistema Operacional de Tempo Real (SOTR), dado que, conforme (Stankovic e Rajkumar 2004),
um SOTR é capaz de gerenciar é capaz de gerenciar múltiplas tarefas através de
mecanismos de sincronização envolvendo priorização de tarefas e escalonamento,
provendo uma camada de abstração no projeto do software.
O SOTR utilizado aqui foi o FreeRTOS. No FreeRTOS as tarefas podem estar em
um dos seguintes estados:
• executando, quando a tarefa está executando;
• bloqueada, quando a tarefa não está apta a executar até que algum evento
ocorra;
• pronta, quando não está executando, mas pode estar; e
• suspensa, quando não está executando e não pode estar.
A Figura 4.10 mostra os estados listados acima e as possı́veis transições entre
eles. Quando uma tarefa é criada o estado dela é “pronta”, e um escalonador de
tarefas decide se ela pode ou não estar no estado “executando” com base na sua
45
prioridade: se alguma tarefa com prioridade superior já está executando, a tarefa
recém criada espera (no estado “bloqueada”) até que a tarefa que está executando
seja bloqueada ou suspensa; se a tarefa executando tem prioridade inferior à criada,
esta última passa a executar e a primeira vai para o estado “bloqueada”. Caso não
haja uma tarefa no estado “executando”, a nova tarefa passa automaticamente para
este estado.
Figura 4.10: Diagrama de estados das tarefas no FreeRTOS.
As tarefas criadas no nı́vel reativo são mostradas na Tabela 4.2. Nesta tabela,
a terafa inativa corresponde à tarefa que é posta no estado “executando” pelo escalonador de tarefas quando não há tarefas neste estado, nem no estado “pronta”.
Tabela 4.2: Tarefas implementadas.
Tarefa
Prioridade
Controle Cinemático
3
Controle de Atuadores*
2
Recepção de Mensagens CAN
2
Envio 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 Reativo
Na Figura 3.6 (Capı́tulo 3, Seção 3.3) é mostrado o conjunto de comportamentos reativos a serem implementados na versão embarcada do nı́vel reativo do AAC.
Mencionou-se, quando da apresentação da supracitada figura, que um sistema de
controle clássico seria utilizado para a construção dos comportamentos no nı́vel
reativo, e nesta seção se descreverá como o modelo cinemático do robô móvel omnidirecional AxéBot será utilizado no nı́vel reativo para o desenvolvimento de um
controlador cinemático que, por sua vez, deverá servir de base para a implementação
dos comportamentos.
46
Modelo Cinemático
O modelo cinemático de uma robô móvel omnidirecional é dado pela relação matemática entre as velocidades angulares dos seus atuadores e a velocidade do seu
centro de massa. É obtido a partir da relação geométrica entre sistemas de referência locais (aqueles “fixados” na base móvel do robô) e um sistema de referência
global (com relação ao qual os sistemas de referência locais se movem). A Figura
4.11 mostra estes sistemas de referência para o robô AxéBot. Nesta figura, SR é o
sistema de referência da base do robô e os SC i são sistemas de coordenadas fixados
a cada roda i, com i = 1, 2 e 3 (Bitencourt et al. 2008).
Figura 4.11: Sistemas de coordenadas no AxéBot para modelagem cinemática
(Bitencourt et al. 2008).
A Equação (4.1) apresenta a matriz da cinemática direta do AxéBot.


2 cos θ
− 3


2 sin θ
P (θ) = 
− 3


1
3l
√
√
3 cos θ−3
√ sin θ
3 3
3 sin θ+3
√ cos θ
3 3
√
√
1
3l
3 cos θ+3
√ sin θ 
3 3



3 sin θ−3
√ cos θ 
3 3

1
3l
(4.1)

O modelo cinemático direto completo é apresentado na Equação (4.2).
 
 
vxI 
φ̇1x 
 
 
 
 
v  = P (θ) φ̇  .
 yI 
 2x 
 
 
 
 
θ̇
φ̇3x
47
(4.2)
Na Equação (4.2), vxI , vxI e θ̇ representam, respectivamente, as velocidades nas
direções x e y, e a velocidade angular do centro de massa do robô no sistema de
coordenadas SI , φ̇ix representa a velocidade angular da roda i com relação ao eixo
x do sistema de coordenadas SCi e R é o raio das rodas.
Controlador Cinemático
Uma vez de posse do modelo cinemático do robô é possı́vel utilizar este modelo
para projetar um controlador que o possibilite estabilizar em uma dada posição desejada (ponto-a-ponto) ou seguir uma trajatória dada (rastreamento de trajetória).
A este controlador, por se basear em um modelo cinemático, dá-se o nome de controlador cinemático. Com o controlador cinemático é possı́vel implementar controle
de posição ou de velocidade. Aqui será descrito o controle de posição, apontando no
final como modificar este controlador para executar o controle de velocidade.
A entrada do controlador de posição é a posição ou trajetória desejada, isto é,
o set-point. O controlador então calcula o vetor de diferença entre a posição de
R
R
referência (xR
I , yI e θ ) e a posição real do centro do robo (xI , yI e θ). Esta
operação produz o vetor de erro, como na Equação (4.3). (4.3).

  
 xI (t)
xR

 I 

  



e(t) = yIR  −  yI (t) 


  
  

θ(t)
θR
(4.3)
Este vetor de erro é utilizado para calcular uma ação de de controle ProporcionalIntegral (PI). Para o controle ponto-a-ponto, segundo Tsai et al. (2005), a ação de
controle é calculada de acordo com a Equação (4.4), onde KP e KI são matrizes
3 × 3 simétricas e positivamente definidas.
Zt
u(t) = KP e(t) + KI
e(τ ) dτ
(4.4)
0
R
R
Para o rastreamento de trajetória o vetor referência pT (t) = xR
I (t) yI (t) θ (t)
é agora dependente do tempo, e a ação de controle é modificada pela adição da
derivada do vetor de referência, conforme a Equação (4.5).
Zt
u(t) = KP e(t) + KI
e(τ ) dτ + ṗ(t)
(4.5)
0
O vetor da ação de controle é então aplicado na Equação (4.6) (cinemática inversa) para a obtenção das velocidades angulares desejadas dos atuadores. Estas
48
Figura 4.12: Diagrama de blocos do controlador cinemático.
velocidades angulares, por sua vez, são os set-points de outro controlador, em um
nı́vel mais baixo: o controlador dos atuadores. As velocidades das rodas devem
ser ajustadas aos valores dados para que a posição da base seja corrigida. Ribeiro
(2010) projetou e implementou este controlador de baixo nı́vel para os atuadores do
AxéBot, e os seus resultados serão utilizados aqui.
 
φ̇1x 
 
 
φ̇  = 1 P −1 (θ) u(t).
 2x  R
 
 
φ̇3x
(4.6)
Por fim, a velocidade real das rodas é lida através de encoders e aplicadas na
Equação (4.2) (cinemática direta), tendo como resultado as velocidades lineares
e angular da base. A integração deste resultado provê a posição da base, que é
realimentada no controlador para novo cálculo de erros e continuar o laço. A Figura
4.12 mostra um diagrama do controlador.
O controlador cinemático foi utilizado no PSoC 5LP para implementar os comportamentos do nı́vel reativo. Estes comportamentos consistiram simplesmente do
movimento nas direções cardeais: norte, nordeste, leste, sudeste, sul, sudoeste, oeste
e noroeste. Nessa caso um controlador de velocidades é mais adequado, pois pode-se
fixar uma velocidade linear e alterar apenas a orientação para intercambiar entre os
comportamentos. A mudança com relação ao expostos até aqui, no entanto, é mı́nima. Primeiro, o set-point agora é um vetor de velocidades, na mais uma posição
ou uma trajetória. Depois, realimenta-se a velocidade da base (obtida pelo aplicação
da valocidade real das rodas na cinemática direta), isto é, não executa a integração
mencionada no parágrafo anterior.
4.4
Nı́vel Instintivo: o mbed
O mbed é na realidade um módulo microcontrolado, baseado no microcontrolador
NXP LPC1768. Este último, por sua vez, também utiliza o micriprocessador ARM
Cortex-M3 como CPU, a exemplo do PSoC 5LP. O mbed é mostrado na Figura
4.13(a) com os seus 40 pinos dispostos em duas linhas de 20. Na parte (b) da
mesma figura, os elementos do módulo são apontados, e um diagrama completo dos
seus recursos de comunicação 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ı́das
digitais do mbed, assim como os periféricos que este disponibiliza, são os do microcontrolador LPC 1768. Mas devido ao fato de o LPC 1768 possuir mais de 100 pinos
e o mbed só possuir 40, limita este último à utilização de apenas um subconjunto
das funções do primeiro. O mbed utiliza um microcontrolador de interface para gerenciar a comunicação USB com o PC. Este microcontrolador faz o PC reconhceer o
mbed como um dispositivo de armazenamento, e gerencia a transferência do arquivo
executável para uma memória flash de 16 MBits. Quando o botão de reset é pressionado, o microcontrolador de interface transfere para a memória flash do LPC 1768
o arquivo executável mais recente, e inicia a execução (Toulson e Wilmshurst 2012).
Uma das interfaces CAN é utilizada para a comunicação com o PSoC 5LP. Este
último envia para o mbed informações referentes ao estado do ambiente e do agente,
e recebe comandos de seleção de comportamentos. A interface Ethernet é utilizada
para comunicação com o nó computacional correspondente ao nı́vel cognitivo (o DNP
2486 ).
O mbed possui uma API (Application Program Interface) que consiste em uma
abstração da CMSIS (do inglês, Cortex Microcontrollers System Interface Standard ),
que por sua vez é um padrão de interface de software em linguagem C, desenvolvida
pela ARM, para a programação de microcontroladores baseados em microprocessadores da famı́lias Cortex. A abstração 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 implementação da CMSIS para o LPC
1768, abstraindo-a do desenvolvedor.
A partir da sua versão 3, a CMSIS passou a contar com a CMSIS RTOS, que
oferece uma API padronizada para SOTR. Assim, a API do mbed implementa o
mbed RTOS, totalmente baseado na CMSIS RTOS. Este é o SOTR utilizado para a
implementação do nı́vel instintivo. AS tarefas neste SOTR são chamadas de threads,
e possuem estados similares às tarefas do FreeRTOS (Figura 4.10).
As cinco tarefas utilizadas na implementação do nı́vel instintivo foram:
• Envio de mensagens pela rede CAN;
• Recepção de mensagens pela rede CAN;
• Envio de mensagens pela rede Ethernet;
• Recepção de mensagens pela rede Ethernet;
• Motor de inferência.
Neste nó, um sistema baseado em conhecimento com regras em LPO teve que ser
implementado, pois o mbed mostrou-se incapaz de executar o processo “Interface” do
Expert-Coop++ (responsável por executar o nı́vel instintivo) mesmo para pequenas
bases de regras. Assim, utilizou-se estruturas de dados estáticas para armazenar as
51
regras. Além disso, um mailbox foi implementado para a comunicação CAN com o
PSoC 5LP e outro separado para a comunicação Ethernet.
4.5
Nı́vel Cognitivo: o DNP 2486
O nı́vel cognitivo é implementado no DIL/NetPC 2486 : um módulo baseado no
microcontrolador Vortex86SX SoC (System on Chip) de 300MHz, com 1GB de memória Flash NAND e 64MB de memória SDRAM DDR2. O DNP 2486 utiliza uma
distribuição embarcada do sistema operacional Linux, o que faz com que o nı́vel
cognitivo embarcado nesta plataforma corresponda a uma aplicação de usuário executando neste sistema. Este nó tinha que ser bastante robusto computacionalmente
pois executará as tarefas mais complexas de raciocı́nio simbólico do AAC. A Figura
4.15 mostra o DNP 2486 juntamente com um diagrama de blocos simplificado do
mesmo.
Figura 4.15: DIL/NetPC 2486.
Conforme mencionado no Capı́tulo 3, o nı́vel cognitivo implementa um sistema
baseado em conhecimento com um motor de inferência que pode utilizar tanto o
algoritmo de encadeamento adiante da LPO, como o algoritmo MetateM da LTP.
No primeiro caso, uma implementação do processo “Expert” do framework ExpertCoop++ é utilizada para o nı́vel cognitivo embarcado. Isso porque este framework
se mostrou portável para o sistema operacional do DNP.
No caso da base de conhecimento utilizando LTP, com execeção do mailbox, que
também utilizou a implementação do Expert-Coop++, um novo sistema baseado
em conhecimento teve que ser desenvolvido. O diagrama de classes da Figura 4.16
mostra as classes implementadas e o relacionamento entre elas. A classe “Symbol ”
representa um sı́mbolo proposicional, que pode ser positivo ou negativo (sem ou com
negação, respectivamente), e possui um rótulo identificador. Um conjunto de um
ou mais objetos da classe “Symbol ” interconectados por conjunções ou disjunções,
passados como argumentos para um operador temporal unário compõe um objeto
da classe “Logic”. A base de fatos é representada pela classe “FactsBase”, que pode
conter uma lista de objetos da classe “Logic” desprovidos de operadores temporais
(isto é, sentenças clássica conjuntivas ou disjuntivas) que, por sua vez, representam
52
Figura 4.16: Diagrama de classes do sistema baseado em conhecimento de nı́vel
cognitivo com LTP.
os fatos. Uma regra é um objeto da classe “Rule”, e contém dois objetos da classe
“Logic” para representar a sua premissa e a sua consequência. A classe “RulesBase”
permite instanciar uma base de regras com um ou mais objetos da classe “Rule”.
Um objeto da classe “InferenceEngine”, então, implementa o algoritmo MetateM,
que consulta as bases de regras e de fatos, atualizando o modelo lógico proposicional
contido nesta última.
4.6
Operação do Sistema
Na Figura 4.17 o diagrama de sequência do sistema é mostrado, ilustrando como o
mesmo funciona. Esta figura mostra a troca de mensagens entre os nı́veis do AAC e
entre este útimo e o ambiente. O agente inicia com um comportamento B1 ativo no
nı́vel reativo, e este envia ao instintivo as leituras dos sensores. Este nı́vel converte
as percepções recebidas em informação simbólica a respeito dos estados do agente
e do ambiente. A informação simbólica é usada pelo motor de inferência do nı́vel
instintivo, para decidir se deve mudar o comportamento ativo no reativo, e enviada
ao nı́vel cognitivo. Este, por sua vez, utiliza a informação simbólica no seu motor
de inferência para gerar uma nova meta local, caso necessário.
Toda vez que o nı́vel instintivo decide que o comportamento atual não deve ser
mudado, ele simplesmente não envia nenhuma mensagem ao reativo, como se vê em
I2. De maneira similar, o nı́vel cognitivo pode decidir não atualizar a meta local
(especialmente se a informação simbólica recebida do nı́vel instintivo não informa
que a meta local atual foi cumprida). Isso é mostrado em C2 e C3, e é independente
da decisão do nı́vel instintivo de mudar ou não o comportamento reativo atual.
4.7
Conclusão
Neste capı́tulo apresentou-se uma rede de microcontroladores concebida especialmente para embarcar o AAC no robô móvel omnidirecional AxéBot. Os três nós da
53
Figura 4.17: Diagrama de sequência 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 através de
dois protocolos de comunicação: CAN (entre o PSoC e o mbed ) e Ethernet (entre o
mbed e o DNP ).
Conforme discorreu-se no Capı́tulo 3, o nı́vel cognitivo do AAC pode executar
um sistema baseado em regras com LPO e quadros para representar o conhecimento
simbólico do agente, de acordo com a sua implementação original (com o ExpertCoop++), como também pode utilizar LTP e o algoritmo MetateM para este fim.
Mas a utilização de LTP pelo cognitivo é uma extensão à arquitetura original do
AAC, e o fato de que a arquitetura de hardware proposta permite a utilização de
ambas mostra que, não obstante o seu propósito especı́fico, a arquitetura proposta
ainda permite o desenvolvimento de outras técnicas no AAC.
54
Capı́tulo 5
Resultados
Os resultados de experimentos realizados com a arquitetura de hardware descrita
no Capı́tulo 4 são agora apresentados. Inicialmente um esquemático da arquitetura
resultante é mostrado. Depois os experimentos são descritos e seus resultados expostos. O primeiro experimento utiliza apenas o nı́vel reativo, e os dois experimentos
seguintes com todos os nı́veis, apenas alterando a estratégia de representação de
conhecimento e inferência no nı́vel cognitivo.
5.1
Nı́vel Reativo: Controlador Cinemático
Nesta seção serão apresentados resultados referentes a experimentos de estabilização ponto-a-ponto e rastreamento de trajetória utilizando o controlador cinemático
embarcado no microcontrolador PSoC 5LP.
5.1.1
Configuração dos Experimentos
A configuração do experimento com o controlador cinemático difere da dos experimentos subsequentes, pois neste caso foi possı́vel utilizar o robô AxéBot real, por
utilizar 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 cinemático foi implementado com um perı́odo TCin = 50ms.
Para realizar esse ciclo, uma interrupção de um temporizador do PSoC 5LP foi utilizada, liberando a cada 50ms, um semáforo para a tarefa do controlador cinemático
que, por sua vez, executa o correspondente ao ramo direto do diagrama de blocos da Figura 4.12. As matrizes KP e KI são 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 controladores de baixo nı́vel) foi executado em um perı́odo mais curto de TM ot = 10ms.
Isto significa que este controlador executará cinco iterações a cada iteração do controlador cinemático, o que é suficiente para estabilização com erro pequeno segundo
55
?. Destes trabalhos foram também retirados os valores das constantes proporcional
e integral: kp = 0.239 e ki = 0.051, respectivamente.
5.1.2
Resultados
Estabilização Ponto-a-Ponto
Como foi dito anteriormente, na estabilização ponto-a-ponto uma pose desejada ou
de referência é dada como entrada ao controlador e o robô precisa estabilizar naquela
T
pose. No presente experimento, a pose de referência foi dada por xR
yIR θIR =
I
T
2 m 3 m 4 rad . A Figura 5.1 mostra o resultado.
Figura 5.1: Resultado para estabilização ponto a ponto.
56
Rastreamento de Trajetória
No problema de rastreamento de trajetória a referência é dinâmica. A referência
utilizada neste experimento foi uma circunferência com raio de 2m, cujos pontos foram gerados internamente pela tarefa do controlador cinemático através da equação
paramétrica do cı́rculo, enquanto a orientação foi fixada em π/2 rad e a velocidade
. A Equação 5.1 dá a expressão
angular da trajetória de referência foi ω R = 0.2 rad
s
paramétrica da trajetória.

 

(t) 2 cos (θIR (t) + ω R t)
xR
 I  


 

y R (t) = 2 cos (θR (t) + ω R t)
 I  

I

 


 

θIR (t)
π/2
Os resultados são mostrados na Figura 5.2.
Figura 5.2: Resultados para rastreamento de trajetória.
57
(5.1)
5.2
Nı́veis Reativo, Instintivo e Cognitivo: Planejamento
Os resultados doravante apresentados correspondem a experimentos realizados
com a rede de microcontroladores completa, isto é, contendo os três nós correspondentes aos nı́veis do AAC. A arquitetura dos experimentos, conforme será mencionado logo em seguida, difere da do anterior.
5.2.1
Configuração dos Experimentos
Um diagrama de circuito da rede é mostrado na Figura 5.3. Neste diagrama vê-se
que o barramento CAN, entre o PSoC e o mbed, não utilizou transceivers, o que é
aceitável 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 todos os nós possuem um conector RJ45 com isolamento magnético, exceto o mbed.
Isto ocorre porque o mbed não possui uma interface fı́sica RJ45 nem o isolamento
magnético em sua placa, então optou-se por implementar o isolamento magnético
através de um banco de capacitores, conforme Ben-Josef (2011), e fazer a conexão
pino-a-pino com um cabo CAT5 (par trançado e sem blindagem).
Reiterando o que se afirmou no inı́cio desta seção, os experimentos com a rede
completa utilizaram uma configuração diferente daquela dos experimentos com o
controlador cinemático: não se utilizou o robô AxéBot real, mas sim um simulado
nos softwares Player 3.0.2 e Stage 3.2.2. O Player é um servidor para robôs que
fornece interfaces para sensores e atuadores, permitindo uma maior abstração no
desenvolvimento de aplicações envolvendo robôs equipados com estes elementos. O
simulador, na realidade, é apenas o Stage, que funciona sobre o Player simulando
robôs, sensores e objetos.
58
Figura 5.4: Diagrama da Rede Ethernet.
A despeito da utilização de um simulador, o raciocı́nio automático do AAC se
dá inteiramente embarcado na rede de microcontroladores. A arquitetura é aquela
da Figura 5.5. Assim, o simulador recebe os comandos do controlador cinemático e
envia as leituras do ambiente de acordo com os seus sensores.
Figura 5.5: Configuração dos experimentos de planejamento de movimento.
No Capı́tulo 3.2 viu-se que o nı́vel cognitivo do AAC pode utilizar tanto a LPO
quanto a LTP como mecanismos de representação de conhecimento e inferência.
Sendo assim, dois experimentos serão realizados, cada um utilizando uma dessas
variantes de representação no nı́vel cognitivo. Um aspecto comum a ambos os experimentos é a estratégia de redução do número de estados do mundo (ambiente), que
consiste de uma leve modificação daquela apresentada por Cerqueira et al. (2013).
Esta representação é mostrada na Figura 5.6. Os estados do ambiente são caracterizados pela posição relativa dos obstáculos e da meta com relação ao robô. Segmentase o espaço, no referencial do robô, em regiões: 4 para a meta (parte (a) da Figura
5.6) e 8 para os obstáculos (parte (b) da Figura 5.6). Dessa forma, o estado do
59
ambiente resume-se à determinação das regiões onde estão a meta (r1, r2, r3 ou r4)
e os obstáculos (r1, ... , r7 ou r8).
Figura 5.6: Segmentação do espaço (a) para a posição relativa da meta e (b) para
as localizações relativas dos obstáculos.
5.2.2
Resultados
Planejamento com LPO
Com o nı́vel cognitivo utilizando LPO, a tarefa utilizada no experimento foi: iniciando na posição (−7, −4), o robô deve ir à posição (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. Nesta
figura nota-se a utilização da sintaxe da linguagem do sistema de produção do AAC
(que consta na Figura 3.14).
Figura 5.7: Base de regras para o nı́vel cognitivo utilizando LPO.
60
O único objeto presente é o “meta local”, cujos atributos e respectivos possı́veis
valores são listados abaixo:
• o atributo “atual” pode receber os valores “ir para ponto1”, correspondente à
execução da primeira meta local, “ir para ponto2”, correspondente à execução
da segunda meta local ou “nenhuma”; e
• o atributo “status”, por sua vez, tem como possı́veis valores “ativa” (indicando uma meta em execução), “sucesso” (indicando uma meta alcançada) ou
“f alha” (para uma meta que não pôde ser alcançada).
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 representação de
conhecimento, 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 : alcançou meta 1.
• G2 : alcançou meta 2.
• going to none: agente não está indo a nenhuma meta.
• going to G1 : agente em direção à meta 1.
61
• going to G2 : agente em direção à meta 2.
• x1 and x2: variáveis auxiliares para deixar as regras na FNS.
As regras utilizadas são listadas nas Tabelas 5.1 (regras de inı́cio e de eventualidade) e 5.2 (regras de próximo instante), acompanhadas por uma descrição.
Tabela 5.1: Regras de inı́cio e de eventualidade
Regra
inı́cio ⇒ going to none
inı́cio ⇒ ¬G1 ∧ ¬G2
inı́cio ⇒ x1 ∧ x2
x1 ⇒ ♦G1
x2 ⇒ ♦G2
going to none ⇒ going to G1
Descrição
Inicialmente o robô não está indo
a nenhuma meta.
Inicialmente nenhuma meta foi alcançada.
Inicialmente as variáveis auxiliares
são verdadeiras
x1 faz ♦G1 válida inicialmente.
x2 faz ♦G2 válida inicialmente.
Vai para G1 .
Tabela 5.2: Regras de próximo instante
Regra
¬G1 ⇒ e(¬G2 )
Descrição
G2 não pode ocorrer se G1 não ocorreu.
Mantém-se indo a G1 se meta 1 não foi
alcançada
Se ainda está indo a G1 neste instante,
não terá alcançado no próximo.
Se não está mais indo a G1 , deve estar
indo a G2 .
Mantém-se indo a G2 se meta 2 não foi
alcançada.
Se ainda está indo a G2 neste instante,
não terá alcançado no próximo.
¬G1 ∧ going to G1 ⇒ egoing to G1
going to G1 ⇒ e(¬G1 )
¬going to G1 ⇒ egoing to G2
going to G2 ∧ ¬G2 ⇒ egoing to G2
going to G2 ⇒ e(¬G2 )
O resultado é mostrado na Figura 5.9.
5.3
Placa de Circuito Impresso
O presente trabalho também produziu como resultado o projeto de uma placa de
circuito impresso com a rede de microcontroladores para o AxéBot. O projeto é
62
Figura 5.9: Resultado para navegação com LTP: em verde o ponto inicial, e em
amarelo as metas.
mostrado na Figura 5.10. Esta placa encontra-se em processo de confecção e por
isso não foi utilizada para a realização 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 utilizado. O circuito resultante é mostrado na Figura 5.11, onde “IC4” e “IC5” cor63
respondem aos CIs (Circuitos Integrados) dos transceivers do lado do PSoC e do
mbed, respectivamente. O CI escolhido para a função foi o SN65HVD255D da Texas Instruments, que possui tensão nominal de entrada de 5V e suporta taxas de
transmissão de até 1Mbps.
Figura 5.11: Esquemático do barramento CAN.
O diagrama de blocos da rede Ethernet na placa se assemelha àquele da Figura
5.4, com a diferença que o transceiver Ethernet do mbed é também ligado a uma
porta RJ45 com isolamento magnético na placa. Além disso, a placa conta com
interfaces para os seguintes sensores:
• CMPS03 (compasso magnético): possui uma precisão de 0,1o , e a leitura do
valor medido pode ser feita via I2C (Inter-Integrated Circuit) ou PWM (Pulse
Width Modulation);
• GP2D02 (sensor de distância infravermelho): muito bom para medidas entre
10 e 80cm, e a leitura do valor medido é realizada de através do envio de uma
sequência de pulsos para o sensor, o qual retorna sincronamente os 8 bits do
valor medido;
• DE-ACCM5G (acelerômetro): acelerômetro com dois eixos e uma saı́da analógica para cada eixo; possui escala completa de ±5g.
5.4
Conclusão
No presente capı́tulo foram descritos os resultados de exprimentos utilizando o
AAC embarcado em uma rede de microcontroladores. Os experimentos com o nı́vel
reativo utilizaram o robô AxéBot, enquanto que os demais foram realizados com
um robô simulado. Adicionalmente, uma placa de circuito impresso contendo esta
rede é mostrada no final da seção. Esta placa encontra-se em processo de confecção.
Com os resultados apresentados neste capı́tulo, mostrou-se que o AAC pode utilizar
a arquitetura de hardware proposta para tarefas de navegação e planejamento em
robótica móvel.
64
Capı́tulo 6
Conclusão
Neste trabalho uma rede de microcontroladores foi projetada para comportar a
arquitetura cognitiva do AAC. A rede foi concebida mimetizando a estrutura funcional do AAC: os três nı́veis deste último (a saber, o nı́vel reativo, o nı́vel instintivo e
o nı́vel cognitivo) foram embarcados em cada nó da rede, cujas interfaces de comunicação foram utilizadas para implementar a troca de mensagens entre estes nı́veis.
O nı́vel reativo, responsável pela resposta em tempo real do agente, foi embarcado
no PSoC 5LP, e consistiu basicamente de um controlador cinemático de posição
baseado no modelo do robô omnidirecional AxéBot. Este nó se comunica através de
um barramento CAN com o mbed, um módulo microcontrolado onde foi embarcado
o nı́vel instintivo. Um sistema baseado em conhecimento com uma base de regras em
LPO foi implementado neste nı́vel para coordenar a seleção de comportamentos no
nı́vel reativo. O nı́vel cognitivo do AAC foi embarcado no DIL-Net PC 2486. Este nó
se comunica com o mbed através de uma rede Ethernet. Na implementação original
do AAC, o nı́vel cognitivo implementou um sistema baseado em conhecimento como
método de raciocı́nio automático que utilizava LPO e quadros como formalismos para
a composição da base de conhecimento. Outrossim, neste trabalho foi implementado
um motor de inferência baseado no algoritmo MetateM para execução de uma base
de regras em LTP.
Os primeiros experimentos para validação desta arquitetura de hardware envolveram apenas o nı́vel reativo, onde se comprovou o correto funcionamento do controlador cinemático de posição, seja para estabilização em um ponto ou para rastreamento
de trajetórias. Em seguida, experimentos com a rede completa confirmaram a performance do sistema completo, com o nı́vel cognitivo utilizando LPO e em seguida
LTP como formalismos de representação do conhecimento.
Com isso, este trabalho mostrou que a arquitetura de hardware concorrente proposta atende satisfatoriamente às demandas de concorrência e comunicação do AAC.
Adicionalmente, a arquitetura mostrou-se flexı́vel e modular, pois permitiu que um
novo método de inferência pudesse ser utilizado em um dos nı́veis da arquitetura
cognitiva, fato este importante para pesquisas posteriores em IA que utilizem o
AAC.
65
Não obstante o sucesso obtido nos experimentos, o mbed mostrou severas limitações em termos de recursos computacionais, o que sugere que em pesquisas posteriores este seja substituı́do por um nó computacional mais robusto. Além disso,
para usufruir inteiramente das vantagens de se utilizar uma lógica temporal, a LTP
pode ser substituı́da pela lógica temporal de primeira ordem, para a qual o algoritmo MetateM possui uma extensão. Por fim, os experimentos que fizeram uso
da arquitetura completa utilizaram um robô simulado; a placa de circuito impresso
projetada neste trabalho possibilitará testes futuros com robôs reais, o que deve
fortalecer ainda mais o uso desta arquitetura de hardware com o AAC.
66
Referências Bibliográficas
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 atmosférico. Dissertação 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 Engineers 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, Cristiano 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 Conference 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 Cognitive Angents and Agent Interaction.
Bittencourt, Guilherme (2006). Inteligência artificial: ferramentas e teorias. Editora
da UFSC.
Brachman, Ronald e Hector Levesque (2004). Knowledge representation and reasoning. 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: Simpósio Brasileiro de Automação Inteligente
2013.
Costa, A. L. da e G. Bittencourt (1999). From a concurrent architecture to a concurrent autonomous agents architecture. Lecture Notes in Artificial Inteligence
1856, 85–90.
Costa, P. J., A. G. S. Conceição, T. T. Ribeiro e J. Junior (2011). Embarcando
o agente autônomo concorrente no robô móvel omnidirecional axébot: Nı́vel
reativo. Em: X Simpósio Brasileiro de Automação Inteligente (SBAI), 2011.
Proceedings of the 2011. Vol. X.
Córdoba-Montiel, F., S. F. Hernández-Machuca e D. Hernández-Ventura (2004).
Hybrid microcontrollers network for distributed instrumentation. Journal of
Applied Research and Technology 2(2), 179–188.
R 5LP Architecture TRM (Technical Refrence Manual).
Cyp (2013). PSoC
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 Gonçalves (2003). Expert–coop++: Ambiente para desenvolvimento de sistemas multiagente.. ENIA-Encontro Nacional de Inteligência
Artificial.
da Costa, Augusto Loureiro e Guilherme Bittencourt (2000). From a concurrent
architecture to a concurrent autonomous agents architecture. Em: RoboCup99: Robot Soccer World Cup III. pp. 274–285. Springer.
da Costa; G. Bittencourt; L. R. Silva; E. M. N. Gonçalves, A. L. (2003).
Expert-coop++: Ambiente para desenvolvimento de sistemas multiagente.
http://www.expert-coop.ufba.br/,.
de Santana Júnior, OV e AL Costa (2007). Mecateam 2006: Um sistema multiagente
reativo para futebol de robôs simulados. VII Escola Regional de Computaçao
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 logic 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 Knowledge 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 Temporal Logic. John Wiley and Sons, Ltd.
Fitting, Melvin (1996). First-order logic and automated theorem proving. Springer.
R 5lp.
Fosler, Ross M. (2012). An77759 - getting started with psoc
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 temporal 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 understanding 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). Cognitive 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:
aplicações, tendências e implicações - um estudo exploratório em empresas brasileiras. Dissertação 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.. Cypress 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 trajetória de robôs omni-direcionais: Uma
abordagem multivariável. Dissertação 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 problem. 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̀ robótica móvel.
Trabalho Final de Graduação, UFBA.
Ribeiro, Tiago T., Jovelino T. dos Santos, André G. S. Conceição e Augusto L.
da Costa (2011). Sistema microprocessado para controle em tempo real de robôs
71
móveis ominidrecionais. Em: X SBAI Simpósio Brasileiro de Automação Inteligente.
Russel, Stuart e Peter Norvig (2004). Inteligência Artificial. Elsevier.
Santos, J. T. (2010). Projeto e desenvolvimento de um sistema microprocessado
aplicado à robótica móvel. Trabalho Final de Graduação, 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). Kinematics 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

do arquivo

Transcrição

Documentos relacionados

Bolo do Caco Bimby: 27 min Ingredientes: 1 c. café sal

Nota de Alta

Fettuccine à Alfredo Ingredientes: 400 g massa fettuccine ou

Sopa de Castanhas Ingredientes: 1 cebola 40 g azeite 50 g linguiça

Jardineira de Carne

autorização do responsável

Empanada de Frango com Sultanas Ingredientes p/ a massa

Inteligência Artificial

FORA DA ORDEM: FOTOGRAFIAS DA NATIONAL GEOGRAPHIC

Mini pizza com escabeche Ingredientes: 1 receita de