I SBAI - UNESP - Rio Claro/SP - Brasil
Uma Arquitetura Adequada à Resolução de
Problemas de Configuração.
Alberto N. de Castro Jr.*
Crediné Silva de Menezes
Universidade Federal do Espírito Santo
Centro Tecnológico - Mestrado em Automação
Cx Postal 019011 - Vitória-ES - 29060-900.
Email:albertoj@brufes ou credine@brufes
Resumo
Propomos um ambiente para representar e processar conhecimento, adequado à
resolução dos problemas de configuração. A arquitetura proposta possui recursos como
múltiplas bases de conhecimento e dois níveis para a representação do conhecimento,
além de permitir ao usuário interagir com o sistema, modificando o processo de busca
de soluções.
"Fundação Universidade do Amazonas
- 86-
I SBAI- UNESP - Rio Claro/SP - Brasil
1
Introdução
Ao contrário do que ocorreu com os problemas de interpretação, para os quais existe um
grande número de ferramentas disponíveis principalmente nas tarefas de diagnóstico
e controle, para os problemas de construçã.o há ainda poucas ferramentas, e mesmo
assim, sempre restritas a certos domínios em particular.
Propomos aqui um ambiente destinado a representar e processar conhecimento que
seja adequado à resolução dos problemas d~ configuração. Trata-se de um 'shell' onde
o usuário descreve o domínio de um determinado problema, bem como as estratégias
e preferências utilizadas na sua resolução, atuando diretamente sobre o processo de
resolução.
Uma vez observadas as características dessa classe de problemas, foram definidos
os requisitos de tal ambiente e agregados recursos diferenciadores, tais como a representação do conhecimento em dois níveis (declarativo e procedimental) e a utilização
de múltiplas bases de conhecimento. É um sistema expansível, com o qual o usuário
pode interagir.
2
Trabalhos Correlatos
Para mostrarmos o contexto onde se insere esse trabalho, faremos um breve apanhado
dos trabalhos correlatos.
Como mencionado anteriormente, grande parte dos sistemas que utilizam recursos
oriundos da Inteligência Artificial e são aplicados na prática, destinam-se à lidar com
problemas de interpretação. Para a outra categoria de problemas (os de construção),
somente poucas ferramentas foram criadas, sempre abrangendo um domínio específico,
como é o caso dos sistemas RljXCON, MOLGEN e VT [3], dentre outros.
Combinando técnicas da resolução de problemas de satisfação de restrições com recursos como o backtracking, Lauriere [4] propôs o sistema ALICE, que procura atender
a um largo espectro de problemas. ALICE tem um conjunto de primitivas na qual o
usuário deve expressar o problema, e um conjunto de heurísticas gerais que podem ser
utilizadas na sua resolução. Contudo, ALICE é uma caixa-preta que não possibilita ao
usuário interagir com e modificar o processo dedutivo.
Hentenryck[13] apresentou uma linguagem de programação lógica destinada a manusear restrições, CIJIP. O aspecto principal dessa proposta é a redefinição da lógica
de primeira ordem, procurando incorporar técnicas de consistência.
A partir de CHIP, outra linguagem para tratar com restrições foi desenvolvida:
Charme. Procurando inserir conceitos de objetos à linguagens desse tipo, surgiram
linguagen s como ConstraintLisp e Pecos[5,6].
A arquitetura aqui proposta se situa entre a faixa ocupada pelas linguagens genéricas
(como ALICE ou CHIP) e as aplicações restritas a um domínio específico. Ao mesmo
tempo que o usuário não precisa elaborar um novo programa a cada aplicação, ele pode
utilizar esse shell num conjunto relativamente amplo de aplicações.
3
Classificação dos Problemas
Clancey[2] propôs uma análise em termos das operações genéricas sobre um sistema,
distinguindo entre operações sintéticas que constroem um sistema e operações analíticas
que interpretam um sistema. Esses conceitos bem genéricos foram especializados, resultando em uma análise hierárquica dos tipos de operação que um programa pode
- 87-
I SBAI - UNESP - Rio Claro/SP - Brasil
fazer. Jackson[3] apresenta a seguinte representação dessas hierarquias:
INTERPRETAÇÃO
CONSTRUÇÃO
~
~
Especificar. Projetar
Identificar_ PredizerControlar
Montar
AI
A
Configurar
Monitorar Diagnosticar
Planejar Modificar
Figura 3.1: Classificação dos Problemas
3.1
Classificação x Construção
o aspecto principal para distinguir entre problemas de classificação (ou interpretação)
e de construção, é que no primeiro o conjunto-solução pode ser previamente enumerado.
No segundo caso, pode-se dizer que as soluções são construídas ao invés de selecionadas.
Teoricamente, também para o segundo caso se poderia enumerar o conjunto-solução,
contudo, para a maioria dos problemas desse grupo, o tamanho desse conjunto seria
de tal ordem que tornaria a tarefa impossível.
Construir uma solução para um problema, normalmente envolve ter algum modelo
da estrutura e do comportamento de um objeto complexo que se está tentando construir. Este modelo deve conter conhecimento concernente às restrições que o 'produto
final' deve satisfazer.
Por exemplo, na geração de um plano para um robô atingir certo objetivo, existirão
restrições físicas e temporais que ordenarão certas ações ou sequência de ações. Nesse
problema co,mo na maioria das tarefas de planejamento, o espaço de sequências possíveis
de ações é essencialmente infinito; então não existe meio para que todas as sequências
possam ser previamente armazenadas para posterior seleção. A ordem na qual as
coisas são feitas é também muito importante em tarefas de montagem e configuração.
Na configuração, os elementos da solução são componentes, e soluções são combinação
de componentes que formam um objeto complexo que satisfaça certas restrições.
3.2
Problemas de Configuração
Os problemas de configuração tem como componentes principais:
• Um conjunto de objetos quaisquer (recursos) que devem ser alocados segundo as
restrições.
• Um conjunto de restrições que determinam como os recursos devem ser arruma·
dos.
• O quadro, que é o 'invólucro' de uma solução, é onde os recursos serão arrumados.
Uma característica importante em problemas desse tipo é que teoricamente não há
uma solução melhor que outra. Para ser uma solução, qualquer configuração obtida
deve apenas atender às restrições especificadas, não há um custo ou função equivalente
que caracterize um ótimo. 1 Em vista disso, muitas vezes necessita-se 'navegar' por
um conjunto de soluções. Alguns exemplos de problemas desse tipo são:
1É
claro que há estratégias visando conseguir eficiência na busca de uma solução.
- 88-
I SBAl - UNESP - Rio Claro/SP - Brasll
1. Preenchimento de tabelas ou quadros, tais como:
• 'chaves' de campeonatos;
• ocupação das salas de um prédio, como salas de uma escola;
• horário escolar.
2. Mapa de atividade (ou de folga) de pessoal (trabalho em turnos).
3. Disposição dos objetos em um local (lay-out).
4. Carteira de Investimentos (distribuição de capital).
5. Distribuição das frentes de serviço.
4
Modelagem do Conhecimento
Necessitamos proceder o entendimento da atividade em questão para a consequente
modelagem do conhecimento nela envolvido[lO,11,3]. A adequada representação desse
conhecimento é um requisito de qualquer Sistema Baseado em Conhecimento (SBC).
Um SBC pode ser definido como qualquer sistema que realiza uma tarefa pela manipulação de uma representação simbólica de conhecimento.
Tal modelagem e representação do conhecimento tem que considerar a finalidade
para a qual ele será utilizado. Esse é um ponto que diferencia uma coleção qualquer
de fatos, de um corpo do conhecimento.
Deve-se considerar alguns critérios para se determinar corno o conhecimento envolvido na classe de problemas em questão deve ser agrupado, tais como:
• Segundo sua natureza - ou seja, a que 'parte' do problema o conhecimento se
refere, à definição ou à resolução.
• Segundo a abrangência - determinando a que nível de generalidade tal conhecimento pode ser considerado: em qualquer problema de uma classe, naqueles que
apresentarem certas características ou só em algumas exceções.
• Segundo a utilidade no processo de resolução - determinando qual parte do conhecimento envolvido será utilizado para orientar a busca de soluções, bem como
quando e onde esse conhecimento será utilizado.
• Segundo a utilidade nos processos complementares - visando utilização do conhecimento em processos como aquisição de conhecimento ou explicação do processo
de resolução.
Como resultado da análise dos critérios acima, foram identificados 5 grupos básicos
de conhecimento, cujas características básicas são:
• Dados (componentes)
Nesse grupo estão as informações básicas sobre urna determinada ocorrência do
problema no mundo real ou seja, de urna 'instância' do problema. Estão nesse
grupo os componentes básicos, que durante o processo de busca de soluções, devem ser alocados ou dispostos segundo os critérios descritos nos outros grupos.
Também deve estar aqui a forma ou 'molde' onde os componentes serão dispostos.
• Restrições
Esse grupo de conhecimento é extremamente importante pois é ele quem deter-
mina a redução no tamanho do conjunto de soluções de determinado problema.
Uma restrição é um tipo de conhecimento que determina basicamente urna condição
de validade em qualquer dos casos abaixo:
- 89-
I SBAI - UNESP - Rio Claro/SP - Brasil
1. Sobre componentes.
Determinando se um componente proposto possui as características necessárias para ser candidato aos demais processos. Exemplo de restrições desse
tipo:
- Os componentes devem ser de uma mesma categoria.
- Cada componente deve ter associado a ele um conjunto de características.
2. Sobre arranjos.
Determinando se um número determinado. de componentes podem ser associados de modo a formar um grupo que chamamos de arranjo, que por sua
vez serão os componentes de uma solução. Exemplo de restrições desse tipo:
Os componentes devem ser diferentes entre sí.
Não se pode utilizar mais de um componente com uma característica C1
associada.
Deve haver uma quantidade mínima m de componentes com certa característica C2 associada.
3. Sobre soluções.
Análogo ao anterior, determina se um conjunto de arranjos podem ser associados de modo a formar uma solução. Exemplos de restrições desse tipo
são:
Os arranjos devem ser diferentes entre sí.
Uma operação sobre certa característica associada C3 dos componentes
de um arranjo deve ser diferente da mesma operação noutro arranjo.
• Preferências
Uma preferência é uma condição que como na restrição comum, estabelece a
validade de uma configuração. Contudo, essa condição é considerada enquanto
houver solução que a atenda. Caso não existam soluções sob tal condição, a
condição é 'relaxada'.
• Estratégias
Uma parte importante do conhecimento referente a determinada classe de problemas diz respei to à sua resol ução, descrevendo si tuações favoráveis, funções
avaliadoras (heurísticas) e demais informações e/ou processos que quando utilizados, orientam a busca de uma solução. Tal conhecimento é conhecido como
estratégico.
As estratégias podem ser hierarquizadas segundo sua adequação ao conjunto de
problemas, podendo ser de uso particular ou geral.
A adequada modelagem do conhecimento, observando a função desse conhecimento no processo de resolução é um exemplo de estratégia. Outra estratégia
que pode ser utilizada, refere-se à formação de determinada configuração (seja
um arranjo ou solução). A princípio, todas as restrições devem ser satisfeitas.
Essa estratégia consiste em associarmos a cada restrição uma prioridade, segundo
a qual as restrições 'mais fortes' seriam checadas primeiro, permitindo que uma
configuração inadequada seja logo descartada. De modo análogo, se poderia priorizar as preferências, de modo que na hora dessas preferências serem relaxadas,
isso seguisse uma sequência determinada pelo usuário.
• Esqueletos
Um esqueleto é um esquema básico, uma configuração parcial, parte de um arranjo
ou de uma solução que o usuário pode informar ao sistema, definindo como deseja
tal configuração.
-90-
I SBAl - UNESP - Rio Claro/SP - Brasil
Com isso, o usuaflO pode informar que deseja que certos componentes sejam
dispostos juntos num mesmo arranjo, ou exatamente o contrário: que certos
componentes não devem participar de um mesmo arranjo. Do mesmo modo
quanto aos arranjos numa solução.
Certamente esses esqueletos devem também atender às restrições descritas, a
menos que se deseje um tratamento de exceção.
Nesse grupo ainda, inserimos um outro tipo de conhecimento, imprescindível a
todo o processo: A definição de um estado-solução. Ou seja, é onde se estabelecem
os critérios segundo os quais um conjunto de arranjos forma uma solução.
Uma ferramenta construída com essas características de sintonia funciona como um
laboratório para quem deseja resolver diversos problemas do tipo em questão.
5
Processamento
Nosso processo de resolução consiste numa procura no espaço de estados. Assim,
resolver um problema consiste em 'navegar' no espaço de estados desse problema:
Partimos de um estado inicial, passamos por estados intermediários até atingir um
estado solução.
O processo termina segundo a interferência do usuário, que pode solicitar ou não
que outra solução seja encontrada.
Um estado é composto dos seguintes elementos:
• arranjos já concluidos.
• componentes que ainda não foram utilizados na formação de arranjos.
• ponto de retorno (backtracking).
• informações adicionais ao processo.
O estado · inicial possui apenas componentes (podendo associar os esqueletos informados pelo usuário). Um estado final (solução) é aquele onde todos os componentes
foram arranjados adequa.damente, segundo os critérios definidos pelo usuário.
Cada estado possu i um número maior de arranjos que aquele imediatamente anterior, bem como um número menor de componentes restantes. Assim, cada novo estado
está pelo menos em termos quantitativos (tamanho do conjunto-solução), mais próximo
de uma solução que o anterior.
5.1
Mudança de estados
A geração de um novo estado a partir do atual, define um passo do processo, e pode
ser dividido em duas etapas:
5.1.1
Formação do arranjo
Quando um arranjo é proposto e aprovado, dá origem ao novo estado.
Inicialmente, uma composição de componentes candidatos a um arranjo é proposta.
Nessa hora, são utilizadas estratégias definidas pelo usuário para selecionar quais componentes tem a princípio, maior chance de ao formar um arranjo, constituir um caminho promissor. Dentre essas estratégias, podemos citar a do menor comprometimento,
que sugere que devem ser utilizados inicialmente aqueles componentes que deixam um
maior leque de opções ou caminhos a seguir. É também nesse ponto onde considera-se
os esqueletos (de arranjos) fornecidos pelo usuário.
- 91 -
I SBAI - UNESP - Rio Claro/SP - Brasil
A combinação proposta (arranjo) deve ficar registrada, para no caso de um retorno,
não gerar combinações repetidas.
Mas se não se consegue gerar nova arranjo, é hora de fazermos um retorno a algum
estado anterior do processo (operação de backlracking). O estado considerado deve
permitir a continuidade do processo, formando um arranjo diferente do anteriormente
gerado. 2
Quando nenhum caminho puder ser tomado (ou retomado), deve-se procurar por
uma preferência que possa ser relaxada, e. um novo caminho (com menos restrições)
será iniciado. Caso contrário o usuário é informado que não há mais soluções possfveis
e o processo termina.
5.1.2
Aprovação do arranjO
Nesse ponto devem ser verificadas o grupo de restrições e preferências que digam respeito à combinação de arranjos. Caso o arranjo não seja aprovado, voltamos à etapa
anterior.
Também aqui devem ser considerados os esqueletos de soluções fornecidos pelo
usuário.
U ma vez aprovado um arranjo, a geração do novo estado consiste simplesmente
de copiar do estado atual os arranjos existentes (inclusive o recém-criado) e registrar
os componentes restantes, o ponto de ponto de backtracking (normalmente o estado
anterior) e as informações adicionais.
5.2
Verificar se estado é solução
Caso o estado que foi gerado não atenda àquilo que o usuário definiu como solução, o
processo retoma à etapa de formação de novo arranjo.
Quando o estado atual é de fato solução, é feita uma consulta ao usuário sobre a
adequabilidade dessa solução às suas necessidades. Se a solução é de fato suficiente, o
processo termina.
Mas quando o usuá.rio solicita que uma nova solução seja encontrada, duas alternativas se apresentam:
1. Simplesmente retornar ao último ponto de backtracking (ou àquele indicado por
uma estratégia), retomando o processo e buscando uma nova solução. Como
os estados gerados são sempre diferentes que os anteriores, uma nova solução é
também sempre diferente das anteriores.
2. A soluçã.o encontrada é armazenada. O usuário é solicitado a informar novos
esqueletos ou mesmo restrições e preferências que por ventura tenham sido reconhecidas naquele momento.
De acordo com a influência desses novos critérios no processo de solução em
andamento, pode-se apenas dar continuidade ao processo de modo semelhante
ao tratado no ítem anterior, passando a considerar um conjunto adicional de
critérios ou, no caso dos critérios incluídos virem a alterar ou mesmo anular o
processo em andamento, um novo processo será iniciado. Caso se deseje que as
soluções obtidas até aquele momento não sejam novamente apresentadas, estas
devem ser armazenadas e na definição de um estado-solução deve ser explicitado
que qualquer solução deve ser diferente daquelas anteriormente armazenadas.
2Uma estratégia que se poderia utilizar aqui é o retorno ao n-ésimo estado anterior quando não se
conseguir gerar um novo estado devido ao número reduzido de componentes. O usuário poderia informar
qual o número mínimo de componentes a considerar.
- 92-
I SBAI - UNESP - Rio Claro/SP - Brasil
Requisitos
6
Seria adequado a um snc destinado à resolução dos problemas de configuração, possuir
alguns recursos como os relacionados a seguir [3,12,1,7,14,8].
6.1
Regime de Controle
o regime
de controle básico utilizado é o backtracking. Buscando melhorar o desempenho desse tipo de recurso, atuam as estratégias. Essas estratégias vão desde a
modelagem adequada do conhecimento, passam por sugestões mais inteligentes para
candidatos a arranjos, e até orientam a busca dos pontos de backtracking.
6.2
Multiplas Bases de Conhecimento
N a base de conhecimento de um SBC estão armazenados o conhecimento factual e o
conhecimento semãntico de um domínio, conhecimento extra-domínio e composições
das várias modalidades de conhecimento.
Além de cumprir a função de 'depósito' de conhecimento, a utilização de múltiplas
bases de conhecimento permite externalizar uma modelagem do conhecimento segundo
necessitamos, explicitando o agrupamento dos diversos tipos ou grupos de conhecimento.
Além de armazenar o conhecimento segundo os grupos definidos, a existência de
múltiplas bases facilita a implementação de estratégias, como a que diz respeito à
separação ou hierarquização de restrições e estratégias segundo sua aplicabilidade a
todos os problemas de uma classe (gerais) ou a determinadas situações (particulares).
Um recurso necessário é que tais bases possam ser utilizadas ora isoladamente, ora
em conjunto, segundo definido pelo usuário ou requisitado pelo processo de resolução.
6.3
Multiplos Níveis
A possibilidade de permitir que o usuário descreva o domínio de um problema não só
por meio do conhecimento primitivo e derivado, mas por processos (procedimentos)
complexos, é um recurso importante ainda pouco utilizado em SBC's, particularmente
como sugerido aqui [9].
Basicamente, propomos a utilização de dois níveis para representar e manusear o
conhecimento:
• Nível declarativo.
Destinado aos fragmentos de conhecimento passíveis de descrição formal, em particular fatos e associação causal entre fatos .
• Nível procedimental.
Destinado a descrever ações a serem executadas condicionalmente ou não, segundo ordem determinada pelo programador.
No nível declarativo são efetuadas deduções capazes de extrair conhecimentos ou
conclusões não mencionados explicitamente, baseados em consultas feitas pelo usuário.
O processo pelo qual essas conclusões são obtidas não sofrem interferência do usuário,
embora seja desejável a capacidade de dar explicações aceitáveis sobre como uma conclusão foi obtida.
Já na parte do conhecimento agrupado no nível procedimental, envolvendo o controle do processo de resolução de um problema específico ou de uma classe de problemas, deve haver uma linguagem própria que permita a composição de procedimentos
- 93 -
I SBAI - UNESP - Rio Claro/SP - Brasil
visando a execução de ações. Esse elenco de procedimentos se somarão a um núcleo
pré-programado compondo o 'programa' utilizado na resolução do problema.
Urna semãntica precisa, deve estabelecer a necessária integmção entre entre os dois
níveis, de modo que no nível procedimental possa ser requerida uma dedução sobre o
conhecimento representado no nível declarativo.
No nível procedimental poderão ser ativadas não só as composições de procedimentos lá armazenadas, mas também outros procedimentos externos ao ambiente, permitindo ligação com o 'mundo exterior'.
6.4
Diagrama da Arquitetura
A figura 6.2 apresenta os elementos principais do ambiente, dispondo-os segundo o
nível que atuam.
Usuário
Conhecimentof----~
procedural
Controle
do
processo
f-----..IProcedimentos
externos
tNível
rocedural
~ Nível declarativo
ntermediários
Conhecimento Declarativo
.-----~---,
Máquina
de
Inferência
Figura 6.2: Esquema da Arquitetura
o controle do processo é o 'centro' do ambiente, e corno o nome informa, gerencia
a comunicação com o usuário, solicita a atuação da máquina de inferência, dirige o
processo de busca, gera os estados, utiliza o conhecimento armazenado sob forma de
procedimentos e ativa processos externos, complementares ao ambiente.
A máquina de inferência que atua no nível declarativo, serve para provar propriedades acerca do conhecimento declarativo e dos estados. Sua atuação é sempre gerenciada
pelo controle do processo.
Durante o procedimento de propor-e-testar, é a máquina de inferência é quem
cumpre a etapa de teste, ou checagem, conferindo estados e restrições, preferências,
etc.
- 94-
I SBAI - UNESP - Rio Claro/SP - Brasil
Certamente o conhecimento representado no esquema está distribuido por diferentes
bases, cuja organização pode variar conforme implementação.
7
Considerações Finais
Foi apresentada a arquitetura de um sheU destinado à resolução de problemas de configuração, baseando-se nas características próprias a esse tipo de problema.
Atualmente está sendo efetivada a implementação dessa arquitetura, que deverá
utilizar os recursos de um ambiente para processamento de conhecimento existente,
baseado em lógica de primeira ordem. Simultaneamente, estão sendo registradas situações do 'mundo real' que ilustrem a utilização do sistema em diferentes domínios.
Referências
[1] Chandrasekaran, B.; Design Problem Solving: A Task Analysis; AI Magazine,
Winter 1990, p.59- 7l.
[2] Clancey, W.J.; Heuristic Classification; Artificial Intelligence, 27,1985, p.289-350.
[3] J ackson, Peter; Introduction to Exper't Systems; Addison- Wesley, 1990.
[4] Lauriere, J .L.; Problem Solving and Artificial Intelligence; Prentice RaU, 1990.
[5] Liu, B.; A Comparison of Charme, Pecos and ConstraintLisp; Technical Report,
Information Technology Institute, 1991.
[6] Liu, B. e Ku, Y-W.j ConstraintLisp: An 0.0. Constraint Programming Language;
ACM SIGPLAN, 11, Nov 92, p.17-26.
[7] Mackworth, A.K.; Constmint Satisfaction; Encyclopedia of AI, 1986.
[8] Menezes, Credinéj Ambientes Para Processamento de Conhecimento; PUCjRJDI, 'Tese de Doutorado, 1989.
[9] Menezes, Crediné e Carvalho, R.L.; Processamento de Conhecimento em Ambientes Multinivelados; Relatório de Pesquisa, LNCC, 1990.
[10] Polya, George; A Arte de Resolver Problemas; Ed. Interciência, 1981.
[11] Simon, H.A.; Science of the Artificialj The MIT press, 1969.
[12] Steels, L.; Components of Expertisej AI Magazine, Summer 1990, p.28-49.
[13] Van Hentenryck, P.; Constraint Satisfaction in Logic Programmingj The MIT
Press, 1989.
[14] Vieira, Newton; Máquinas de Inferência para Processamento de Conhecimento;
PUCjRJ-DI, Tese de Doutorado, 1987.
- 95-