Resolución de Problema de Navegación de Robot en Matriz con Costes Variables

Formalización del Problema

Espacio de Estados

Este problema puede ser representado mediante una matriz de 2 dimensiones con n filas y m columnas (n=4 y m=3 para este enunciado). Cada estado (i, j) indica, por tanto, las coordenadas de la celda en la que se encuentra el robot en cada momento.

Estado Inicial

El estado inicial es (1, 1) para este enunciado.

Estado Final

El estado final es (4, 3).

Test Objetivo

Consiste en comprobar que el estado actual (i, j) es igual al Estado Final: (i, j) = Estado Final.

Operadores

Los operadores son los movimientos a celdas adyacentes de la matriz:

• Mover abajo
• Mover arriba
• Mover izquierda
• Mover derecha

Cada movimiento implica mover una posición. Además, según este enunciado, los costes de aplicar un operador son 100, 200 o 300 euros, dependiendo del estado en que nos encontremos. Por tanto, si el movimiento es realizado, además de devolver el estado sucesor, es necesario devolver el coste de aplicar dicho operador.

Considerando las constantes: MAX_FILAS = 4 y MAX_COL = 3, se definen los siguientes procedimientos:

Procedimiento MoverAbajo

procedimiento MoverAbajo(E/S entero: fil, E/S entero: col, S entero: coste)
var
  entero: coste_calculado
inicio
  coste_calculado <- 0
  si fil < MAX_FILAS entonces
    // Calcular coste basado en la celda actual ANTES de mover
    si fil = 2 Y (col = 1 O col = 3) entonces
      coste_calculado <- 200
    sino
      si fil = 3 entonces
        coste_calculado <- 300
      sino
        coste_calculado <- 100
      fin_si
    fin_si
    // Actualizar posición
    fil <- fil + 1
    coste <- coste_calculado // Asignar coste de salida
  sino
    coste <- 0 // No se puede mover, coste 0
  fin_si
fin_procedimiento

Procedimiento MoverArriba

procedimiento MoverArriba(E/S entero: fil, E/S entero: col, S entero: coste)
var
  entero: coste_calculado
inicio
  coste_calculado <- 0
  si fil > 1 entonces
    // Calcular coste basado en la celda actual ANTES de mover
    si fil = 3 Y (col = 1 O col = 3) entonces
      coste_calculado <- 200
    sino
      si fil = 4 entonces
        coste_calculado <- 300
      sino
        coste_calculado <- 100
      fin_si
    fin_si
    // Actualizar posición
    fil <- fil - 1
    coste <- coste_calculado // Asignar coste de salida
  sino
    coste <- 0 // No se puede mover, coste 0
  fin_si
fin_procedimiento

Procedimiento MoverIzq

procedimiento MoverIzq(E/S entero: fil, E/S entero: col, S entero: coste)
var
  entero: coste_calculado
inicio
  coste_calculado <- 0
  si col > 1 entonces
    // Calcular coste basado en la celda actual ANTES de mover
    si fil = 2 Y col = 2 entonces
      coste_calculado <- 200
    sino
      coste_calculado <- 100
    fin_si
    // Actualizar posición
    col <- col - 1
    coste <- coste_calculado // Asignar coste de salida
  sino
    coste <- 0 // No se puede mover, coste 0
  fin_si
fin_procedimiento

Procedimiento MoverDer

procedimiento MoverDer(E/S entero: fil, E/S entero: col, S entero: coste)
var
  entero: coste_calculado
inicio
  coste_calculado <- 0
  si col < MAX_COL entonces
    // Calcular coste basado en la celda actual ANTES de mover
    si fil = 2 Y col = 1 entonces
      coste_calculado <- 200
    sino
      coste_calculado <- 100
    fin_si
    // Actualizar posición
    col <- col + 1
    coste <- coste_calculado // Asignar coste de salida
  sino
    coste <- 0 // No se puede mover, coste 0
  fin_si
fin_procedimiento

Definición de la Heurística

Este problema se representa en una matriz de 2 dimensiones donde cada movimiento consiste en ir de una celda a otra adyacente. Por tanto, una heurística admisible puede estar relacionada con el número de celdas que restan hasta la solución, expresada mediante la distancia de Manhattan: número de filas y número de columnas desde la celda actual hasta la celda objetivo.

Por otra parte, el enunciado ya indica que el coste mínimo para atravesar dos salas es de 100 euros. Realizando una relajación de las condiciones del problema, se puede estimar que cada movimiento tiene un coste mínimo de 100. Por lo tanto, la heurística se define como:

H(n) = 100 * Distancia_Manhattan(n, Estado_Objetivo)

Siendo n cualquier estado del espacio del problema.

Admisibilidad de la Heurística

La función heurística es admisible si nunca sobreestima el coste real de llegar a la solución. Esta heurística calcula el coste estimado basándose en el mínimo número de movimientos necesarios (según la distancia de Manhattan) y multiplicándolo por el mínimo coste posible de un movimiento (100 euros). Por tanto, nunca sobreestimará el coste real de llegar a la solución, cumpliendo la condición de admisibilidad.