Robótica Cognitiva Projeto FAPESP: 03/08311-3 (out/03 - set/04) IME - USP

Monografia do trabalho de formatura

Parte I

Introdução

Uma das maneiras para desenvolver um agente inteligente é através de sua especificação em um formalismo lógico. Em especial, na área de Robótica Cognitiva (RC), em que os domínios de aplicação envolvem o raciocínio sobre ações e atualização do estado do mundo, a especificação formal do agente se torna mais interessante. Isso acontece porque dada uma especificação em linguagem lógica, juntamente com um mecanismo correto de inferência, é possível obter e provar o comportamento desse agente.

Assim, a área de Robótica Cognitiva (RC) se preocupa em estudar as capacidades de um agente inteligente cuja implementação se baseia numa especificação lógica. Os problemas de maior interesse da RC envolvem mundos dinâmicos e mundos com informação incompleta, ou seja, onde o agente não conhece a priori todas as características do ambiente.

Nesse projeto, para a construção de um agente inteligente imerso em um mundo com informação incompleta, foi escolhido como formalismo lógico o Cálculo de Situações, uma extensão do Cálculo de Predicados de Primeira Ordem. Com esse formalismo, é possível raciocinar sobre ações e seus efeitos, permitindo a criação de planos de ações e a representação de mundos dinâmicos e com informação incompleta como, por exemplo, o Mundo do Wumpus [1]. Outro motivo que levou a escolha desse formalismo lógico foi o fato dele ser a base da linguagem de programação Golog [2]: uma linguagem de programação de agentes robóticos proposta por pesquisadores de RC [4], e que foi usada para implementar o agente proposto nesse projeto.

O domínio de exemplo escolhido para esse projeto é o problema clássico do Mundo do Wumpus. Um agente que resolva o problema do Mundo do Wumpus [1] deve ser capaz de raciocinar sobre a aplicação de suas ações e seus efeitos, bem como executar ações. Além disso, o agente possui percepção local e portanto deve planejar suas ações com informação incompleta do mundo.

Objetivos do trabalho

O principal objetivo desse projeto é desenvolver a especificação lógica de um agente inteligente imerso em um mundo dinâmico com informação incompleta. Esse agente também deve ser capaz de raciocinar sobre a aplicação de suas ações e seus efeitos, bem como executá-las. Além disso, o projeto ainda prevê a implementação desse agente, usando como base a sua especificação lógica, em três diferentes linguagens: Prolog, Golog e Legolog. Os outros objetivos do projeto são:

• Produzir material sobre o desenvolvimento de agentes inteligentes, em especial dos agentes implementados nesse projeto.
• Implementação de um ambiente virtual para teste de agentes inteligentes escritos em Golog para o Mundo do Wumpus.

Metodologia empregada

Para desenvolver esse projeto de Iniciação Científica, foram realizadas reuniões semanais com o orientadora, sendo em pontos mais teóricos, como a modelagem do agente em Cálculo de Situações, a quantidade de reuniões se intensificaram. Os principais pontos de discussão foram:

• Elaboração da proposta de bolsa para a FAPESP
• Definir um especificação para o Mundo do Wumpus usado como domínio de exemplo no projeto
• Modelagem em Cálculo de Situações do agente para o Mundo do Wumpus
• Criar um planejador para Cálculo de Situações em Prolog
• Definir interface dos módulos do agente em Prolog
• Estudo de Golog
• Implementação do agente em Golog
• Implementação do agente em Legolog
• Definir o escopo do material didático que foi produzido
• Redação do material didático
• Modelagem do sistema de virtual para teste de agentes
• Implementação do sistema virtual de teste de agentes
• Elaboração dos relatórios da FAPESP

A implementação dos agentes foi feita de forma gradativa, iniciando pelo agente em Prolog (mais simples) e terminando com o agente em Legolog. Todos os agentes foram desenvolvidos seguindo os conceitos definidos pela área de Robótica Cognitiva, que consiste em elaborar um especificação formal para o agente, que nesse projeto foi feito em Cálculo de Situações, e implementar o agente baseado totalmente nessa especificação. Além disso, a implementação dos agentes foi divida em módulos, que puderam ser reaproveitados nas outras versões de agentes.

Domínio de exemplo

Como domínio de exemplo para esse projeto será usado o problema clássico do Mundo do Wumpus. Esse problema consiste em um reticulado, cercado por paredes que modelam uma caverna cuja exploração será feita pelo agente. O agente só tem acesso à informação local do mundo, ou seja, da posição do reticulado em que ele estiver localizado. Durante sua jornada, o agente poderá se deparar com o Wumpus - um monstro que o devorará -, um abismo no qual a queda do agente implica na sua morte ou uma pepita de ouro.

O objetivo do agente é encontrar o ouro e escalar a saída da caverna (a mesma de entrada) sem ser morto pelo Wumpus ou pela queda no abismo. Para comparar soluções diferentes, é adotado um sistema de pontuação, onde o agente perde 1 ponto para cada ação realizada, perde 10.000 pontos se ele for morto e ganha 1.000 pontos se sair da caverna com o ouro. A montagem do reticulado deve obedecer as seguintes regras:

• Todo o reticulado deve conter um Wumpus e pelo menos uma pepita de ouro.
• Qualquer posição, com excessão da inicial, tem probabilidade de 0.2 de ser um abismo.
• As posições diretamente adjacentes ao Wumpus (posições adjacentes, excluindo as diagonais) serão marcadas como Stench, indicando sua proximidade. De forma análoga, a adjancência direta do abismo será marcada como Breezy.
• Quando o agente estiver na mesma posição do ouro, ele perceberá o seu brilho, ou seja, a posição será marcada como Glitter.
• Ao matar o Wumpus, através do disparo de uma flecha, o agente percebe um grito (Scream) indicando a morte do Wumpus. Depois de morto, o Wumpus não oferece mais risco ao agente.
• Se o agente tentar caminhar para uma posição que é uma parede, ele perceberá o choque (Bump) e continuará na mesma posição.
• O único meio de comunicação entre o agente e o ambiente será através da ação percept, que retorna um vetor com 5 percepções, Stench, Breeze, Glitter, Scream, Bump, e caso alguma delas não ocorra, sua posição no vetor terá o valor None.

As outras ações possíveis no Mundo do Wumpus são:

• Turn(direction): muda a orientação do agente no mapa. As possíveis orientações são: North, South, East ou West, definidas respectivamente pelos vetores: (0, 1), (0, -1), (1, 0) e (-1, 0).
• Foward: faz o agente avançar uma posição na sua atual direção.
• Grab(object): o agente pega e segura um objeto (object).
• Release(object): solta um objeto (object).
• Climb: faz com que o agente escale a parede de entrada da caverna. Essa ação só pode ser realizada se o agente estiver na posição inicial da caverna.
• Shoot: atira uma flecha na direção em que o agente está virado. Essa ação só pode ser realizada se o agente possuir uma flecha.

Trabalhos correlatos

Durante o projeto foi estudado alguns artigos relacionados Golog e à modelagem de aplicações para Golog. A lista completa de artigos estudados pode ser encontrada na página de referências.

Artificial Intelligence: Modern Approach [1]

Nesse livro, o mais usado na área de IA atualmente, é exibido o problema do Mundo do Wumpus e também é fornecido alguns axiomas para um agente capaz de solucioná-lo. No entanto, o material fornecido limita-se a um agente reflexivo, isso é, outras formas de raciocínio, mais complexas, não são fornecidas pelo livro. A Figura 1 representa a divisão em sub-tarefas para um agente capaz de resolver o problema do Mundo do Wumpus, onde as ovais simples são apresentadas parcialmente ou integralmente pelo livro e as ovais duplas indicam as tarefas modeladas de forma original por esse projeto.

Figura 1: Divisão em sub-tarefas para o Mundo do Wumpus. As ovais duplas representam as tarefas totalmente originais do projeto.

Legolog: Inexpensive Experiments in Cognitive Robotics [3]

Esse artigo apresenta a linguagem Legolog, para isso, é usado como domínio de exemplo o problema do robô entregador de pacotes. Esse domínio consiste em um agente que anda sobre uma linha, representando o seu caminho, e leva pacotes de estações para outra nessa linha, onde as estações são demarcadas na própria linha. As semelhanças da modelagem desse domínio com o Mundo do Wumpus está na forma de deslocamento e na existência de marcas de parada, as quais no domínio do entregador de pacotes são seqüências (uma dimensão) e no Mundo do Wumpus são representadas por uma matriz (duas dimensões) (Figura 2).

   
Figura 2: A esquerda a maquete para o domínio do entregador de pacotes e a direita a maquete para o domínio do Mundo do Wumpus.

Tópicos estudados

Cálculo de Situações

O cálculo de situações é um formalismo lógico para axiomatização de mundos dinâmicos e pode ser definido como uma extesão da lógica de primeira-ordem com três tipos disjuntos de termos:

1. Ações, responsáveis pelas mudanças no estado do mundo;
2. Situações, representam estados do mundo como resultado da execução de uma seqüência de ações que, por sua vez, representa uma possível história do mundo;
3. Fluentes, representam relações e propriedades do mundo cujos valores mudam de situação para situação.

Essa linguagem inclui símbolos funcionais para ações, como por exemplo, no Mundo do Wumpus o símbolo grab(o) tem como significado a ação do agente pegar o objeto o e guardá-lo por tempo intedermindo. A linguagem também inclui uma constante especial S₀ que denota a situação inicial do mundo, em que nenhuma ação foi executada, e um símbolo funcional do que funciona como um construtor binário, onde do(a, s) denota a situação que resulta da execução da ação a na situação s. Por exemplo, o termo situação:

do(shoot, do(grab(arrow), S₀))

denota a situação resultante da execução, a partir de S₀, onde o agente pegou uma flecha (do(grab(arrow), S₀)) e depois atirou essa flecha (do(shoot, do(grab(arrow), S₀))).

O último tipo de termo, os fluentes, tem como finalidade especificar ropriedades sobre o ambiente. Em especial no Mundo do Wumpus, eles descrevem as caracteríscas de cada posição, mantêm informações sobre o agente (sua localização e quais objetos ele possui) e categorizam as ações que podem ser executadas em cada situação. Como essas características podem variar conforme a situação, é adicionado um argumento dos fluentes a situação a qual a propriedade deve ser verificada, por exemplo, holding(o, S₀) verfica se o agente está segunrando o objeto o na situação S₀.

Usando os três tipos de termos descritos acima, uma axiomatização do cálculo de situações para um domínio deve incluir:

• axiomas de pré-condições de ação, especificando em que situações é possível executar uma ação;
• axiomas de estado sucessor, especificando como um fluente muda ou permanece inalterado com a execução de ações; e
• axiomas de situação inicial: sentenças descrevendo o que é verdadeiro em S₀.

Golog

Golog é uma linguagem criada pelo Grupo de Robótica Cognitiva da Universidade de Toronto, baseada no cálculo de situações, que oferece vantagens para aplicações em domínios dinâmicos, como programação de alto nível de agentes de software ou robóticos, controle de processos, simulação de eventos discretos, etc. Essa é uma linguagem estruturada e, como tal, oferece estruturas de controle (desvios condicionais e laços) e chamadas de procedimentos, no entanto, diferentemente de outras linguagens estruturadas convencionais, programas Golog decompõe-se em primitivas que se referem a ações do mundo. A execução dessas primitivas deve obedecer as condições dadas por axiomas do cálculo de situações, tornando possível o raciocínio lógico sobre o programa.

Programas Golog são avaliados por meio de um provador de teoremas, mais especificamente, o meta-interpretador Golog é implementado atualmente em Prolog. Para programar em Golog, o usuário deve fornecer axiomas de pré-condição (um por ação), axiomas de estado sucessor (um por fluente), uma especificação do estado inicial e os procedimentos escritos em Golog, usando as seguintes construções:

• Condição de teste: φ?, testa se φ, um fluente, é verdadeiro na situação atual.
• Seqüência: δ₁:δ₂, executa δ₁ seguido de δ₂, onde δ_i é uma ação ou um procedimento.
• Escolha não-determinística de ação: δ₁#δ₂, executa δ₁ ou δ₁.
• Escolha não-determinística de argumentos: (π x) δ, escolhe um valor para x e executa δ para aquele valor.
• Iteração não-determinística: δ*, executa δ zero ou mais vezes.
• Condicional: if φ then δ₁ else δ₂. Se φ é verdadeiro, executa δ₁; caso contrário, executa δ₂.
• Laço: while φ do δ. Enquanto φ é verdadeiro, executa δ.
• Definição de procedimentos: proc P(x₁ ... x_n) δ endProc. P é o nome do procedimento, x₁ ... x_n são os n parâmetros de P e δ é o corpo do procedimento.

O robô Lego® Mindstorm™

O robô Lego® Mindstorm™ faz parte do conjunto básico RIS (Robotics Invention System ™), que é composto por (Figura 3):

• bloco RCX (Robotic Commander Explorer), que contém um microprocessador Hitachi H8/3297 de 16 bits, juntamente com uma máquina virtual implementada para ele em um firmware;
• sensores: um sensor de luz/contraste, que mede a quantidade de luz refletida por uma superfície e dois botões, que podem ser usados como sensores de toque;
• atuadores: dois motores que possuem cinco intensidades de funcionamento diferentes para ambas as direções (frente e trás) e
• torre de infravermelho: um transmissor infravermelho que é ligado na porta serial do computador para comunicação com o bloco RCX.

Figura 3: bloco RCX, pilha AA (para referência de tamanho), sensor de toquem sensor de contraste motor e torre de infravermelho.

O bloco RCX é o responsável por controlar até três entradas (sensores) e três saídas (atuadores) de forma simultânea e também permite a execução concorrente de até quatro tarefas. Além disso, ele possui uma porta de infravermelho usada para se comunicar com o PC através da torre infravermelho, ou outros RCXs.

No pacote de softwares fornecido pelo RIS, há uma linguagem de programação visual, chamada Robolab. Nessa linguagem é possível construir programas para o bloco RCX integrando figuras (similares a peças de quebra-cabeça) e configurando parâmetros para elas. Cada uma dessas figuras representa comandos (palavras reservadas) de uma linguagem de programação, como if, for e while. Depois de pronto, o programa é compilado para a máquina virtual que é implementada pelo firmware do bloco RCX. Além desse software, também existem outros compiladores capazes de gerar código para essa máquina virtual, como por exemplo o NQC (not-quite C). Uma vez compilado, o programa deve ser enviado, via infravermelho, para o bloco RCX, onde ele será armazenado e depois executado.

Legolog

Legolog[3] é uma linguagem para programação de robôs Lego® Mindstorm™ baseada na linguagem IndiGolog (uma extensão do Golog), proposta pelo grupo de Robótica Cognitiva da Universidade de Toronto. Essa linguagem pode ser usada para modelar aplicações do tipo cliente e servidor (Figura 4), em que o bloco RCX, parte responsável pelo processamento dos robôs Lego® Mindstorm™, é o servidor de atuadores e sensores, e o computador (executando o meta-interpretador Legolog) é o cliente. A comunicação entre cliente e servidor é feita através da troca de um número inteiro por um protocolo de mensagens via infravermelho.

Figura 4: Decomposição do pacote Legolog.

Dessa forma, um programa de controle de robô em Legolog é dividido em duas partes:

• Programa de raciocínio do agente, que fica armazenado no computador e que é executado pelo meta-interpretador Legolog. Este programa, ao ser executado, faz a geração incremental (online) de planos de ações primitivas, considerando as percepções do robô e a ocorrência de ações exógenas.
• Programa de execução de ações, especificadas pelo Legolog que implementa: (i) como serão executadas as ações primitivas; (ii) como serão executadas as ações de sensoriamento (percepções) e (iii) a monitoração de ações exógenas.

Através dessa divisão do programa, o projetista é capaz de definir o nível de abstração de ações delegadas ao robô Lego® Mindstorm™, isto é, seu grau de autonomia. Assim, o robô pode ser programado para apenas controlar suas entradas e saídas; ou pode implementar ações mais complexas, como por exemplo, seguir uma linha, encontrar um objeto, permanecer dentro de uma área limitada, etc.

Como o Legolog já trás a implementação do protocolo de comunicação entre cliente e servidor, após ter definido o nível de abstração das ações delegadas ao bloco RCX, a criação de um programa de um agente robótico em Legolog resume-se em três passos: (i) criar o programa do agente em IndiGolog, (ii) criar as tabelas que relacionam as ações primitivas do Legolog às ações que podem ser executadas diretamente pelo bloco RCX, sejam elas ações de atuação, de sensoriamento ou de monitoração de ações exógenas e (iii) implementar as ações primitivas na linguagem da máquina virtual do firmware do bloco RCX.

A construção do código para a máquina virtual implementada pelo firmware da LEGO é feita usando o compilador NQC (not-quite C). Esse compilador usa uma linguagem semelhante a C, acrescida de comandos para configurar, ativar e desativar os atuadores, receber informações dos sensores e executar de forma concorrente funções do tipo task. Essa linguagem também apresenta algumas restrições, entre elas: (i) só existem variáveis globais; (ii) as funções só podem ser do tipo void; (iii) as variáveis só podem ser do tipo int; (iv) todo o programa deve ter uma task chamada main, restando espaço para serem executadas mais três tarefas concorrentemente.

Assim, é possível ver o Legolog como um pacote de software que contém um meta-interpretador (Indigolog), que não será embarcado no bloco RCX (cliente), mais a implementação de um protocolo de comunicação entre as duas plataformas (o bloco RCX e o computador) permitindo a troca de mensagens durante a execução de um programa no bloco RCX.

Sistemas desenvolvidos

Agente em Prolog

A especificação lógica do agente foi implementada inicialmente em Prolog. Essa primeira versão do agente foi feita para um problema relaxado do Mundo do Wumpus, com o objetivo de descobrir erros nos axiomas básicos da especificação lógica do agente. Assim, no problema relaxado, foram considerados apenas os axiomas do Cálculo de Situações, ignorando-se o raciocínio sobre a classificação de ações e situações, a escolha da melhor ação e objetivo de matar o Wumpus.

Para isso, o agente utiliza o algoritmo de busca em profundidade iterativa no espaço de ações (Figura 5), garantindo que todas as ações possíveis serão testadas. Como o algoritmo de busca usado é completo, isto é, se existir uma solução, ela será encontrada, o agente necessariamente deve encontrar uma solução para cada problema. Isso porque pelo menos a solução trivial, sair da caverna sem explorá-la, é sempre possível, logo, se o agente não encontrar uma solução, a especificação lógica está com incorreta.

Figura 5: Funcionamento do programa do agente para o problema relaxado do Mundo do Wumpus.

Depois de testar os axiomas básicos da modelagem feita, foi necessário testar as formas mais complexas de raciocínio, que são: (i) a classificação de ações e situações, (ii) a escolha da melhor ação e (iii) encontrar e matar o Wumpus. Como nessa versão do agente todas as formas de raciocínio propostas estão presentes (problema completo), o agente não deverá realizar backtracking, ou seja, uma vez que ele executou uma ação, ela não poderá ser desfeita. Dessa forma, o algoritmo de busca em profundidade iterativa é substituido pela escolha de uma ação, representada pelo predicado find_action. A Figura 6 mostra o funcionamento do agente, onde as caixas pontilhadas são módulos do programa e serão comentados a seguir.

Figura 6: Funcionamento do programa do agente em Prolog para o problema completo do Mundo do Wumpus.

Para deixar a implementação do agente mais clara, foi feito a divisão do código fonte em vários arquivos, que serão chamados de módulos. Como conseqüência dessa modularização, a implementação atual do programa, além de resolver o problema completo, possui um recurso adicional, chamado de troca de personalidades, que é indicado pelo retângulo "Personalidade do agente" na Figura 1.

Uma personalidade para o agente do Mundo do Wumpus é a forma como esse agente categoriza, através de uma ordem de preferência, as ações que podem ser executadas naquele instante. Por isso, a troca da personalidade do agente reflete diretamente nas decisões que ele irá tomar. Por exemplo, é possível criar uma personalidade onde o agente procura e mata o Wumpus e se, ocasionalmente, encontrar a pepita de ouro, ele a pega. Por outro lado, também é possível criar outra personalidade de agente que procura pela pepita de ouro e nunca mata o Wumpus.

Computacionalmente, a troca de personalidade nada mais é do que a uma modificação no módulo de personalidade do agente, mantendo todo o resto do código, ilustrado na Figura 6, inalterado. Assim, podemos implementar diferentes agentes para o Mundo do Wumpus mudando apenas um pequeno trecho de código, possibilitando também simulação de algumas das diferentes versões do problema do Mundo do Wumpus.

Agente em Golog

Para implementar o programa do agente do Mundo do Wumpus em Golog, foi usado o mesmo conceito de modularização utilizado na construção do agente em Prolog. Graças à isso, essa etapa do projeto se resumiu a implementar as personalidades do agente em Golog e modificar o meta-interpretador Golog. Essas duas etapas serão comentadas a seguir.

A Figura 7 ilustra o funcionamento do agente em Golog, onde a escolha de ações, que faz parte do módulo do Agente (personalidade), foi implementada usando a escolha não determinística de ações através do operador # de Golog. Esse operador infixo recebe dois programas Golog e tenta executar um deles e caso este não seja executado com sucesso, o outro programa será executado.

Figura 7: Funcionamento do programa do agente em Golog para o problema completo do Mundo do Wumpus.

Uma característica desse operador é que ele padece do mesmo mal que o Prolog, ou seja, sua escolha é feita na ordem em que os argumentos foram escritos. Isso significa que a sua escolha não determinísca é previsível, ou seja, no trecho de código Golog A # B sempre A será executado primeiro, e caso falhe, B será executado. Devido essa peculiaridade desse operador, a escolha de ações foi implementada como a escolha não determinística de todas as categorias de ações possíveis, onde o agente irá tentar primeiro as ações que aumentam a sua pontuação e por último (caso todas falhem), o agente irá sair da caverna.

Como Golog realiza planejamento offline, ou seja, primeiro é deliberado um plano solução e depois ele é executado, foi necessário alterar o meta-interpretador para ele realizar planejamento online. O principal motivo para o meta-interpretador Golog ter que executar cada ação escolhida e não poder desfazê-la é devido ao sensoriamento do mundo: no Mundo do Wumpus,o agente usa as percepções adquiridas até o momento para raciocinar sobre suas próximas ações, logo, o agente não poderá mais deliberar planos de ações, mas sim escolher a melhor ação naquele momento e executá-la.

Agente em Legolog

A implementação do agente em Legolog foi totalmente baseada na implementação já feita em Golog. Assim, nessa etapa foi necessário decompor o conjunto de ações já criadas em ações primitivas para o Legolog e ações primitivas para o bloco RCX. Além disso, também foi necessário implementar as ações primitivas para o bloco RCX, usando como linguagem o NQC.

Na decomposição escolhida para a implementação do Mundo do Wumpus em Legolog, a captação das percepções de uma posição (glitter, stench e breezy), de forma não ordenada, é implementada como uma ação primitiva entre o computador e o RCX. Isso é, a tarefa de coleta de percepções do agente é feita de forma autônoma pelo RCX. O algoritmo para captar percepções consiste em levar o robô até uma marca de giro, realizar um giro de 360 graus, coletar as percepções e retornar à posição anterior. Como cada posição é dividida em quatro partes (Figura 8), o algoritmo de giro consiste em quatro iterações da função ilustrada pelo Algoritmo 1, escrita em NQC.

Figura 8: Modelo de cada posição do Mundo do Wumpus.

Algoritmo 1: Essa função realiza um quarto de volta (90⁰) e caso seja encontrado uma marca de percepção, a variável global boolean_sense receberá o valor TRUE, caso contrário, o valor FALSE

void get_boolean_sense() {

    // Reiniciando a variável global
    boolean_sense = FALSE;
    
    // Girando no fundo até achar algo
    turnToExitMark(BACKGROUND_DIF_MIN, BACKGROUND_DIF_MAX, 1);

    // Verificando se ele encontrou a percepção (token foi pego)
    light_dif = LIGHT_SENSOR - valor_base;
    if (light_dif >= SENSE_DIF_MIN && light_dif <= SENSE_DIF_MAX) {
	// Percepção encontrada
	boolean_sense = TRUE;
	PlaySound(SOUND_UP);

	// Saindo da marca de percepção e indo para o fundo
	turnToFindMark(BACKGROUND_DIF_MIN, BACKGROUND_DIF_MAX, 1); 
	// Procurando a linha, mas eventualmente ele pode cair na marca de percepção
	turnToFindMark(LINE_DIF_MIN, MARK_DIF_MAX, 1);
	
    } 
    // Se não foi encontrado um token, o robô já está na linha
}

Como as marcas de percepção são iguais para todas as percepções e elas são distribuídas em cada posição seguindo a Figura 8, o robô não é capaz de distingüir cada uma das percepções captadas. Isso porque o robô pode atingir uma determinada posição por quatro direções distintas (norte, leste, sul e oeste), alterando a ordem em que as marcas são lidas. Por isso, o algoritmo implementado no bloco RCX devolve um vetor de quatro booleans para representar as percepções obtidas de forma não ordenada. Para reordenar as percepções, o meta-interpretador Legolog foi alterado para pré-processar o resultado da percepção, levando em conta a direção atual do agente, e devolve para o programa do agente as percepções já ordenadas. O trecho correspondente ao Algoritmo 2, escrito em Prolog, foi adicionado ao meta-interpretador Legolog para essa finalidade.

Algoritmo 2: O predicado translateSensorValue traduz os valores obtidos pelos sensores. Na versão original do Legolog, esse predicado apenas devolve o valor que foi recebido: translateSensorValue(_, SensorValue, SensorValue). Na implementação do Mundo do Wumpus, o valor da percepção gerada pela ação percept foi traduzida através de shifts circulares da lista de 0s e 1s passada com parâmetro pela variável Vetor.

translateSensorValue(percept, SensorValue, Vetor, H) :-
    % O valor recebido foi SensorValue
    Rot90 is mod(SensorValue, 10) - 1,
    Rot180 is mod(integer(SensorValue/10), 10) - 1,
    Rot270 is mod(integer(SensorValue/100), 10) - 1,
    Rot360 is mod(integer(SensorValue/1000), 10) - 1,
    % O agente está na direção D
    holds(agentDirection = D, H),
    rotacionarPercepcao([Rot90, Rot180, Rot270, Rot360], D, Vetor).
    % O valor recebido foi traduzido para Vetor

As outras ações primitivas usadas na modelagem do Mundo do Wumpus para Legolog são turn_clokwise, turn_anti_clockwise, foward, grab, shoot e climb. Dessas ações, apenas as três primeira movem o robô, girando 90 graus, com ajuda das linhas guias, no sentido horário e anti-horário e avançando uma posição (respectivamente). Para as outras ações, grab, shoot e climb, o robô apenas emite sons indicando que elas foram executadas e esperando que o ambiente seja atualizado manualmente, ou seja, que as marcas de percepção sejam atualizadas.

Ambiente Virtual

No ambiente virtual desenvolvido, de forma similar aos sistemas de olimpíadas de computação, o aluno submete pelo site o seu agente e espera a notificação por email que a execução da bateria de testes seja concluída. Quando a notificação for recebida, o aluno acessa o sistema e pode ver a animação da execução do seu agente em um ambiente do Mundo do Wumpus. A escolha do ambiente é feita conforme a seguinte regra, se o agente submetido passou por todos os casos de testes sem morrer, o ambiente escolhido será aquele onde foi obtida a menor pontuação (para servir como uma referência de situação para a qual o programa deve ser melhorado), caso contrário, é escolhido o primeiro ambiente onde o agente morreu.

Para implementar esse sistema foi usada a linguagem PHP, uma linguagem de scripts voltada para fazer aplicações para Internet e a comunicação do agente com o Golog é feita via emails. Com isso, o aluno apenas necessita de um browser comum para submeter e visualizar as simulações. Isso porque os scripts em PHP são processados pelo servidor Web, retornando apenas código HTML. A Figura 9 ilustra o funcionamento do ambiente virtual do Mundo do Wumpus.

Figura 9: Funcionamento do ambiente virtual do Mundo do Wumpus.

Os principais subsistemas do ambiente virtual (Figura 9) são:

• Parser para Golog. Parser para reconhecer uma pequena extensão do Golog, onde o aluno pode programar um agente para o Mundo do Wumpus usando a interface do ambiente e algumas variáveis especiais, como as variáveis para representar hipóteses sobre a posição do Wumpus e dos abismos. A principal função desse subsistema é evitar que o aluno use predicados do Prolog que afetem a segurança do computador que rodará as simulações (agente rejeitado), como leitura e escrita em disco, executar processos, etc.
• Mundo do Wumpus em Golog. Implementação do ambiente do Mundo do Wumpus, já feita na primeira parte do projeto, modificado para gerar como saída parâmetros sobre movimentação do agente e variáveis especiais, como por exemplo, pontuação, hipóteses de Wumpus, quantidade de pepitas pegas.
• Visualizador de Simulações. Sistema feito em PHP que interpreta a saída da execução do agente e gera uma animação em tempo real para a simulação desejada.

A ativação do servidor de CPU, responsável pelo subsistema Mundo do Wumpus em Golog, pode ser feito de três maneiras diferentes, (i) manual, o professor executa um script que ativa o servidor de CPU e todas as simulações acumuladas são realizadas, (ii) programada, em sitemas do tipo UNIX, como o Linux, é possível usar o utilitário cron para programar horários para os quais a ativação manual será executada e (iii) automática, o servidor de CPU é ativado toda a vez que uma simulação é ativada, assim o tempo de resposta para o aluno é apenas o tempo gasto para realizar os testes.

Apesar do modo automático ser o melhor modo para o ambiente, pois o resultado obtido é devolvido para o aluno de forma mais rápida, atualmente, o ambiente é executado na forma programada. Isso porque a execução de maneira automática pode sobrecarregar o servidor de emails, compromentendo o envio e entrega de emails.

Atividades realizadas

Participação em palestras e tutoriais

Durante a primeira parte do projeto, o grupo de Lógica, Inteligência Artificial e Métodos Formais (LIAMF) do Instituto de Matemática de Estatística da USP realizou dois eventos relacionados a esse trabalho. O primeiro, uma palestra sobre a linguagem Golog, foi apresentado pelo aluno de mestrado Edward M. I. Iamamoto, sob orientação da Profa. Leliane Nunes de Barros, e teve como finalidade introduzir a linguagem Golog ao grupo.

O segundo evento, um tutorial de quatro dias sobre Robótica Cognitiva, foi ministrado pelo professor visitante doutor Maurice Pagnucco, da Universidade de New South Wales, Austrália. Nesse tutorial foram abordados temas como, Cálculo de Situações, Golog, Legolog e raciocínio sobre conhecimento e crenças no Cálculo de Situações. Essa visita fez parte do projeto FAPESP CCC-AHIA - Cooperação e Compartilhamento de Conhecimento entre Agentes Heterogêneos Inteligentes e Autônomos.

Palestra para o LIAMF

Na segunda parte do projeto, após o ter sido feito o relatório parcial para a FAPESP, um seminário foi apresentado sobre o projeto. Esse seminário ocorreu no dia 21 de junho de 2004 e teve como público o LIAMF e outros interessados. Os slides criados para essa apresentação podem ser vistos através do site do projeto.

12^o SIICUSP

No dia 25 de novembro de 2004 o poster do projeto foi apresentado no 12^o Simpósio Internacional de Iniciação Científica da USP. O poster usado foi o mesmo apresentado no projeto de formatura e pode ser visto aqui aqui.

Conclusões

Através desse projeto, foi possível aprender como usar a linguagem Golog para a construção de agentes baseados em um especificação lógica, área conhecida como Robótica Cognitiva. Para isso, foram construidas diferentes versões de um agente baseado em lógica para o problema do Mundo do Wumpus. Numa primeira versão, inicialmente baseada na especificação do livro AIMA[1], foi construido um programa Prolog para o problema relaxado (Figura 5) que supõe que o agente possa fazer backtracking mesmo que este tenha sido morto. Na segunda versão, foi construido um programa Prolog para o agente que de fato interage com um ambiente simulado do Mundo do Wumpus (Figura 6), também implementado em Prolog. A terceira versão, em que os maiores desafios surgiram, foi a implementação do agente em Golog (Figura 7) a partir do programa Prolog, o que exigiu o estudo do meta-interpretador Golog e a realização de inúmeros testes do programa.

Na segunda metade da projeto, a proposta foi estendida com a construção de um agente Legolog, versão de Golog para um robô Lego® Mindstorm™. Isso foi motivado com a visita do professor Maurice Pagnucco, da Universidade de New South Wales, autor da linguagem Legolog. Durante sua visita, o professor Maurice apresentou seus últimos resultados de pesquisa em raciocínio sobre conhecimento e crenças na construção de agentes robóticos, incluindo uma demonstração com robôs Lego® Mindstorm™.

O uso da linguagem Legolog mostrou dispensar o conhecimento de hardware para a programação de robôs Lego® Mindstorm™. Esse fator viabiliza o estudo de Robótica Cognitiva em robôs, sem a necessidade de realizar cursos sobre hardwares específicos. Apesar dessa ser uma das vantagens frequentemente apontada por pesquisadores da área, a construção de um robô Lego® Mindstorm™ para esse projeto apresentou uma série de dificuldades, entre elas, a limitação de sensoriamento e capacidade de armazenamento dos robôs Lego® Mindstorm™. Os testes realizados com sucesso nesse robô conseguiram demonstrar o raciocíonio de captação e exploração do ambiente, que correspondem às principais tarefas autônomas do robô. No entanto, devido à imprecisão dos sensores, o robô perde sua linha guia após explorar 2 ou 3 casas do Mundo do Wumpus sendo que para completar uma missão, o robô teve que ser reposicionado.

Uma outra meta desse projeto foi a de estender o Laboratório Virtual de Inteligência Artificial - LabVIA. O LabVIA disponibiliza material didático para cursos de Inteligência Artificial, seguindo a tendência atual de organizar o conteúdo de disciplinasLego® Mindstorm™ de IA de acordo com características de agentes e ambientes. A perspectiva usada nesse laboratório é a do agente racional, similar àquela apresentada no livro Artificial Intelligence: Modern Approach[1] , principal referência desse projeto. Dessa forma, o projeto é dirigido tanto para alunos de graduação, fornecendo uma nova perspectiva para o estudo de IA, quanto para professores ministrantes dessas disciplinas, ajudando na criação de exemplos de integração de técnicas de IA.

O LabVIA enfatiza que a construção do programa de um agente inteligente depende das características do ambiente onde ele se encontra, desta forma é preciso caracterizar os diferentes tipos de ambientes. Esse foi um dos aspectos trabalhados nesse projeto: a construção de páginas com definições de tipos de agentes e ambientes, sendo a ênfase maior foi dada para a construção de um agente inteligente para ambientes estáticos, onde o agente tem informação incompleta e percepção local sobre ele, por exemplo, o agente Mundo do Wumpus. Apesar disso, a nova organização proposta para o LabVIA, prevê que outros problemas possam ser incorporados para a construção de outros agentes definidos do LabVIA.

Para completar as páginas e atividades do tipo de agente abordado, foram ainda construídos, para fins didáticos, dois exemplos simples de programa de agente (além do agente Golog): um agente reativo e um agente baseado em modelo[1] . Além disso, o LabVIA fornece a possibilidade dos alunos criarem e testarem seus próprios agentes no laboratório de agentes, atualmente implementado apenas para o problema do Mundo do Wumpus em Golog.

Bibliografia utilizada

1. RUSSELL, J. Stuart, NORVIG, Peter. Artificial Intelligence: Modern Approach. 1 ed. Prentice Hall, 1995.
2. LEVESQUE, J. Hector, REITER, Raymond, LESPÉRANCE, Yves., LIN, Fangzhen., SCHERL, B. Richard. 1994. GOLOG: A Logic Programming Language for Dynamic Domains}.
3. LEVESQUE, J. Hector, PAGNUCCO, Maurice. 2000. Legolog: Inexpensive Experiments in Cognitive Robotics. Berlin, Germany.
4. Grupo de robótica cognitiva da Universidade de Toronto.http://www.cs.toronto.edu/cogrobo/

Parte II

Desafios e frustrações encontrados

Esse projeto foi desafiador em uma série de pontos, sendo o principal desafio o desenvolvimento de um agente inteligente que resolvesse completamente o problema do Mundo do Wumpus, pois na literatura atual[1] é apresentado apenas as partes mais simples dos agentes (parte reflexiva).

Outro desafio foi a implementação do agente robótico para o problema do Mundo do Wumpus devido as limitações de hardware dos robôs Lego® Mindstorm™. Entre essas limitações estão a precisão dos sensores, o espaço para armazenamento do programa (apenas 512Kbits), etc.

Além dos desafios, o robô foi a principal fonte de frustações do projeto, pois a falta de precisão dos sensores, em especial o sensor de contraste que foi usado para locomoção e captação de percepções, não permite que o robô funcione de forma completamente autônoma, sendo necessário que uma pessoa o coloque em sua posição correta grande parte das vezes que o robô realiza um giro para captar as percepções da posição atual.

Disciplinas do curso mais relevantes para o projeto

Todas as disciplinas do currículo do BCC foram significativas nesse projeto, seja diretamente ou indiretamente, como por exemplo Noções de Probabilidade e Processos Estocásticos (MAE0228) onde é visto o conceito de cadeia de Markov que é citado em alguns artigos. As disciplinas que mais influenciaram esse projeto foram:

• MAC0425 - Introdução à Inteligência Artificial
  Essa disciplina foi fundamental para estabelecer os conceitos básico e a termilogia da área de IA. Os principais tópicos abordados que foram usados no projeto foram: busca heurística, planejamento e Cálculo de Situações.


• MAC0435 - Tópicos de Inteligência Artificial
  Essa é a disciplina coringa do grupo de IA para graduação, onde cada ano um professor aborda um tema diferente. Em 2003 ela foi ministrada pela Profa. Renata Wassermann juntamente com a pós-graduação sobre o nome Raciocínio sobre Conhecimento. O tema mais usado no projeto foi revisão de crenças, possibilitando gerenciar o conhecimento do agente e garantir a sua consistência.


• MAC0444 - Sistemas Baseados em Conhecimento
  Essa disciplina teve participação no projeto pois ela também abordou os temas de Introdução a Inteligência Artificial: busca heurística, planejamento e Cálculo de Situações.


• MAC5734 - Técnicas de Programação Declarativa
  Devido a forma de programação usada no projeto, programação em lógica através do Prolog (uma linguagem declarativa) e Golog (uma linguagem híbrida entra lógica e procedimental), essa disciplina foi grande utilidade. Isso porque nela foram abordados temas como técnicas básicas de programação declarativa, recusões de calda e otmização de código em programação declarativa.


• MAC5789 - Laboratório de Inteligência Artificial
  Essa disciplina, divida em três projetos distintos, teve grande utilidade pois o último projeto, proposto pela Profa. Leliane Nunes de Barros, abordou o tema de planejamento, ampliando o conhecimento sobre a área.

Interação com membros da equipe que tenham agido como mentores do trabalho

Além das reuniões com a Profa. Leliane Nunes de Barros, orientadora do projeto, também foram realizadas algunas reuniões com dois orientandos dela, Silvio do Lago Pereira (doutorando) e Edward Mitsuo Iwanaga Iamamoto (mestrando). A interação com todos eles foi muito boa, sempre contando com muita cooperação e troca de conhecimento, o que enriqueceu o projeto.

Diferenças entre as tarefas em grupo das disciplinas e a forma de trabalho na iniciação científica

Durante os 18 meses de iniciação científica foi possível encontrar algumas diferenças entre o projeto e os trabalhos em grupo, sendo que todas elas deixam o projeto de iniciação científica mais motivante e interessante do que os EPs em grupo. Entre essas diferenças, as principais são:

• Magnitude do projeto, pois um trabalho de iniciação científica possui um tempo de duração e dedicação maior do que um EP, por isso é possível desenvolver ferramentas mais interessantes e completas.


• Tema. Como os objetivos do projeto estão diretamente ligados com os interesses do orientando, a execução da iniciação científica se torna mais prazerosa.


• Conhecimento do completo do projeto. Nos EPs em grupo, geralmente não é possível conhecer completamente o sistema desenvolvido, tão pouco participar de todas as decisões do projeto, pois sempre há delegação de tarefas entre os membros do grupo.

Observações sobre aplicações de conceitos estudados nos cursos em aplicações reais

Apesar do projeto de iniciação científica não ser tão prático como um estágio, foi possível verificar que os conceitos aprendidos durante todo o curso foram úteis. Além das disciplinas já comentadas como mais relevantes no curso, a disciplina de Engenharia de Software (MAC0332) também foi importante. Como durante o curso não é dado a devida importância a essa disciplina, ela deveria ser oferecida de forma diferente. Uma possível abordagem seria tornar a disciplina anual e desenvolver um projeto, como em Laboratório de Programação I e II, usando diferentes técnicas de engenharia de software.

Passos que deverão ser tomados para aprimorar os conhecimentos relevantes

Para aprimorar os conhecimentos obtidos durante a iniciação científica, será realizado o programa de mestrado em Ciência da Computação do IME, tendo como tema planejamento, monitoração e execução de ações e replanejamento. Além disso, outros artigos sobre a área de Planejamento serão estudados, oferecendo uma visão mais abrangente da área.

Agradecimentos

Agradeço a todos os meus colegas pelos quatro anos de boa convivência e ajuda quando necessário, enriquecendo a minha formação. Também agradeço aos meus pais pela total dedicação por todos esses anos, em especial nesses quatro anos de BCC, onde pude estudar tranqüilamente. Por último, agraço também aos professores do IME aos quais devo boa parte do que aprendi durante o curso e em especial a minha orientadora, Profa. Leliane Nunes de Barros, que apesar de todos os percalços, sempre esteve presente.