Problema de Satisfação de Restrições ou CSP (Constraint Satisfaction Problem)

 

Neste tópico retorno à Inteligência Artificial para falar do Problema de Satisfação de Restrições, problemas de IA e algoritmos para resolver essa classe de problemas. Ao final colocarei as referências utilizadas para a definição do algoritmo.

Vou abordar esse assunto em três postagens distintas.

Nessa primeira postagem vou tratar da parte teórica, onde explicarei o Problema de Satisfação de Restrições, aplicação e algoritmo.

Na segunda postagem, não falarei sobre CSP, mas sim sobre o NetLogo, um software para simulação mono ou multi agente, com um exemplo didático e um breve tutorial em português sobre como utilizar o NetLogo.

E na terceira postagem retorno ao CSP para implementar o algoritmo dessa postagem no NetLogo, com o objetivo de resolver computacionalmente o “Problema das 4 Rainhas”.

Eugene C. Freuder escreveu que a programação de restrições representa a abordagem mais próxima para se atingir o Santo Graal da programação, baseia-se na ideia de que o usuário declara o problema e o computador resolve.

Com essa afirmação eu diria que muitos programadores perderam seus empregos, mas a coisa não é por aí. Para que o problema seja resolvido por CSP, temos que formalizá-lo. Ou seja definir as variáveis do nosso problema e as restrições para essa variável, então o algoritmo poderia resolve-lo.

E a tarefa de formalizar o problema não é nada trivial.

Resolução de Problemas com Domínios Finitos:

O problema que demonstrarei na terceira postagem da série sobre CSP, 4-Queen ou sua variante n-Queen, trata de quatro rainhas colocadas em um tabuleiro de xadrez de 4x4 casas, e consiste em posicionar as quatro rainhas de modo que elas não se ataquem.

A variante N-Queen funciona da mesma forma, no entanto, temos um número n de rainhas num tabuleiro de xadrez de n x n casas.

Queens10_bbc

Ilustração do Problema de 10-Rainhas

Fonte: http://rosettacode.org/wiki/N-queens_problem

Problemas de empacotamento são outro tipo de problemas que podem ser resolvidos utilizando CSP de domínio finito, neste caso, temos uma série de objetos para serem postos em uma área limitada de forma que esses objetos não se sobreponham, de modo que respeitem restrições de posicionamento e não violem determinado valor de capacidade. Uma apliação prática desse tipo de problema poderiam ser inserção de cargas em veícuos de transporte, inserção de componentes eletrônicos em placas de circuito impresso, armazenamento de produtos. Há um problema clássico que trata de empacotamento de retângulos em uma área, de forma que todos se encaixem.

empacotamento de blocos

Empacotamento de Blocos

Fonte: TAVARES, 2000.

Problemas de escalonamento são oriundos do surgimento de tarefas dependentes que compartilham recursos ou tem recursos escassos. Por exemplo elaboração de horários em salas de aulas, hospitais, etc., sequenciamento de tarefas em um projeto, agendamento, entre outros.

Problemas de Layout, destaco o Facility Layout Problem (em português ficaria Problema de Disposição de Instalações) que é um problema de otimização combinatória que consiste no posicionamento de instalações de um sistema de manufatura de modo a otimizar a produção, obedecendo as restrições que podem envolver o fluxo dos processos e outros fatores da manufatura.

Quebra – Cabeças de Lógica podem ser resolvidos por CSP também, entre eles temos SUDOKU, o próprio n-Queen poderia ser considerado um quebra – cabeça, outro bem interessante é o Zebra Puzzle.

Formalmente um CSP é definido por variáveis (x1, x2, x3, …) que possuem um domínio (D1, D2, D3, … Dm) e um conjunto de restrições para os seus valores. O objetivo é encontrar o valor de cada variável de modo que todas as restrições sejam satisfeitas. Aqui menciono variáveis com um domíinio finito, mas o CSP pode tratar problemas com domínio infinito ou desconhecido.

De acordo com o domínio o problema pode ser tratável ou intratável.

Uma outra classe de CSP é a DCSP, Distributed Constraint Satisfaction Problem, ou Problema de Satisfação de Restrições Distribuídos. Nesse caso, as variáveis do problema são distribuídas entre vários agentes, que se comunicam entre si.

Formalizando Problemas:

Aqui vou tratar de um problema simples que é 4-Queen, temos quatro rainhas em um tabuleiro de xadrez de 4x4, e queremos posicioná-las sem que uma ataque a outra.

Para formalizar esse problema como CSP, temos que responder três perguntas:

  1. Quais são as variáveis do problema?
  2. Qual é o domínio de cada variável?
  3. E quais são as restrições?

Num jogo de Xadrez a rainha é a única peça que pode se mover em todas as direções, quantas casas quiser.

mov.dama

Fonte: http://xadrezdaescolacaiosergio.blogspot.com.br/p/movimentos-e-capituras-das-pecas.html

Para o problema das 4 Rainhas, vamos ter 4 Rainhas (logicamente) e um tabuleiro de 4 x 4.

estado_inicial_4_q

Fonte: não lembro.

Então, para facilitar a modelagem do problema, consideramos que as rainhas só podem se mover na sua linha, indo para esquerda ou para direita, de modo a verificar se irão atacar umas às outras.

Nossas variáveis são as 4 Rainhas, no caso, as linhas onde elas estão.

Quanto ao domínio das variáveis, temos um tabuleiro 4 x 4, e se elas podem se mover apenas para esquerda ou para direita, nosso domínio se resume as quatro posições de cada linha [1, 2, 3, 4].

As restrições são que uma rainha não pode atacar a outra, sendo assim, uma rainha não pode estar na mesma coluna ou na mesma diagonal que outra rainha.

Variáveis: Q1, Q2, Q3, Q4

Domínio: dom(Q1) = [1, 2, 3, 4], dom(Q2) = [1, 2, 3, 4], dom(Q3) = [1, 2, 3, 4] e dom(Q4) = [1, 2, 3, 4]

Restrições:

constraint_graph

Grafo de Restrições do Problema 4-Queen

Fonte: http://www.cs.toronto.edu/~hojjat/384w09/Lectures/Lecture-04-Backtracking-Search.pdf

Ainda pode-se definir da seguinte maneira:

constraint

A primeira restrição (C1) aplicada de uma Rainha para as outras indica que a posição delas devem ser diferentes, no caso não podem estar na mesma coluna.

A segunda restrição (C2) refere-se a diagonal.

Na aplicação confirmaremos se essas restrições são suficientes e se estão corretas para esse problema.

Algoritmo de Busca com Retrocesso:

Esse algoritmo realiza uma busca em profundidade, fazendo atribuições uma variável de cada vez, fazendo um retrocesso quando as restrições não são satisfeitas.

backtracking

Algoritmo Backtracking – Pesquisa com Retrocesso

Fonte: Adaptado de RUSSEL, NORVIG.

Neste algoritmo a função PESQUISA-COM-RETROCESSO retorna a função RETROCESSO-RECURSIVO, que recebe dois parâmetros, um vetor com as variáveis e seus valores atribuídos, inicialmente um vetor vazio, e um CSP, podendo retornar um sucesso ou falha.

Para o caso de DCSP (problema de satisfaão de restrições distribuído) há o algoritmo Asynchronous Backtracking [YOKOO, 1992], o qual não entrarei em detalhes nesta postagem, abaixo está a referência do artigo.

Para terminar a postagem, temos então o problema formalizado e o algoritmo para solucioná-lo, em breve vamos visualizar o resultado na prática.

Referências:

BAZZAN, A. L. C. Notas de Aula da Disciplina Advanced Artificial Intelligence. 2012

YOKOO. et al. Distributed Constraint Satisfaction for Formalizing Distributed Problem Solving. 1992. 12th IEEE International Conference on Distributed Computing Systems.

RUSSEL Stuart. NORVIG, Peter. Inteligência Artificial. 2ª Edição. Editora Campus.

TAVARES, J.A.R. Geração de Configurações de Sistemas Industriais com o Recurso à Tecnologia das Restrições e Computação Evolucionária. Dezembro de 2000. Disponível em: [http://www.dei.isep.ipp.pt/~jtavares/PhD_Tese/Resumo_PhD.htm]

Comentários

  1. Boa noite!
    Poderia mostrar um exemplo de representação de um estado para um problema de satisfação de restrições?

    ResponderExcluir
  2. Boa noite.
    Um CSP é definido por uma tupla , certo?
    Onde X é o conjunto de variáveis, D, o conjunto de domínios das variáveis, e R um conjunto de restrições unárias entre as variáveis e seus valores ou binárias entre duas variáveis relacionadas.
    cada variávei x possui um dominio D_x com os valores que podem ser atribuídos a essa variável.

    Um estado em CSP é a atribuição de uma ou várias variáveis no problema, por exemplo, vamos retomar o problema das 4-Rainhas, onde cada rainha tem um domínio com os valores {1,2,3,4} representando as colunas que ela pode estar, e se considerarmos que as rainhas obrigatoriamente estão no tabuleiro, então, não há variável com valor nulo.
    Um estado possível pode ser Q1=1, Q2=1, Q3=1, Q4=1, que é o início do problema.
    No entanto não é um estado objetivo, pois as restrições não estão satisfeitas.
    Q1=1, Q2=2, Q3=1, Q4=1 é outro estado, e por aí vai.

    ResponderExcluir
  3. faltou a informação: definido por uma tupla [X,D,R]

    ResponderExcluir

Postar um comentário

Postagens mais visitadas