Cómo reducir el número de estados en un algoritmo BFS?

Tengo un algoritmo de BFS en Python. Estoy creando el árbol mientras lo recorro. Aquí está el código de mi implementación:

def bfs(estado_inicial, objetivo):

    visitados = []
    cola = [estado_inicial]

    encontrado = False

    while not encontrado:

        s = cola.pop(0)

        # Objetivo
        for r in s.robots:
            if r.x == 5 and r.y == 10:
                print("ENCONTRADO")
                return visitados

        # Si el estado no tiene hijos -> Crear sus hijos
        if not s.hijos:
            s.crear_hijo()

        for hijo in s.hijos:
            if hijo not in visitados:
                visitados.append(hijo)
                cola.append(hijo)

Aquí quiero intentar una solución en 3 movimientos. Cuando imprimo la longitud de la lista visitados, imprime 20k estados. Eso es demasiado porque cada padre tiene 16 hijos, por lo que una solución de 3 movimientos genera 16^3 + 16^2 + 16 estados.

¿Es el problema mi BFS?
El número de hijos creados es el correcto, hice muchas pruebas.

Gracias por sus respuestas.