En el ámbito de la robótica, la planificación de rutas es fundamental, especialmente para la cobertura completa en sistemas como drones múltiples, robots móviles y robots aspiradores. Este artículo explora métodos basados en el algoritmo A* para la planificación de rutas de cobertura total y su extensión a la coordinación multi-robot.

Fundamentos del Algoritmo A*

El algoritmo A* es un método de búsqueda que encuentra la ruta de menor costo en un grafo. Evalúa nodos usando la fórmula f(n) = g(n) + h(n), donde g(n) es el costo desde el inicio hasta el nodo actual, y h(n) es una heurística que estima el costo restante al objetivo. Se priorizan nodos con menor valor de f(n).

Ejemplo de Implementación en C++

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

struct GraphNode {
    int posX;
    int posY;
    double costG;
    double estimateH;
    double totalF;
    GraphNode* prev;
    GraphNode(int x, int y) : posX(x), posY(y), costG(0), estimateH(0), totalF(0), prev(nullptr) {}
};

double calculateHeuristic(GraphNode* node, GraphNode* target) {
    double dx = node->posX - target->posX;
    double dy = node->posY - target->posY;
    return std::sqrt(dx * dx + dy * dy);
}

std::vector<GraphNode*> findPathAStar(std::vector<std::vector<bool>>& environment, GraphNode* origin, GraphNode* destination) {
    auto comparator = [](GraphNode* a, GraphNode* b) { return a->totalF > b->totalF; };
    std::priority_queue<GraphNode*, std::vector<GraphNode*>, decltype(comparator)> openSet(comparator);
    std::vector<std::vector<bool>> visited(environment.size(), std::vector<bool>(environment[0].size(), false));

    openSet.push(origin);

    while (!openSet.empty()) {
        GraphNode* current = openSet.top();
        openSet.pop();

        if (current->posX == destination->posX && current->posY == destination->posY) {
            std::vector<GraphNode*> route;
            while (current != nullptr) {
                route.push_back(current);
                current = current->prev;
            }
            return route;
        }

        visited[current->posX][current->posY] = true;

        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 && dy == 0) continue;
                int newX = current->posX + dx;
                int newY = current->posY + dy;

                if (newX >= 0 && newX < environment.size() && newY >= 0 && newY < environment[0].size() &&
                    !environment[newX][newY] && !visited[newX][newY]) {
                    GraphNode* neighbor = new GraphNode(newX, newY);
                    neighbor->costG = current->costG + 1;
                    neighbor->estimateH = calculateHeuristic(neighbor, destination);
                    neighbor->totalF = neighbor->costG + neighbor->estimateH;
                    neighbor->prev = current;
                    openSet.push(neighbor);
                }
            }
        }
    }
    return std::vector<GraphNode*>();
}

En este código, la estructura GraphNode almacena posiciones y valores de costos. La función calculateHeuristic implementa la distancia euclidiana. El algoritmo principal findPathAStar utiliza una cola de prioridad para expandir nodos con menor totalF, explorando vecinos válidos y construyendo la ruta óptima.

Planificación de Cobertura Total para Múltiples Robots

Para la cobertura completa con drones o robots móviles, se extiende el algoritmo A* para garantizar que toda el área sea explorada. Esto implica definir mapas personalizados y gestionar obstáculos.

Configuración Personalizada del Mapa

El entorno se modela como una cuadrícula 2D, donde cada celda indica si es transitable o no. Ejemplo en C++:

std::vector<std::vector<bool>> environmentGrid = {
    {false, false, false, false, false},
    {false, true, false, true, false},
    {false, false, false, false, false},
    {false, true, false, true, false},
    {false, false, false, false, false}
}; // 'true' representa un obstáculo, 'false' es área libre.

Los mapas pueden actualizarse dinámicamente basados en datos de sensores, marcando celdas como obstáculos cuando se detectan.

Coordinación en Planificación de Rutas Multi-Robot

Para la coordinación de múltiples robots, se asignan regiones separadas a cada unidad, aplicando el algoritmo A* de manera independiente para evitar colisiones y asegurar cobertura completa. Esto se puede implementar mediante partición espacial o asignación de zonas.

Enfoque de Implementación para Coordinación

// Definir puntos de inicio y destino para dos robots
GraphNode* robotAlphaStart = new GraphNode(0, 0);
GraphNode* robotAlphaEnd = new GraphNode(4, 4);
GraphNode* robotBetaStart = new GraphNode(0, 4);
GraphNode* robotBetaEnd = new GraphNode(4, 0);

// Planificar rutas independientes
std::vector<GraphNode*> pathAlpha = findPathAStar(environmentGrid, robotAlphaStart, robotAlphaEnd);
std::vector<GraphNode*> pathBeta = findPathAStar(environmentGrid, robotBetaStart, robotBetaEnd);

Este ejemplo básico ilustra la planificación para dos robots. En aplicaciones prácticas, se consideran factores como velocidad, posiciones en tiempo real y dinámicas de movimiento para ajustar rutas continuamente.

El algoritmo A* es altamente flexible y extensible, adecuado para escenarios como robots aspiradores, donde se optimiza la cobertura para minimizar repeticiones. Su implementación permite personalizaciones avanzadas para diversas necesidades de planificación de rutas.