Skip to content

Examples

Abaixo são apresentados alguns exemplos de problemas que podem ser resolvidos com esta biblioteca.

Aspirador de Pó

O método main da classe VacuumWorldGeneric.py deve receber um arquivo texto que descreve a situação do ambiente e as posições do robô como parâmetros. Por exemplo, para o seguinte ambiente:

O seguinte arquivo de configuração será entregue: 

0;1;1;1
0;0;0;0
1;1;1;1

onde 0 significa limpo e 1 sujo.

E o seguinte comando deve ser executado:

python VacuumWorldGeneric.py configuracao.txt 0 0

As ações que o robô (agente) sabe executar são:

  • esq: ir para a esquerda;
  • dir: ir para a direita;
  • baixo: ir para baixo;
  • cima: ir para cima;
  • limpar: limpar o quarto onde está.

Ao executar o comando acima, o programa deverá gerar uma sequência de ações que fará com que o robô saia do estado inicial e chegue em um estado final válido. Um estado final válido é um estado onde todos os quartos (quadrados) estão limpos.

Uma sequência de ações válidas para resolver o estado acima é: 

dir; limpar; dir; limpar; dir; baixo; baixo; limpar; esq; limpar; esq; limpar; esq; limpar

Um outro exemplo

Considere um novo exemplo:

Para este exemplo o arquivo de configuração precisa ter este conteúdo:

0;1;1;1
0;0;1;1
1;1;1;1

E a chamada para o programa: 

python VacuumWorldGeneric.py configuracao.txt 2 3

O programa que está implementado em VacuumWorldGeneric.py não se preocupa com a validação dos dados de entrada. Assume-se que os dados de entrada estão corretos, por exemplo, a posição do robô é uma posição válida.

A única tarefa que o programa deve fazer é se existir solução então retornar uma sequência de ações ótima para o problema. Se não existir solução então informar que não existe solução.

Banda U2

A banda U2 tem um concerto que começa daqui a 17 minutos e todos precisam cruzar uma ponte par chegar lá. Todos os 4 participantes estão do mesmo lado da ponte. É noite. Só há uma lanterna. A ponte suporta, no máximo, duas pessoas. Qualquer pessoa que passe, uma ou duas, deve passar com a lanterna na mão. A lanterna deve ser levada de um lado para outro e não ser jogada. Cada membro da banda tem um tempo diferente para passar de um lado para o outro. O par deve andar no tempo do menos veloz: Bono: 1 minuto para passar; Edge: 2 minutos para passar; Adam: 5 minutos para passar; e Larry: 10 minutos para passar.

O problema consiste em ter os quatro elementos da banda do outro lado da ponte no menor tempo possível.

O arquivo U2.py implementa uma solução possível para este problema.

8 Puzzle

O arquivo Puzzle8.py implementa um solucionador para o jogo Puzzle8:

Grafo

For large or computationally expensive problems you can use ParallelSearch to distribute the workload across all CPU cores of the machine. The wrapper accepts any existing search algorithm as its first argument.

The example below solves the 8-Puzzle in parallel using A*:

from aigyminsper.search.search_algorithms import ParallelSearch, AEstrela
from Puzzle8 import Puzzle8  # or any other State subclass

if __name__ == '__main__':
    initial = Puzzle8('', [7, 2, 4, 5, 0, 6, 8, 3, 1])
    solver = ParallelSearch(AEstrela)
    result = solver.search(initial, pruning='general')
    if result is not None:
        print(result.show_path())
        print('Total cost:', result.g)
    else:
        print('No solution found')

You can also wrap simpler algorithms — for instance, BuscaLargura for problems that do not have a heuristic function defined:

from aigyminsper.search.search_algorithms import ParallelSearch, BuscaLargura

solver = ParallelSearch(BuscaLargura, n_processes=8)
result = solver.search(initial_state, pruning='general')

Note: ParallelSearch is a best-effort parallel race. Cost-optimal algorithms (BuscaCustoUniforme, AEstrela) are not guaranteed to return the globally optimal path when used inside ParallelSearch because each worker only explores its own sub-tree.