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

>最初有N个机器人(通常N> 100)处于静止状态.
>每个机器人吸引半径为r的所有其他机器人.
>我有一组方程式,可以用来计算加速度,速度和功率.因此,时间间隔后机器人的位置.简而言之,经过delta时间后,我可以找到每个机器人的位置.
>我要做的只是针对给定的增量.我需要显示每个机器人的每个机器人的位置.

问题实际上很简单.算法将是这样的：

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流程的笛卡尔网格.

>因为每个机器人的计算都是独立的任务.每个机器人的计算
可以由独立线程完成.对？
>我对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：t = 9的位置是(21.1051065245,-53.8757356694)

此代码中有错误. Bot的t = 0位置由position()决定xAcceleration& y加速.我们需要使用所有其他粒子的先前迭代的位置.

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))

accelerator_along_X&中的位置函数accelerator_along_Y应该返回机器人的最新位置.最新的意思是该位置在上一次迭代的末尾.因此,每个流程都必须将其最新位置告知其他流程.在知道机器人的最新位置之前,该过程必须等待.

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

关于如何做的任何想法？我猜这就是为什么在问题中建议使用MPI的原因.

解决方法:

因此,这里的窍门是,在每个步骤中,所有机器人都必须在某个时候查看所有其他机器人的数据.这使得有效的并行化变得很困难！

一种简单的方法是让每个进程都在自己的机器人上跳开,首先计算自交互,然后从其他处理器一个接一个地获取数据并计算这些力.请注意,这不是唯一的方法！此外,此类事物(分子动力学或大多数天体N体模拟)的现实世界求解器完全采用了不同的方法,仅对远处的对象进行大约处理,因为远处的对象与附近的对象无关紧要.

以下是使用两个mpi进程(使用mpi4py和matplotlib / pylab进行绘图)对该方法进行的简单python实现.这将是一条流水线；每个处理器将其数据块发送到下一个邻居,进行计算,然后重复此过程,直到每个人都看到每个人的数据为止.理想情况下,您将在管道进行时更新绘图,这样就无需立即将所有数据都存储在内存中.

您将使用mpirun -np 2 ./robots.py运行该程序；请注意,您需要安装MPI库,然后mpi4py需要知道在哪里可以找到这些库.

还要注意,我在将所有机器人数据发送到邻居方面非常浪费.邻居只关心位置.

#!/usr/bin/env python
import numpy
import pylab
from mpi4py import MPI

class Robot(object):
    def __init__(self, id, x, y, vx, vy, mass):
        self.id = id
        self.x = x
        self.y = y
        self.vx = vx
        self.vy = vy
        self.ax = 0.
        self.ay = 0.
        self.mass = mass
    def rPrint(self):
        print "Robot ",self.id," at (",self.x,",",self.y,")"
    def interact(self, robot2):
        dx = (self.x-robot2.x)
        dy = (self.y-robot2.y)
        eps = 0.25
        idist3 = numpy.power(numpy.sqrt(dx*dx +dy*dy + eps*eps),-3)
        numerator = -self.mass*robot2.mass
        self.ax += numerator*dx*idist3
        self.ay += numerator*dy*idist3
        robot2.ax -= numerator*dx*idist3
        robot2.ay -= numerator*dy*idist3
    def updatePos(self, dt):
        self.x += 0.5*self.vx*dt
        self.y += 0.5*self.vy*dt
        self.vx += self.ax*dt
        self.vy += self.ay*dt
        self.x += 0.5*self.vx*dt
        self.y += 0.5*self.vy*dt
        self.ax = 0.
        self.ay = 0.



def init(nRobots):
    myRobotList = []
    vx = 0.
    vy = 0.
    mass = 1.
    for i in range(nRobots):
        randpos = numpy.random.uniform(-3,+3,2)
        rx = randpos[0]
        ry = randpos[1]
        myRobotList.append(Robot(i, rx, ry, vx, vy, mass))
    return myRobotList

def selfForces(robotList):
    nRobots = len(robotList)
    for i in range(nRobots-1): 
       for j in range (i+1, nRobots):
            robotList[i].interact(robotList[j])

def otherRobotForces(myRobotList, otherRobotList):
    for i in myRobotList:
        for j in otherRobotList:
            i.interact(j)

def plotRobots(robotList):
    xl = []
    yl = []
    vxl = []
    vyl = [] 
    for i in robotList:
       xl.append(i.x)
       yl.append(i.y)
       vxl.append(i.vx)
       vyl.append(i.vy)
    pylab.subplot(1,1,1)
    pylab.plot(xl,yl,'o')
    pylab.quiver(xl,yl,vxl,vyl)
    pylab.show()

if __name__ == "__main__":
    comm = MPI.COMM_WORLD
    nprocs = comm.Get_size()
    rank   = comm.Get_rank()

    if (nprocs != 2):
        print "Only doing this for 2 for now.."
        sys.exit(-1)
    neigh = (rank + 1) %  nprocs

    robotList = init(50)

    for i in range (10):
        print "[",rank,"] Doing step ", i
        selfForces(robotList)

        request = comm.isend(robotList, dest=neigh, tag=11)
        otherRobotList = comm.recv(source=neigh, tag=11)

        otherRobotForces(robotList,otherRobotList)

        request.Wait()

        for r in robotList:
            r.updatePos(0.05)



    if (rank == 0):
        print "plotting Robots"
        plotRobots(robotList + otherRobotList)