多目标点路径规划---模拟退火算法+A*算法送餐机器人多目标点路径规划，室内AGV路径规划

hid62962581

665人浏览 · 2026-02-08 18:45:00

hid62962581 · 2026-02-08 18:45:00 发布

多目标点路径规划---模拟退火算法+A*算法送餐机器人多目标点路径规划，室内AGV路径规划。基于模拟退火算法融合A*算法的移动机器人路径规划 1，从厨房出发，移动到多个目标点，最后返回厨房。 2，采用A*算法规划两点间的距离，然后依据规划路径距离模拟退火算法运算全过程最短距离。旅行商的室内规划应用

厨房里的送餐机器人刚接了个大单——要送8份餐到不同房间。它盯着地图上闪烁的标记点突然死机：先送哪家能少走冤枉路？这个问题让无数机器人程序猿秃了头，直到他们发现用A*算法和模拟退火搞组合技有奇效。

咱们先看A算法怎么搞定单点路径。假设机器人要从坐标(0,0)到(5,5)，地图上有几个不可逾越的餐桌障碍。用Python实现个极简版A：

def a_star(start, end, grid):
    open_set = PriorityQueue()
    open_set.put((0, start))
    came_from = {}
    g_score = {start: 0}
    
    while not open_set.empty():
        current = open_set.get()[1]
        if current == end:
            return reconstruct_path(came_from, current)
        
        for neighbor in get_neighbors(current, grid):
            tentative_g = g_score[current] + 1  # 假设每步移动代价为1
            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score = tentative_g + heuristic(neighbor, end)
                open_set.put((f_score, neighbor))
    return None

这段代码的亮点在PriorityQueue——它确保程序永远先扩展最有希望的节点。heuristic函数如果用曼哈顿距离，在室内直角走廊环境比欧氏距离更靠谱。但注意别让机器人斜着穿墙，会撞到端着热汤的服务员。

当目标点超过5个时，问题复杂度会指数爆炸。这时候模拟退火就该上场了。咱们先定义个能量函数：

def total_distance(path_order, distance_matrix):
    total = 0
    for i in range(len(path_order)-1):
        total += distance_matrix[path_order[i]][path_order[i+1]]
    return total + distance_matrix[path_order[-1]][0]  # 最后返回厨房

distance_matrix是提前用A*算好的各点间最短距离矩阵。这招预处理让计算量减半——总比每次迭代都重新算路径强，毕竟机器人电池撑不住。

接下来是模拟退火的核心操作：

current_order = initial_order.copy()
best_order = current_order.copy()
T = 1000.0  # 初始温度
cooling_rate = 0.003

while T > 1:
    new_order = perturb(current_order)  # 随机交换两个点或翻转子序列
    current_cost = total_distance(current_order, distance_matrix)
    new_cost = total_distance(new_order, distance_matrix)
    
    if acceptance_probability(current_cost, new_cost, T) > random.random():
        current_order = new_order
        if new_cost < total_distance(best_order, distance_matrix):
            best_order = new_order.copy()
    
    T *= 1 - cooling_rate  # 降温曲线

perturb函数里有个小技巧：当温度高时允许大范围扰动（比如随机打乱整个序列），温度降低后改为相邻点交换，这样后期微调更有效。就像厨师开始大火翻炒，最后转小火收汁。