多机器人任务分配

多机器人任务分配，要解决的是这样一个问题：当一队机器人面对一堆活儿时，到底该让哪台机器人去做哪件事。设想一座仓库里有十台配送机器人，要搬运四十个包裹：得有人——或某段软件——把包裹分派下去，好让整桩活儿尽快做完、谁也不撞着谁，也不会出现一台机器人闲着、另一台却忙不过来的情形。把这件分派的事做好，并随着新活儿不断出现而反复地做，就是任务分配。

难就难在，最好的答案同时取决于一切：每台机器人离每件活儿有多远、还剩多少电量、有没有两件活儿由同一台机器人一趟顺路做完更省事，以及局面还在不停地变。像“每台机器人都去抢离自己最近的活儿”这样简单的规则虽快，却可能让整队的负担严重失衡。所以机器人学者要找的，是能让总时间、总行驶距离，或别的某种代价最小的分派方案——这是一场拔河：一头要让每台机器人分到公平的负担，另一头要让整桩活儿尽快完成。

一类常用的解法，借用了拍卖（或市场）的思路。每件活儿被拿出来“竞标”；每台机器人算一算自己做这件活儿能有多便宜（按时间或能量计），就报出这个数当作出价；活儿归出价最低者，再对下一件活儿重复这个过程。不需要有一个中央老板什么都知道——机器人只需互相比一比出价——所以这类以市场为基础的方法，即便在机器人中途加入、退出，或发现世界与预想不符时，也照样行得通。