python - 如何将这种情况与机器人并行化

Question

我正在研究机器人问题。情况是这样的:

1. 最初有 N 个机器人(通常 N>100)都处于静止状态。
2. 每个机器人都会吸引其半径为 r 的所有其他机器人。
3. 我有一组方程式，可以用来计算加速度、速度以及机器人在时间增量t 后的位置。简单地说，我可以在 deltat 时间后找到每个机器人的位置。
4. 我需要做的就是针对给定的 deltat。我需要为每个 deltat 显示每个机器人的位置。

问题其实很简单。算法将是这样的:

del_t = ;its given
initialPositions = ;its given
num_robots = ;its given

以下代码针对每个 del_t

执行

robots = range(1,no_robots)
for R in robots:
    for r in robots:
        if  distanceBetween(r,R) <= radius and r is not R:
            acceleration_along_X[R] += xAcceleration( position(r), position(R) )
            acceleration_along_Y[R] += yAcceleration( position(r), position(R) )
    currVelocity_along_X[R] = prevVelocity_along_X[R] + acceleration_along_X[R] * del_t
    currVelocity_along_Y[R] = prevVelocity_along_Y[R] + acceleration_along_Y[R] * del_t
    curr_X_coordinate[R] = prev_X_coordinate[R] + currVelocity_along_X[R] * del_t
    curr_Y_coordinate[R] = prev_Y_coordinate[R] + currVelocity_along_Y[R] * del_t
    print 'Position of robot ' + str(R) + ' is (' + curr_X_coordinate[R] + ', ' + curr_Y_coordinate[R] +' ) \n'
    prev_X_coordinate[R] = curr_X_coordinate[R]
    prev_Y_coordinate[R] = curr_Y_coordinate[R]
    prevVelocity_along_X[R] = currVelocity_along_X[R]
    prevVelocity_along_Y[R] = currVelocity_along_Y[R]

现在我需要并行化算法并设置 MPI 进程的笛卡尔网格。

1. 因为每个机器人的计算是一项独立的任务。每个机器人的计算 可以由独立线程完成。对吧？
2. 我对 MPI 一无所知。这个“MPI 过程的笛卡尔网格”是什么意思？我该如何设置这个网格？我对此一无所知。

编辑:

现在问题变得有趣了。其实，事情并没有我想的那么简单。看完Unode's answer .我继续通过使用多处理进行并行化来应用他的方法二。

这是代码。 printPositionOfRobot 是我的串行算法。基本上，它应该打印机器人的位置(id robot_id)t=1,2,3,4,5,6,7,8,9,10。 (此处 del_t 取为 1。num_iterations = 10。每个机器人打印如下消息:Robot8 : Position at t = 9 is (21.1051065245, - 53.8757356694 )

此代码中存在错误。机器人的 t=0 位置由 position() 给出，用于确定 xAcceleration 和 yAcceleration。我们需要使用所有其他粒子先前迭代的位置。

from multiprocessing import Pool
import math


def printPositionOfRobot(robot_id):
    radius = 3
    del_t = 1
    num_iterations = 10
    no_robots = 10

    prevVelocity_along_X = 0
    prevVelocity_along_Y = 0
    acceleration_along_X = 0
    acceleration_along_Y = 0
    (prev_X_coordinate,prev_Y_coordinate) = position(robot_id)#!!it should call initialPosition()
    for i in range(1,num_iterations+1):
        for r in range(no_robots):
            if  distanceBetween(r,robot_id) <= radius and r is not robot_id:
                acceleration_along_X += xAcceleration( position(r), position(robot_id) ) #!! Problem !!
                acceleration_along_Y += yAcceleration( position(r), position(robot_id) )#!! Problem !!
        currVelocity_along_X = prevVelocity_along_X + acceleration_along_X * del_t
        currVelocity_along_Y = prevVelocity_along_Y + acceleration_along_Y * del_t
        curr_X_coordinate = prev_X_coordinate + currVelocity_along_X * del_t
        curr_Y_coordinate = prev_Y_coordinate + currVelocity_along_Y * del_t
        print 'Robot' + str(robot_id) + ' : Position at t = '+ str(i*del_t) +' is (' + str(curr_X_coordinate) + ', ' + str(curr_Y_coordinate) +' ) \n'
        prev_X_coordinate = curr_X_coordinate
        prev_Y_coordinate = curr_Y_coordinate
        prevVelocity_along_X = currVelocity_along_X
        prevVelocity_along_Y = currVelocity_along_Y

def xAcceleration((x1,y1),(x2,y2)):
    s = distance((x1,y1),(x2,y2))
    return 12*(x2-x1)*( pow(s,-15) - pow(s,-7) + 0.00548*s )

def yAcceleration((x1,y1),(x2,y2)):
    s = distance((x1,y1),(x2,y2))
    return 12*(y2-y1)*( pow(s,-15) - pow(s,-7) + 0.00548*s )

def distanceBetween(r,robot_id):
    return distance(position(r), position(robot_id))

def distance((x1,y1),(x2,y2)):
    return math.sqrt( (x2-x1)**2 + (y2-y1)**2 )

def Position(r): #!!name of this function should be initialPosition
    k = [(-8.750000,6.495191) , (-7.500000,8.660254) , (-10.000000,0.000000) , (-8.750000,2.165064) , (-7.500000,4.330127) , (-6.250000,6.495191) , (-5.000000,8.660254) , (-10.000000,-4.330127) , (-8.750000,-2.165064) , (-7.500000,0.000000) ]
    return k[r]

if __name__ == "__main__":
    no_robots = 10  # Number of robots you need
    p = Pool(no_robots)  # Spawn a pool of processes (one per robot in this case)
    p.map(printPositionOfRobot, range(no_robots))

acceleration_along_X 和acceleration_along_Y 中的position 函数应该返回机器人的最新位置。最新的意思是最后的位置之前的迭代。因此，每个进程都必须通知其他进程其最新位置。直到机器人的最新位置知道该过程必须等待。

其他方式可以是所有进程都编辑一个全局位置。(我想知道这是否可能，因为每个进程都有自己的虚拟地址空间)。如果一个进程尚未达到该迭代，则所有其他进程必须等待。

关于如何着手的任何想法？我想这就是问题中建议使用 MPI 的原因。

Answer 1

注意:Python 的线程 仍然在同一个处理器上运行。如果您想使用机器的所有处理器，您应该使用 multiprocessing (python2.6+)。

只有在计算分布在多台计算机上时，使用 MPI 才会为您带来明显的好处。

有两种方法可以解决您的问题。由于您拥有完全独立的进程，因此您可以根据需要多次启动算法(为每个机器人传递一个唯一标识符)并让操作系统处理并发。

1 - 一个简短的 Linux shell 脚本(或 Windows BATCH 语言中的等效脚本):

#!/bin/sh
for i in {0..99}; do
    echo "Running $i"
    python launch.py $i &
done

注意:launch.py​​ 之后的 & 确保您实际上以连续的方式启动所有进程，而不是等待一个完成然后启动下一个一个。

2 - 如果您想在 python 中完成所有操作，您可以使用以下简单的并行化方法:

from multiprocessing import Pool

def your_algorithm(robot_id):
    print(robot_id)

if __name__ == "__main__":
    robots = 100  # Number of robots you need
    p = Pool(robots)  # Spawn a pool of processes (one per robot in this case)
    p.map(your_algorithm, range(robots))

map 函数负责为每个机器人调度一个独立的操作。

如果您确实需要使用 MPI，我建议 mpi4py .

关于 Cartesian grid 代表什么的信息，请尝试 this