Simple AI

This packages is based and inspired in aima-python: https://code.google.com/p/aima-python/

We implement all the searches in aima-python plus (LISTAR). Besides, we make some improvements in terms of efficiency and error handling.

Installation

Just get it:

pip install simple-ai

Examples

Simple AI allows you to define problems and look for the solution with different strategies. Another samples are in the samples directory, but here is one.

The following problem defines the 8 Puzzle problem (a smaller version of the Fifteen puzzle: http://en.wikipedia.org/wiki/Fifteen_puzzle). States are defined as a list of lists of integers, representing the order of the tiles and 0 being the empty tile. The actions are defined as where the empty tile should go with that action.

After you have the result you can

print result.path()

to get the sequence of actions that lead to the solution from the initial state.

# coding=utf-8
from ai.models import Problem
from ai.methods import *
import copy


class EightPuzzleProblem(Problem):

    def __init__(self):
        initial = [
            [0, 2, 3],
            [1, 8, 5],
            [4, 7, 6]]
        super(EightPuzzleProblem, self).__init__(initial_state=initial)

    def _get_empty_coordinates(self, state):
        '''Returns the coordinates of the empty tile as dictionary'''
        for row in state:
            if 0 in row:
                break
        return {'row': state.index(row), 'column': row.index(0)}

    def _switch_tiles(self, state, tile1, tile2):
        '''Makes a copy of ``state`` and switches the ``tile1`` with
           the ``tile2``'''
        new_state = copy.deepcopy(state)
        aux = new_state[tile2[0]][tile2[1]]
        new_state[tile2[0]][tile2[1]] = new_state[tile1[0]][tile1[1]]
        new_state[tile1[0]][tile1[1]] = aux
        return new_state

    def actions(self, state):
        actions = []
        coordinates = self._get_empty_coordinates(state)
        if coordinates['row'] > 0:
            actions.append('up')
        if coordinates['row'] < 2:
            actions.append('down')
        if coordinates['column'] > 0:
            actions.append('left')
        if coordinates['column'] < 2:
            actions.append('right')
        return actions

    def result(self, state, action):
        coordinates = self._get_empty_coordinates(state)
        empty_tile = (coordinates['row'], coordinates['column'])
        if action == 'up' and coordinates['row'] > 0:
            tile2 = (coordinates['row'] - 1, coordinates['column'])
        if action == 'down' and coordinates['row'] < 2:
            tile2 = (coordinates['row'] + 1, coordinates['column'])
        if action == 'left' and coordinates['column'] > 0:
            tile2 = (coordinates['row'], coordinates['column'] - 1)
        if action == 'right' and coordinates['column'] < 2:
            tile2 = (coordinates['row'], coordinates['column'] + 1)
        new_state = self._switch_tiles(state, empty_tile, tile2)
        return new_state

    def is_goal(self, state):
        ''' Check if the state is goal:
            | 1 2 3 |
            | 4 5 6 |
            | 7 8   |
        '''
        return (state[0] == [1, 2, 3] and
                state[1] == [4, 5, 6] and state[2] == [7, 8, 0])

    def heuristic(self, state):
        total = 0
        row_no = 0
        for row in state:
            for i in row:
                total += abs(int((i - 1) / 3) - row_no) + \
                    abs((i - 1) % 3 - row.index(i))
            row_no += 1
        return total

problem = EightPuzzleProblem()

result = astar_search(problem)

Authors

Juan Pedro Fisanotti fisadev@gmail.com

Rafael Carrascosa rcarrascosa@machinalis.com

Santiago Romero sromero@machinalis.com

Special acknowledgements to Machinalis (http://www.machinalis.com/) for the time provided to work on this project.