Regras e Encadeamentos - USP€¦ · Encadeamento para frente: Um sistema baseado em regras que executa encadeamento para frente utiliza assertivas dadas e assertivas inferidas para

SEL 0362 - Inteligência Artificial 1

Regras e Encadeamentos

Marco H. TerraDepartamento de Eng. Elétrica - EESC - USP


Introdução● Este capítulo discute a utilização de regras IF-THEN para

resolução de problemas. Tais regras serão manipuladas com dois objetivos: (i) inferência de conclusões a partir de um conjunto de assertivas, (ii) validação de uma hipótese dada se ela atender as várias premissas que a fundamentam.

● Estas ideias fundamentam os sistemas especialistas.● Tópicos de discussão:

– Encadeamento: para frente e para trás.– Sistemas dedutivos e reativos baseados em regras.– Exemplos: Identificação de animais (sistemas de diagnóstico) e

sequência de embalagem de mercadorias (ações para configurar sistemas físicos).


Sistemas baseados em regras● Sistemas para resolução de problemas baseados em regras são constituídos

por regras definidas como abaixo: Rn If if1 if2 : ifp Then then1 then2 : thenq● Os padrões IF são chamados de antecedentes e os padrões THEN são

denominados consequentes


Definições importantes● Um fato expressa uma situação ou declaração que é verdadeira.● Uma assertiva é uma declaração que algo é um fato, logo ela

pode ser verdadeira ou falsa.● A memória de trabalho de um sistema destes consiste de uma

coleção de assertivas verdadeiras.● Um antecedente satisfeito é aquele em que um padrão IF se casa

com uma assertiva da memória de trabalho.● Uma regra engatilhada é aquela que todos seus padrões IF estão

satisfeitos.● Uma regra disparada é aquela que estabelece uma nova

assertiva ou executa uma ação.


Tipos de sistemas baseados em regras● Os sistemas baseados em regras possuem padrões IF da

mesma natureza contudo diferem entre si com respeito aos padrões THEN. Baseado nestas diferenças, tais sistemas são divididos em sistemas dedutivos e sistemas reativos.

● Sistema dedutivo é um sistema baseado em regras no qual os padrões THEN especificam novas assertivas a serem anexadas à memória de trabalho.

● Sistema reativo é um sistema baseado em regras no qual os padrões THEN especificam ações a serem tomadas pelo sistema.


Representações para sistemas baseados em regras● Uma memória de trabalho é uma representação na qual:

– Lexicalmente, existem símbolos e símbolos de padrões que são específicos da aplicação.

– Estruturalmente, assertivas são listas de símbolos e padrões são listas de símbolos ou símbolos de padrões, todos dependentes da aplicação.

– Semanticamente, as assertivas denotam fatos em um mundo escolhido.

– Procedimentalmente, possui rotinas para adicionar assertivas à memória de trabalho e rotinas para produzir uma lista de assertivas na memória de trabalho que se casam com assertivas de um padrão.


Representações para sistemas baseados em regras● Uma base de regras é uma representação na qual:

– Lexicalmente, existem símbolos e símbolos de padrões que são específicos da aplicação.

– Estruturalmente, padrões são listas de símbolos ou símbolos de padrões dependentes da aplicação e regras consistem de padrões IF ou THEN.

– Semanticamente, regras denotam restrições que serão checadas nos procedimentos.

– Procedimentalmente, possui rotinas que constroem regras dada um lista ordenada de padrões IF e THEN e rotinas para produzir uma lista de padrões IF or THEN em regras dadas.


Tipos de encadeamento● Encadeamento para frente: Um sistema baseado em

regras que executa encadeamento para frente utiliza assertivas dadas e assertivas inferidas para deduzir novas assertivas ou realizar uma ação. O processamento se dá partindo das assertivas para chegar a uma conclusão.

● Encadeamento para trás: Um sistema baseado em regras que executa encadeamento para trás transforma uma assertiva que se quer provar ou uma ação que se quer tomar em uma hipótese. A partir daí usa as regras retroativamente para analisar as assertivas que suportam a hipótese em questão.


Um sistema dedutivo que identifica animais● Este tópico descreve um sistema dedutivo para realizar

identificação: o ZOOKEEPER. Este sistema produz uma cadeia de conclusões que servem para identificar um animal examinado.

● Características do ZOOKEEPER:– Utiliza regras sem antecedentes longos.– Gera assertivas intermediárias como saídas das regras.– Combina estas assertivas e aquelas originais para produzir uma

conclusão.– Observa hábitos e características físicas para identificar os animais.– Neste exemplo, pode-se distinguir sete animais: leopardo, tigre, girafa,

zebra, avestruz, pinguim e albatroz.


Regras do ZOOKEEPER - Z1

Z1 If ?x tem pelos Then ?x é um mamífero

● Esta é uma regra que observa características físicas.● As regras contêm variáveis x inicialmente sem valores.● Elas vão assumir valores quando os antecedentes são

comparados às assertivas dadas. Quando as variáveis assumem valores diz-se que elas estão instanciadas.


Regras do ZOOKEEPER – Z2 a Z4

Z2 If ?x dá leite Then ?x é um mamífero

Z3 If ?x tem penas Then ?x é um pássaro

Z4 If ?x voa ?x põe ovos Then ?x é um pássaro● Regras determinam classe biológicas dos animais, onde Z2 e Z4 observam

hábitos e Z3 observa características físicas.● Z4 tem dois antecedentes para evitar conflito.


Regras do ZOOKEEPER – Z5 e Z6

Z5 If ?x é um mamífero ?x come carne Then ?x é um carnívoroZ6 If ?x é um mamífero ?x tem dentes pontudos ?x tem garras ?x tem olhos pontiagudos Then ?x é um carnívoro● Regras determinam se animal é carnívoro.● Z5 observa hábitos e Z6 observa características físicas.● Regras já utilizam assertivas geradas por regras anteriormente definidas.



Z7 If ?x é um mamífero ?x tem cascos Then ?x é um unguladoZ8 If ?x é um mamífero ?x rumina Then ?x é um ungulado● Regras determinam se animal é ungulado.● Z7 observa características físicas e Z8 observa hábitos.



Z9 If ?x é carnívoro ?x tem cor amarelo tostada ?x tem manchas escuras Then ?x é um leopardoZ10 If ?x é um carnívoro ?x tem cor amarelo tostada ?x tem listas pretas Then ?x é um tigre● Regras para identificar os animais carnívoros.



Z11 If ?x é um ungulado ?x tem pernas longas ?x tem pescoço comprido ?x tem cor amarelo tostada ?x tem manchas escuras Then ?x é uma girafaZ12 If ?x é um ungulado ?x tem cor branca ?x tem listas pretas Then ?x é um zebra● Regras para identificar os animais ungulados.



Z13 If ?x é um pássaro ?x não voa ?x tem pernas compridas ?x tem pescoço longo ?x é preto e branco Then ?x é uma avestruzZ14 If ?x é um pássaro ?x não voa ?x nada ?x é preto e branco Then ?x é um pinguim


Regras do ZOOKEEPER – Z15

Z15 If ?x é um pássaro ?x é bom voador Then ?x é um albatroz

● Regras para identificar os pássaros.


Encadeamento para frente no ZOOKEEPER● Para identificar um animal com

ZOOKEEPER:– Até as regras não produzirem novas assertivas

ou o animal ser identificado,● Para cada regra

– Tente fundamentar cada um dos antecedentes da regra comparando-os com os fatos.

– Se todos os antecedentes de regras estão fundamentados, declare o consequente a menos que este já exista.

– Repita para todas as alternativas que devem ser testadas.


Memória de trabalho para Stretch● Stretch tem cabelo;● Stretch rumina;● Stretch tem pernas longas;● Stretch tem cor amarela tostada;● Stretch tem pescoço comprido;● Stretch tem manchas negras.


Exemplo: encadeamento para frente● Verificar que tipo de animal é Stretch.● Solução:

– Stretch tem pelos, logo é um mamífero (dispara Z1);

– Stretch rumina e é um mamífero, logo é um ungulado (dispara Z8);

– Stretch é um ungulado, tem pernas longas, tem cor amarela tostada, tem pescoço comprido e tem manchas negras, logo é uma girafa (dispara Z11).


Exemplo: encadeamento para frente

● O fluxo de informação se dá através de uma série de regras antecedente-consequente, a partir das assertivas para as conclusões.


Encadeamento para trás no ZOOKEEPER● Até todas as hipótese terem sido testadas e

nenhuma ter sido totalmente fundamentada ou até o animal ter sido identificado,– Para cada hipótese

● Para cada regra na qual o consequente se casa com a hipótese do momento,

– Tente fundamentar cada um dos antecedentes de regra comparando-o com as assertivas na memória de trabalho ou encadeando para trás através de outra regra, criando assim uma nova hipótese.

– Se todos os antecedentes das regras estiverem fundamentados conclua que a hipótese é verdadeira.


Memória de trabalho para Swifty● Swifty tem cabelo;● Swifty tem olhos pontiagudos;● Swifty tem garras;● Swifty tem dentes pontudos;● Swifty tem cor amarelo tostada;● Swifty tem manchas negras.


Exemplo: encadeamento para trás● Verificar se Swifty é um leopardo.● Solução:

– Hipótese: Swifty é um leopardo logo considera Z9;– Hipótese: Swifty é carnívoro logo considera Z5 ou Z6;– Hipótese: Swifty é mamífero logo considera Z1 ou Z2;– Z1 confirmado mas não se sabe se Swifty come carne logo

desconsidera Z5;– Considera Z6 na qual suas quatro propriedades são confirmadas

por comparação com a memória de trabalho;– Considera Z9 com duas outras propriedades confirmadas por

comparação com a memória de trabalho logo Swifty é um leopardo.


Exemplo: encadeamento para frente

● O fluxo de informação se dá formando hipóteses e procurando através das regras antecedente-consequente se a hipótese é verdadeira.


Adequação do encadeamento ao problema● Considerando como as regras estão relacionadas

com os fatos:– Emprego de encadeamento para trás é recomendado

se os fatos dados e/ou fatos estabelecidos poderem resultar em um número alto de conclusões ou se existirem poucas condições para se chegar a uma conclusão.

– Emprego de encadeamento para frente é recomendado se existirem vários modos de se chegar às conclusões e se o número de conclusões for pequeno.


Um sistema reativo que ensaca mercadorias● Este tópico descreve um sistema reativo baseado em regras,

BAGGER, que produz uma sequência de ensacamento de mercadorias.

● Característicos de BAGGER:– Este programa é estruturado em quatro procedimentos distintos

como descritos a seguir.● Análise de compras: Procura mercadorias perdidas e sugere novas compras.● Ensaca-itens-grandes: Ensaca os maiores itens, colocando os vidros em

primeiro lugar.● Ensaca-itens-médios: Ensaca os itens médios, colocando congelados em

sacos para freezers.● Ensaca-itens-pequenos: Ensaca os menores itens.


Regras do Bagger – B1 e B2

● Regras para o passo de análise da compra.B1 If passo é análise-da-compra batatas fritas estão para ser ensacadas não existe pepsi para ser ensacada Then pergunte ao cliente se ele gostaria de levar uma garrafa de pepsiB2 If passo é análise-da-compra Then passo não é mais análise-da-compra passo é ensaca-itens-grandes


Regras do Bagger – B1 e B2

B2 If passo é análise-de-compra Delete passo é análise-de-compra Add passo é ensaca-itens-grandes● Regras para o passo de análise da compra. Elas sugerem

novos itens para a lista de compras e encerram o primeiro passo.

● B2 tem uma segunda sintaxe, nela utiliza-se operações de subtração e adição.


Regras do Bagger – B3 a B6

B3 If passo é ensaca-itens-grandes um item grande está para ser ensacado o item grande é uma garrafa o saco atual contém menos que 6 itens Delete um item grande está para ser ensacado Add o item grande está no saco atual

B4 If passo é ensaca-itens-grandes um item grande está para ser ensacado o saco atual contém menos que 6 itens Delete um item grande está para ser ensacado Add o item grande está no saco atual



B5 If passo é ensaca-itens-grandes um item grande está para ser ensacado um saco vazio está disponível Delete o saco atual é o saco atual Add o saco vazio é o saco atualB6 If passo é ensaca-itens-grandes Delete passo é ensaca-itens-grandes Add passo é ensaca-itens-médios● Regras para o passo ensaca-itens-grandes. Elas empacotam itens

grandes, iniciando pelas garrafas, em sacos com menos de 6 itens já acondicionados. As regras também encerram este passo.



B7 If passo é ensaca-itens-médios um item médio está congelado o item não está no saco para freezer Delete o item não está no saco para freezer Add o item médio está no saco para freezerB8 If passo é ensaca-itens-médios um item médio está para ser ensacado o saco atual contém nada ou só itens médios o saco atual não contém itens grandes o saco atual tem menos que 12 itens médios Delete um item médio está para ser ensacado Add o item médio está no saco atual



B9 If passo é ensaca-itens-médios um item médio está para ser ensacado um saco vazio está disponível Delete o saco atual é o saco atual Add o saco vazio é o saco atualB10 If passo é ensaca-itens-médios Delete passo é ensaca-itens-médios Add passo é ensaca-itens-pequenos

● Regras para o passo ensaca-itens-médios. Elas acondicionam itens congelados em sacos apropriados, ensacam itens médios, trocam saco cheio por outro vazio e mudam de passo.



B11 If passo é ensaca-itens-pequenos um item pequeno está para ser ensacado o saco atual não contém itens grandes o saco atual não contém itens médios o saco atual tem menos que 18 itens pequenos Delete um item pequeno está para ser ensacado Add o item pequeno está no saco atualB12 If passo é ensaca-itens-pequenos um item pequeno está para ser ensacado um saco vazio está disponível Delete o saco atual é o saco atual Add o saco vazio é o saco atual



B13 If passo é ensaca-itens-pequenos Delete passo é ensaca-itens-pequenos Add passo é final do processo● Regras para o passo ensaca-itens-pequenos.

Elas ensacam itens pequenos, trocam saco cheio por outro vazio e encerram processo.


● Esta é composta por assertivas que capturam informações sobre os itens que serão ensacados. Os itens estão listados como abaixo (esta será a entrada do sistema):


Item Embalagem Tamanho Congelado?

Pão Saco plástico Médio Não

Refresco Jarra Pequeno Não

Granola Caixa de papelão Grande Não

Sorvete Embalagem de papelão Médio Sim

Batata frita Saco plástico Médio Não

Pepsi Garrafa Grande Não


Memória de trabalho do sistema reativo● Formato da memória de trabalho no exemplo: passo é nome-do-passo nome-do-saco é um saco nome-da-mercadoria é para ser ensacada● Composição inicial da memória de trabalho no exemplo: passo é análise-de-compra saco1 é um saco pão é para ser ensacado refresco é para ser ensacado granola é para ser ensacado sorvete é para ser ensacado fritas é para ser ensacado


Memória de trabalho do sistema reativo● Composição após o passo análise-de-compra: passo é ensaca-itens-grandes saco1 é um saco pão é para ser ensacado refresco é para ser ensacado granola é para ser ensacado sorvete é para ser ensacado fritas é para ser ensacado● Segue-se o passo que deve ensacar os itens grandes.


Memória de trabalho do sistema reativo● Composição após o passo ensaca-itens-grandes: passo é ensaca-itens-médios saco1 contém pepsi saco1 contém granola pão é para ser ensacado refresco é para ser ensacado granola é para ser ensacado sorvete é para ser ensacado fritas é para ser ensacado● Segue-se o passo que deve ensacar os itens médios.


Memória de trabalho do sistema reativo● Composição após o passo ensaca-itens-médios: passo é ensaca-itens-médios saco1 contém pepsi saco1 contém granola saco2 contém pão saco2 contém sorvete saco2 contém fritas refresco é para ser ensacado● Segue-se o passo que deve ensacar os itens pequenos.


Memória de trabalho do sistema reativo● Composição após o passo ensaca-itens-médios: passo é ensaca-itens-médios saco1 contém pepsi saco1 contém granola saco2 contém pão saco2 contém sorvete saco2 contém fritas saco3 contém refresco● O processo está encerrado.

Documents

Regras e Encadeamentos - USP€¦ · Encadeamento para frente: Um sistema baseado em regras que executa encadeamento para frente utiliza assertivas dadas e assertivas inferidas para