{"id":25181,"date":"2021-04-01T21:40:53","date_gmt":"2021-04-01T13:40:53","guid":{"rendered":"https:\/\/swarma.org\/?p=25181"},"modified":"2021-04-01T21:40:53","modified_gmt":"2021-04-01T13:40:53","slug":"%e8%ae%ba%e6%96%87%e5%90%88%e9%9b%86%ef%bc%9a%e5%a4%a7%e8%a7%84%e6%a8%a1%e5%a4%9a%e6%99%ba%e8%83%bd%e4%bd%93%e8%b7%af%e5%be%84%e8%a7%84%e5%88%92","status":"publish","type":"post","link":"https:\/\/swarma.org\/?p=25181","title":{"rendered":"\u8bba\u6587\u5408\u96c6\uff1a\u5927\u89c4\u6a21\u591a\u667a\u80fd\u4f53\u8def\u5f84\u89c4\u5212"},"content":{"rendered":"
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

<\/p>\n<\/section>\n

\n
\n
\n
\n
\n
\n

<\/section>\n<\/section>\n
\n
\n

\u5bfc\u8bed<\/strong><\/p>\n<\/section>\n<\/section>\n

\n

<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n
\n
\n
\n

\u4eba\u591a\u667a\u80fd\u4f53\u8def\u5f84\u89c4\u5212\uff0c\u82f1\u6587\u53ebMulti-Agent Path Finding\uff0c\u7b80\u79f0\u4e3aMAPF\u3002<\/strong><\/strong><\/span>MAPF\u7684\u7814\u7a76\u4e3b\u8981\u6709\u4e24\u5927\u65b9\u5411\uff0c\u4e00\u4e2a\u662f\u5982\u4f55\u6539\u8fdb\u73b0\u6709\u7684\u7b97\u6cd5\uff0c\u4e00\u4e2a\u662f\u5728\u5b9e\u9645\u5e94\u7528\u4e2d\u5982\u4f55\u5904\u7406\u7ea6\u675f\uff0c<\/strong><\/strong><\/span>\u5728\u6b64\u6b21AAAI\u4e2d\uff0c<\/strong><\/strong><\/span>\u5357\u52a0\u5dde\u5927\u5b66\u8ba1\u7b97\u673a\u7cfb\u535a\u58eb<\/strong>\u674e\u5a07\u9633\u4e00\u5171\u6709\u56db\u7bc7\u8bba\u6587\u88ab\u9009\u4e2d\uff0c<\/strong><\/strong><\/span>\u8fd94\u7bc7\u8bba\u6587\u5951\u5408\u4e86\u8fd9\u51e0\u4e2a\u65b9\u5411\uff0c\u5728\u8fd9\u7bc7\u6587\u7ae0\u4e2d\uff0c\u4f5c\u8005\u674e\u5a07\u9633\u5bf9\u8fd9\u56db\u7bc7\u6587\u7ae0\u4f9d\u6b21\u8fdb\u884c\u4e86\u4ecb\u7ecd<\/strong><\/strong><\/span><\/strong><\/span><\/strong><\/span><\/p>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

\n
\n
\n
<\/svg><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n
\n
<\/section>\n<\/section>\n<\/section>\n
\n
\n
\n
<\/svg><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n
\u674e\u5a07\u9633 | \u4f5c\u8005<\/strong><\/span><\/p>\n

AI TIME \u8bba\u9053<\/span> | \u6765\u6e90<\/strong><\/p>\n<\/section>\n

\n


<\/p>\n

<\/section>\n<\/section>\n

\n
\n
\n
\n

\u8bba\u6587\u9898\u76ee\uff1a<\/span><\/p>\n

EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding<\/span><\/span><\/p>\n

\u8bba\u6587\u5730\u5740\uff1a<\/span><\/p>\n

https:\/\/arxiv.org\/abs\/2010.01367<\/span><\/p>\n<\/section>\n<\/section>\n<\/blockquote>\n<\/h1>\n

\n
\n
\n


<\/p>\n

\n
<\/section>\n<\/section>\n

\n
\n
\n
\n

\u8bba\u6587\u9898\u76ee\uff1a<\/span><\/p>\n

Symmetry Breaking for k-Robust Multi-Agent Path Finding<\/span><\/span><\/p>\n

\u8bba\u6587\u5730\u5740\uff1a<\/span><\/p>\n

https:\/\/arxiv.org\/abs\/2102.08689<\/span><\/span><\/p>\n<\/section>\n<\/section>\n<\/blockquote>\n<\/h1>\n

 <\/span><\/section>\n<\/section>\n<\/section>\n<\/section>\n
\n
<\/section>\n<\/section>\n

\n
\n
\n
\n

\u8bba\u6587\u9898\u76ee\uff1a<\/span><\/p>\n

Lifelong Multi-Agent Path Finding in Large-Scale Warehouses<\/span><\/span><\/p>\n

\u8bba\u6587\u5730\u5740\uff1a<\/span><\/p>\n

https:\/\/arxiv.org\/abs\/2005.07371<\/span><\/p>\n<\/section>\n<\/section>\n<\/blockquote>\n<\/h1>\n

\n
\n
\n


<\/p>\n

<\/section>\n<\/section>\n

\n
\n
\n
\n

\u8bba\u6587\u9898\u76ee\uff1a<\/span><\/p>\n

Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances<\/span><\/span><\/p>\n

\u8bba\u6587\u5730\u5740\uff1a<\/span><\/p>\n

https:\/\/arxiv.org\/abs\/2012.09052<\/span><\/span><\/p>\n<\/section>\n<\/section>\n<\/blockquote>\n<\/h1>\n


<\/p>\n<\/section>\n<\/section>\n

\n
\n
\n
\n
\n

<\/section>\n

<\/section>\n
\n
<\/svg><\/section>\n<\/section>\n<\/section>\n
\n

\u4e00\u3001\u80cc\u666f<\/span><\/strong><\/strong><\/span><\/p>\n<\/section>\n

\n

<\/section>\n

<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/h3>\n


<\/p>\n

<\/p>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

\n


<\/p>\n

\u591a\u667a\u80fd\u4f53\u8def\u5f84\u89c4\u5212\uff0c\u82f1\u6587\u53ebMulti-Agent Path Finding\uff0c\u7b80\u79f0\u4e3aMAPF\u3002<\/span><\/strong>\u5b83\u672c\u8d28\u4e0a\u662f\u4e00\u4e2a\u6570\u5b66\u95ee\u9898\uff0c\u901a\u8fc7\u7ed9\u6bcf\u4e2a\u673a\u5668\u4eba\u89c4\u5212\u4e00\u6761\u8def\u5f84\uff0c\u4fdd\u8bc1\u8fd9\u4e9b\u8def\u5f84\u4e0d\u76f8\u649e\uff0c\u5e76\u6700\u5c0f\u5316\u603b\u7684\u8fd0\u884c\u65f6\u95f4\u3002<\/span><\/p>\n


<\/p>\n<\/section>\n

\n

<\/p>\n<\/section>\n

\n


<\/p>\n

\u5b83\u6709\u5f88\u591a\u5b9e\u9645\u5e94\u7528\uff0c\u5176\u4e2d\u4e00\u4e2a\u662f\u4ed3\u50a8\u7cfb\u7edf\u3002\u8fd1\u5e74\u6765\u673a\u5668\u4eba\u4ed3\u50a8\u7cfb\u7edf\u5438\u5f15\u4e86\u5f88\u591a\u4eba\u7684\u6ce8\u610f\uff0c\u51fa\u73b0\u4e86\u5404\u79cd\u5404\u6837\u7684\u4ed3\u50a8\u7cfb\u7edf\uff0c\u6bd4\u8f83\u5178\u578b\u7684\u6709\u4e9a\u9a6c\u900a\u7684Kiva system\uff0c\u4ee5\u53casorting center\uff0c\u548c\u4e00\u4e9b\u6bd4\u8f83\u65b0\u7684\u7cfb\u7edf\u3002\u8fd9\u4e9b\u7cfb\u7edf\u672c\u8d28\u4e0a\u662f\u7ed9\u6210\u767e\u4e0a\u5343\u4e2a\u673a\u5668\u4eba\u540c\u65f6\u505a\u89c4\u5212\u8def\u5f84\uff0c\u7136\u540e\u4fdd\u8bc1\u5b83\u4eec\u65e2\u4e0d\u76f8\u649e\uff0c\u540c\u65f6\u53c8\u80fd\u5f88\u5feb\u7684\u5230\u8fbe\u76ee\u7684\u5730\u3002<\/span><\/p>\n


<\/p>\n<\/section>\n

\n

<\/p>\n<\/section>\n

\n


<\/p>\n

\u4f20\u7edf\u65b9\u6cd5\u91c7\u7528single-agent\u65b9\u6cd5\uff0c\u901a\u8fc7\u7ed9\u6bcf\u4e00\u4e2a\u673a\u5668\u4eba\u89c4\u5212\u5b83\u4eec\u7684\u6700\u77ed\u8def\uff0c\u6216\u8005\u6700\u5c0f\u65f6\u95f4\u8def\u5f84\u3002\u5982\u679c\u4e24\u4e2a\u673a\u5668\u4eba\u53ef\u80fd\u76f8\u649e\uff0c\u5c31\u7528\u4e00\u4e9b\u7b80\u5355\u7684\u4ea4\u901a\u89c4\u5219\u5904\u7406\uff0c\u6bd4\u5982\u8bf4\u5176\u4e2d\u4e00\u4e2a\u673a\u5668\u4eba\u51cf\u901f\u6216\u6362\u4e00\u6761\u8def\u3002\u4f46\u8fd9\u79cd\u65b9\u6cd5\u5728\u7b80\u5355\u7684\u7cfb\u7edf\u4e2d\u5de5\u4f5c\u8f83\u597d\uff0c\u4e00\u65e6\u673a\u5668\u4eba\u6570\u91cf\u6216\u5bc6\u5ea6\u589e\u5927\uff0c\u5c31\u4f1a\u51fa\u73b0\u62e5\u5835\uff0c\u5bfc\u81f4\u6574\u4e2a\u7cfb\u7edf\u6548\u7387\u53d8\u4f4e\u3002\u800cMAPF solver\u628a\u6240\u6709\u673a\u5668\u4eba\u7684\u8def\u5f84\u4e00\u8d77\u89c4\u5212\uff0c\u4f1a\u8003\u8651\u5230\u5404\u79cd\u78b0\u649e\u7684\u53ef\u80fd\u6027\u3002\u5728\u540c\u7b49\u60c5\u51b5\u4e0b\uff0cMAPF solver\u53ef\u4ee5\u5f88\u597d\u7684\u53bb\u8c03\u5ea6\u6240\u6709\u7684\u673a\u5668\u4eba\u7684\u8def\u5f84\uff0c\u4f7f\u5f97\u5b83\u4eec\u53ef\u4ee5\u987a\u7545\u7684\u5230\u8fbe\u76ee\u7684\u5730\u3002<\/span><\/p>\n


<\/p>\n<\/section>\n

\n

<\/p>\n<\/section>\n

\n


<\/p>\n

\u8fd9\u5f20\u56fe\u5c55\u793a\u4e86\u4e0d\u540c\u673a\u5668\u4eba\u4e2a\u6570\u4e0b\uff0c\u7cfb\u7edf\u541e\u5410\u91cf\u7684\u53d8\u5316\u3002\u53ef\u4ee5\u770b\u5230\u5728\u4e00\u5f00\u59cb\u7684\u65f6\u5019\uff0c\u4e24\u79cd\u65b9\u6cd5\u5f88\u63a5\u8fd1\uff0c\u57fa\u672c\u4e0a\u4fdd\u6301\u7ebf\u6027\u589e\u52a0\uff0c\u4f46\u662f\u5f53\u673a\u5668\u4eba\u4e2a\u6570\u5230\u4e00\u5b9a\u503c\u7684\u65f6\u5019\uff0cSingle-agent\u4f1a\u51fa\u73b0\u62e5\u5835\uff0c\u5bfc\u81f4\u7cfb\u7edf\u7684\u541e\u5410\u91cf\u589e\u957f\u7387\u5f00\u59cb\u4e0b\u964d\uff0c\u7ecf\u8fc7\u5dc5\u5cf0\u4e4b\u540e\uff0c\u589e\u957f\u7387\u5f00\u59cb\u4e0b\u964d\uff0c\u8fd9\u662f\u56e0\u4e3a\u7cfb\u7edf\u4e2d\u51fa\u73b0\u4e86\u4e25\u91cd\u7684\u4ea4\u901a\u62e5\u5835\uff0c\u5bfc\u81f4\u7cfb\u7edf\u5f00\u59cb\u762b\u75ea\u3002\u800c\u5bf9\u4e8eMAPF solver\u6765\u8bf4\uff0c\u5728\u6d4b\u8bd5\u76841000\u4e2a\u673a\u5668\u4eba\u4e4b\u5185\uff0c\u541e\u5410\u91cf\u51e0\u4e4e\u4fdd\u6301\u7ebf\u6027\u589e\u957f\u3002<\/span><\/p>\n


<\/p>\n<\/section>\n

\n

<\/p>\n<\/section>\n

\n


<\/p>\n

\u9664\u4e86\u4ed3\u50a8\u7cfb\u7edf\uff0c\u5176\u8fd8\u53ef\u4ee5\u5e94\u7528\u4e8e\u4ea4\u901a\u7cfb\u7edf\uff0c\u6bd4\u5982\u706b\u8f66\u8c03\u5ea6\u7684\u4f8b\u5b50\u3002MAPF solution\u53ef\u4ee5\u5728\u51e0\u5206\u949f\u4e4b\u5185\u8c03\u5ea63000\u591a\u4e2a\u706b\u8f66\u5230\u4ed6\u4eec\u7684\u76ee\u7684\u5730\u3002<\/span><\/p>\n


<\/p>\n<\/section>\n

\n

<\/p>\n<\/section>\n

\n


<\/p>\n

\u9664\u706b\u8f66\u8c03\u5ea6\u4ee5\u5916\uff0c\u4e00\u4e2a\u7c7b\u4f3c\u7684\u5e94\u7528\u662f\u98de\u673a\u8c03\u5ea6\uff0c\u8fd9\u662f\u6211\u4e4b\u524d\u548cNASA\u5408\u4f5c\u7684\u9879\u76ee\uff0c\u6211\u4eec\u5982\u4f55\u7528MAPF\u7684\u65b9\u6cd5\u6765\u63a7\u5236\u98de\u673a\u7684\u8d77\u98de\u4e0e\u964d\u843d\u3002\u8fd9\u4e2a\u95ee\u9898\u7684\u96be\u70b9\u5728\u4e8e\uff0c\u98de\u673a\u7684\u63a7\u5236\u5305\u542b\u6709\u5f88\u591a\u4e0d\u786e\u5b9a\u6027\u56e0\u7d20\uff0c\u4f8b\u5982\u5929\u6c14\u5e72\u6270\uff0c\u4eba\u4e3a\u56e0\u7d20\u5e72\u6270\uff0c\u6240\u4ee5\u6211\u4eec\u8981\u628aMAPF\u6a21\u578b\u548c\u968f\u673a\u6a21\u578b\u7ed3\u5408\u8d77\u6765\uff0c\u8003\u8651\u5230\u5404\u79cd\u56e0\u7d20\u5e72\u6270\uff0c\u63a7\u5236\u6574\u4f53\u7684\u8c03\u5ea6\u4e0e\u8fd0\u884c\u3002<\/span><\/p>\n


<\/p>\n<\/section>\n

\n

<\/p>\n<\/section>\n

\n


<\/p>\n

MAPF\u8fd8\u53ef\u4ee5\u88ab\u7528\u5230\u5f88\u591a\u673a\u5668\u4eba\u7cfb\u7edf\u4e2d\uff0c\u6bd4\u5982\u8bf4\u81ea\u52a8\u53c9\u8f66\uff0c\u81ea\u52a8\u505c\u8f66\u7cfb\u7edf\uff0c\u65e0\u4eba\u8f66\u3001\u65e0\u4eba\u673a\u4ee5\u53ca\u4e00\u4e9b\u6c34\u4e0b\u673a\u5668\u4eba\u3002\u5bf9\u8fd9\u4e9b\u7cfb\u7edf\u4e00\u65b9\u9762\u8981\u907f\u514d\u78b0\u649e\uff0c\u53e6\u4e00\u65b9\u9762\u8981\u53bb\u8003\u8651\u5404\u79cd\u673a\u5668\u4eba\u4e0d\u540c\u7684\u52a8\u529b\u5b66\u7ea6\u675f\uff0c\u6bd4\u5982\u8bf4\u901f\u5ea6\u3001\u52a0\u901f\u5ea6\u3001\u8f6c\u89d2\uff0c\u4ee5\u53ca\u5404\u79cd\u5e72\u6270\u7684\u7ea6\u675f\u3002\u5982\u4f55\u628aMAPF\u4e0e\u8fd9\u79cd\u7ea6\u675f\u7ed3\u5408\u8d77\u6765\uff0c\u4e5f\u662f\u4e00\u4e2a\u96be\u70b9\u3002<\/span><\/p>\n


<\/p>\n

\u90a3\u4e48\u603b\u7684\u6765\u8bf4\uff0c\u5176\u5b9eMAPF\u7684\u7814\u7a76\u4e3b\u8981\u6709\u4e24\u5927\u65b9\u5411\uff1a<\/strong><\/span><\/p>\n


<\/strong><\/span><\/p>\n

    \n
  • \n
    \u4e00\u4e2a\u662f\u9488\u5bf9MAPF\u672c\u8eab\u7684\u95ee\u9898\uff0c\u5982\u4f55\u63d0\u9ad8\u73b0\u6709\u7684\u7b97\u6cd5\u6548\u7387\u548c\u89e3\u7684\u8d28\u91cf\u3002<\/span><\/section>\n<\/li>\n
  • \n
    \u7136\u540e\u53e6\u4e00\u4e2a\u662f\u628aMAPF\u5e94\u7528\u5230\u5b9e\u9645\u95ee\u9898\u5f53\u4e2d\u7684\u65f6\u5019\uff0c\u5982\u4f55\u5904\u7406\u4e0d\u540c\u95ee\u9898\u6240\u5e26\u6765\u7684\u4e0d\u540c\u7ea6\u675f\u3002<\/span><\/section>\n<\/li>\n<\/ul>\n


    <\/p>\n<\/section>\n

    \n
    <\/section>\n<\/section>\n
    \n


    <\/p>\n

    \u672c\u6b21AAAI\uff0c\u6211\u4e00\u5171\u67094\u7bc7\u6587\u7ae0<\/strong>\u88ab\u9009\u4e2d\uff0c\u6211\u4f1a\u4f9d\u6b21\u4ecb\u7ecd\u5b83\u4eec\u3002<\/span><\/section>\n

    <\/span><\/section>\n
      \n
    • \n
      \u7b2c\u4e00\u7bc7\u6587\u7ae0<\/span><\/strong>\u662f\u5173\u4e8e\u5982\u4f55\u5229\u7528Heuristic\u65b9\u6cd5\u52a0\u901f\u73b0\u6709\u7684MAPF\u7b97\u6cd5\u3002<\/span><\/section>\n<\/li>\n
    • \n
      \u7b2c\u4e8c\u7bc7\u6587\u7ae0<\/span><\/strong>\u7814\u7a76\u4e86MAPF\u7684\u4e00\u4e2a\u5ef6\u4f38\u95ee\u9898\uff0c\u53ebK-Robust MAPF\uff0c\u5b83\u7684\u903b\u8f91\u5c31\u662f\u5f88\u591a\u60c5\u51b5\u4e0b\u673a\u5668\u4eba\u662f\u4e0d\u4f1a\u4e25\u683c\u7684\u6267\u884c\u6bcf\u4e00\u4e2a\u52a8\u4f5c\uff0c\u53ef\u80fd\u4f1a\u6709\u5ef6\u8fdf\u3002\u6240\u4ee5\u5f53\u6211\u4eec\u8003\u8651\u5230\u6709\u4e00\u5b9a\u5ef6\u8fdf\u7684\u65f6\u5019\uff0c\u6211\u4eec\u4ecd\u7136\u5e0c\u671b\u6700\u7ec8\u7ed9\u7684\u89e3\u4fdd\u8bc1\u6ca1\u6709\u78b0\u649e\u3002\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u8fd9\u4e2a\u95ee\u9898\u4f1a\u5e26\u6765\u5f88\u591a\u7684 Symmetry\u56e0\u7d20\uff0c\u5982\u4f55\u53bb\u6d88\u9664\u8fd9\u4e9b\u56e0\u7d20\uff0c\u5c31\u662f\u8fd9\u7bc7\u6587\u7ae0\u6240\u8981\u89e3\u51b3\u7684\u95ee\u9898\u3002<\/span><\/section>\n<\/li>\n
    • \n
      <\/span><\/section>\n<\/li>\n
    • \n
      \u7b2c\u4e09\u7bc7\u6587\u7ae0<\/span><\/strong>\u5c31\u662f\u521a\u624d\u63d0\u5230\u7684\u4ed3\u50a8\u7cfb\u7edf\uff0c\u5982\u4f55\u53bb\u5e94\u5bf9\u5b9e\u65f6\u7684\u3001\u5927\u89c4\u6a21\u7684\u3001\u4e0d\u65ad\u52a8\u6001\u53d8\u5316\u7684\u4ed3\u50a8\u7cfb\u7edf\uff0c\u7528\u6211\u4eec\u73b0\u6709\u7684MAPF solver\u6765\u89e3\u51b3\u8fd9\u79cdLifelong MAPF\u95ee\u9898\u3002<\/span><\/section>\n<\/li>\n
    • \n
      \u7b2c\u56db\u4e2a<\/span><\/strong>\u4e5f\u662f\u521a\u624d\u63d0\u5230\u7684\uff0c\u8003\u8651\u5230\u673a\u5668\u4eba\u7684\u52a8\u529b\u5b66\u7ea6\u675f\u7684\u65f6\u5019\uff0c\u5982\u4f55\u628a\u5b83\u548cMAPF\u6a21\u578b\u7ed3\u5408\u8d77\u6765\u3002<\/span><\/section>\n<\/li>\n<\/ul>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u8fdb\u4e00\u6b65\u5b9a\u4e49MAPF\uff0c\u5047\u8bbe\u65f6\u95f4\u662f\u79bb\u6563\u5316\u7684\uff0c\u5728\u6bcf\u4e00\u4e2a\u884c\u52a8\u70b9\uff0c\u673a\u5668\u4eba\u53ef\u4ee5\u9009\u62e9\u4e24\u79cd\u52a8\u4f5c\uff0c\u4e00\u79cd\u662f\u79fb\u52a8\u5230\u76f8\u90bb\u7684\u4f4d\u7f6e\uff0c\u4e00\u79cd\u662f\u5728\u5f53\u524d\u4f4d\u7f6e\u7b49\u5f85\uff0c\u4e24\u79cd\u52a8\u4f5c\u53ea\u9700\u8981\u4e00\u4e2a\u884c\u52a8\u70b9\uff0c\u800c\u4e14\u4ed6\u4eec\u7684cost\u4e5f\u662f1\u3002\u78b0\u649e\u88ab\u79f0\u4e3acollisions\u6216\u8005\u662fconflicts\uff0c\u5176\u6709\u4e24\u79cd\u7c7b\u578b\uff0c\u4e00\u4e2a\u53ebvertex conflict\uff0c\u5373\u5728\u4efb\u610f\u65f6\u523b\u5185\uff0c\u6709\u4e24\u4e2aagent\u5728\u540c\u4e00\u65f6\u95f4\u5230\u8fbe\u540c\u4e00\u4f4d\u7f6e\uff1b\u53e6\u4e00\u79cd\u53ebedge conflict\uff0c\u5373\u4e24\u4e2aagent\u5728\u540c\u4e00\u65f6\u95f4\u53bb\u4ea4\u6362\u5f7c\u6b64\u7684\u4f4d\u7f6e\uff0c\u6216\u7ecf\u8fc7\u540c\u4e00\u6761\u8fb9\u3002\u6240\u4ee5\u6211\u4eec\u7684\u4efb\u52a1\u5c31\u662f\u751f\u6210\u6307\u4ee4\uff0c\u4f7f\u673a\u5668\u4eba\u65e2\u80fd\u5230\u8fbe\u76ee\u7684\u5730\uff0c\u4e5f\u4e0d\u4f1a\u53d1\u751f\u78b0\u649e\uff0c\u540c\u65f6\u5177\u6709\u6700\u5c0f\u65c5\u884c\u65f6\u95f4\u548c\u3002<\/strong><\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u8fd9\u91cc\u6709\u4e00\u4e2a\u6bd4\u8f83\u4e3b\u6d41\u4e14\u5177\u6709\u8f83\u597d\u6548\u679c\u7684MAPF\u7b97\u6cd5\u53ebConflict-Based search\u6216\u8005CBS\u3002<\/span><\/strong>\u5b83\u662f\u4e00\u4e2a\u4e24\u5c42\u7684\u7b97\u6cd5\uff0c\u5176\u903b\u8f91\u4e3a\u5047\u8bbe\u4e00\u4e2a\u673a\u5668\u4eba\u60f3\u4eceA2\u5230D3\uff0c\u4e00\u4e2a\u673a\u5668\u4eba\u60f3\u4eceB1\u5230C4\u3002CBS\u6700\u5f00\u59cb\u5148\u7ed9\u6bcf\u4e00\u4e2a\u673a\u5668\u4eba\u89c4\u5212\u4e00\u6761\u6700\u77ed\u8def\uff0c\u5ffd\u7565\u53e6\u4e00\u4e2a\u673a\u5668\u4eba\u6216\u5ffd\u7565\u5176\u4ed6\u673a\u5668\u4eba\u3002\u68c0\u67e5\u5f53\u524d\u7684\u6700\u77ed\u8def\u6709\u6ca1\u6709collisions\uff0c\u7b97\u6cd5\u6839\u636e\u5176\u4e2d\u4e00\u4e2a\u673a\u5668\u4eba\u662f\u5426\u6267\u884c\u5f53\u524d\u6307\u4ee4\u5206\u522b\u751f\u6210\u4e24\u4e2a\u5b50\u6811\u5e76\u4e14\u52a0\u4e00\u4e2a\u989d\u5916\u7684\u7ea6\u675f\u3002\u4e4b\u540e\u5728\u5404\u81ea\u7684\u5b50\u6811\u4e2d\u91cd\u65b0\u89c4\u5212\u8def\u7ebf\uff0c\u5de6\u8fb9\u7ed9agent 2\u91cd\u65b0\u89c4\u5212\u4e00\u6761\u8def\uff0c\u53f3\u8fb9\u7ed9agent 1\u91cd\u65b0\u89c4\u5212\u4e00\u6761\u8def\u3002\u91cd\u590d\u4e4b\u524d\u7684\u8fc7\u7a0b\uff0c\u76f4\u5230\u627e\u5230\u4e00\u4e2a\u8282\u70b9\uff0c\u91cc\u9762\u7684\u8def\u5f84\u6ca1\u6709\u4efb\u4f55collisions\u3002<\/span><\/section>\n
      <\/p>\n
      \n

       <\/span><\/p>\n


      <\/span><\/p>\n<\/section>\n

      <\/span><\/section>\n

      \n
      \n
      \n
      \n
      \n

      <\/section>\n

      <\/section>\n
      \n
      <\/svg><\/section>\n<\/section>\n<\/section>\n
      \n

      \u4e8c\u3001EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding<\/strong><\/strong><\/span><\/p>\n<\/section>\n

      \n

      <\/section>\n

      <\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/h3>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n

      <\/section>\n
      \u7b2c\u4e00\u7bc7\u6211\u4eec\u63d0\u51fa\u4e86\u4e00\u4e2a\u65b0\u7684\u7b97\u6cd5\u53ebEECBS\uff0c\u8fd9\u4e2a\u7b97\u6cd5\u4eceheuristic search\u7684\u89d2\u5ea6\u6765\u5206\u6790\u5982\u4f55\u6765\u52a0\u901fCBS\u3002<\/span><\/strong>heuristic search\u4e2d\u6700\u7ecf\u5178\u7684\u7b97\u6cd5\u5c31\u662fA*\uff0cCBS\u7684\u4e0a\u5c42\u548c\u4e0b\u5c42\u90fd\u4f7f\u7528\u4e86A*\uff0c\u5982\u679c\u60f3\u8ba9\u5176\u8fd0\u7b97\u66f4\u5feb\uff0c\u4e00\u4e2a\u5f88\u5e38\u89c1\u7684\u7b97\u6cd5\u662f\u7528wA*\u3002\u901a\u8fc7\u7ed9h\u4e58\u4e00\u4e2aw\uff0c\u4f7f\u5f97f\u66f4\u504f\u5411\u4e8eh\u7684\u503c\uff0c\u8fd9\u6837\u53ef\u4ee5\u66f4\u5feb\u627e\u5230\u89e3\uff0c\u5e76\u4e14\u89e3\u5728\u6700\u574f\u60c5\u51b5\u4e0b\u4e0d\u8d85\u8fc7w\u500d\u6700\u4f18\u89e3\u3002\u4f46\u662f\u5176\u8868\u73b0\u4f1a\u6bd4CBS\u66f4\u5dee\u3002\u8fd9\u662f\u56e0\u4e3a\u5728CBS\u4e2d\uff0ch\u7684\u503c\u6ca1\u6709\u8003\u8651\u4e2d\u9014\u53ef\u80fd\u5305\u542b\u7684\u78b0\u649e\u4fe1\u606f\u3002\u4e8e\u662f\u57281982\u5e74\u6709\u4eba\u63d0\u51fa\u7b97\u6cd5\u6765\u89e3\u51b3\u8fd9\u79cd\u95ee\u9898\u3002A*\u03b5\u91cc\u6709\u4e24\u4e2aheurisitic\uff0c\u4e00\u4e2a\u662f\u4f20\u7edf\u7684A*\u4f1a\u7528\u5230\u7684admissible cost heuristic\uff0c\u7136\u540e\u53e6\u4e00\u4e2a\u662fdistance to go heuristic d\u3002\u8fd9\u4e2ad\u8868\u793a\u5f53\u524d\u8282\u70b9\u5230goal node\u8fd8\u9700\u8981\u5c55\u5f00\u591a\u5c11\u4e2a\u8282\u70b9\uff0cheuristic\u7528\u4e8e\u4f30\u8ba1\u8fd9\u4e2a\u4e8b\u60c5\u3002\u5f53\u4eba\u4eec\u628a\u653e\u5230CBS\u6846\u67b6\u4e2d\u66ff\u6362A*\u4e4b\u540e\uff0c\u53d1\u660e\u4e86\u7b97\u6cd5ECBS\uff0c\u5b83\u662f\u76ee\u524d\u6700\u597d\u7684bounded suboptimal MAPF solver\u3002<\/span><\/section>\n


      <\/p>\n

      ECBS\u901a\u8fc7\u4e00\u4e2aopen list\u5b58\u5165\u6240\u6709\u7684\u8282\u70b9\uff0c\u5e76\u4e14\u6309\u7167f\u7684\u503c\u53bb\u6392\u5217\u3002\u6700\u5c0f\u7684\u53ebf min\uff0c\u5176\u662f\u6700\u4f18\u89e3\u7684\u4e00\u4e2alower bound\u3002\u800cbounded suboptimal\u7684\u8981\u6c42\u53ea\u9700\u8981\u6700\u7ec8\u89e3\u7684cost\u6bd4wf min\u5c0f\u3002\u6240\u4ee5ECBS\u7528d\u5728\u6a59\u8272\u533a\u57df\u5185\u9009\u62e9\u5408\u9002\u7684node\u4f5c\u4e3a\u89e3\u3002\u4f46\u662f\u5b9e\u9645\u4e2d\u4f1a\u6709\u4e24\u4e2a\u7f3a\u9677\uff0c\u7b2c\u4e00\u4e2a\u662f\u56e0\u4e3af min\u57fa\u672c\u4e0d\u4f1a\u53d8\uff0c\u4e5f\u5c31\u610f\u5473\u7740\u6a59\u8272\u533a\u57df\u6ca1\u6709\u89e3\u7684\u60c5\u51b5\u4e0b\u4e5f\u4e0d\u4f1a\u53d1\u751f\u53d8\u5316\uff0c\u7b2c\u4e8c\u4e2a\u662f\u83b7\u5f97\u7684\u89e3\u4f1a\u6bd4\u771f\u5b9e\u89e3\u5927\u3002<\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u4e3a\u4e86\u89e3\u51b3\u4e0a\u8ff0\u7684\u5f0a\u7aef\uff0c\u6211\u4eec\u63d0\u51fa\u4e86explicit estimation CBS\uff0cEECBS\u3002<\/span><\/strong>\u8fd9\u4e2a\u7b97\u6cd5\u4e2d\u5305\u542b\u4e86explicit estimation search\u548c\u4e09\u4e2aheuristic\u3002\u7b2c\u4e00\u4e2a\u662fA*\u4e2d\u7684h\uff0c\u7b2c2\u4e2a\u4e2d\u7684distance-to-go d\uff0c\u7b2c\u4e09\u4e2a\u662fcost-to-go heuristic h\u2019\u3002\u7b2c\u4e09\u4e2ah\u2019\u7528\u4e8e\u4f30\u8ba1cost\u7684\u589e\u52a0\u91cf\uff0c\u5e76\u4e14\u4e0d\u9700\u8981admissible\uff0c\u6bd4h\u7684\u51c6\u786e\u5ea6\u66f4\u9ad8\u3002<\/span><\/section>\n


      <\/p>\n

       1. \u7b2c\u4e00\u4e2aheuristic\u5c06\u95ee\u9898\u8f6c\u6362\u4e3avertex cover\uff0c\u7136\u540e\u6c42\u89e3\u3002<\/span><\/section>\n
       2. \u7b2c\u4e8c\u4e2aheuristic\u8ba1\u7b97collisions\u7684\u4e2a\u6570\u3002<\/span><\/section>\n
       3. \u7b2c\u4e09\u4e2a\u662fonline learning\u65b9\u6cd5\uff0c\u5728\u641c\u7d22\u8fc7\u7a0b\u4e2d\u89c2\u5bdf\u524d\u9762h\u548cd\u7684\u8bef\u5dee\uff0c\u7136\u540e\u53cd\u9988\u77eb\u6b63\u5f97\u5230\u66f4\u7cbe\u786e\u7684h\u2019\u7684\u9884\u4f30\u8ba1\u3002<\/span><\/section>\n
       4. \u7ed3\u5408\u4e09\u4e2aheuristic\u5c31\u53ef\u4ee5\u514b\u670d\u4e4b\u524dECBS\u63d0\u5230\u4e24\u4e2a\u7f3a\u9677\u3002<\/span><\/section>\n
       5. \u6b64\u5916\uff0c\u6211\u4eec\u5728EECBS\u4e2d\u589e\u52a0\u4e86\u8fd1\u5e74\u6765\u4e00\u4e9b\u65b0\u7684CBS improvements\u3002<\/span><\/section>\n


      <\/p>\n

      \u901a\u8fc7\u5b9e\u9a8c\u5bf9\u6bd4\uff0cCBS\u6700\u591a\u80fd\u89e3\u51b3\u7684agent\u4e2a\u6570\u5c0f\u4e8e200\uff0c\u800cEECBS\u53ef\u4ee5\u8fbe\u52301000\u4e2a\u4ee5\u4e0a\uff0c\u800c\u89e3\u7684\u8d28\u91cf\u4e0e\u6700\u4f18\u89e3\u53ea\u67092%\u7684\u8bef\u5dee\u3002<\/span><\/section>\n
      <\/p>\n
      \n


      <\/p>\n

       <\/span><\/p>\n<\/section>\n

      <\/span><\/section>\n

      \n
      \n
      \n
      \n
      \n

      <\/section>\n

      <\/section>\n
      \n
      <\/svg><\/section>\n<\/section>\n<\/section>\n
      \n

      \u4e09\u3001Symmetry Breaking for k-Robust Multi-Agent Path Finding<\/strong><\/strong><\/span><\/p>\n<\/section>\n

      \n

      <\/section>\n

      <\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/h3>\n<\/section>\n
      \n
      \n
      \n
      \n

      <\/section>\n
      \u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span>\u200d<\/span><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n
      \n

      <\/section>\n
      \u7b2c\u4e8c\u4e2a\u5de5\u4f5c\u5173\u4e8e\u5bf9\u79f0\u6027\u4ee5\u53caK-robust MAPF\u3002<\/span><\/strong>\u89c2\u5bdf\u4e0a\u56fe\u53d1\u73b0\u6bcf\u4e00\u4e2a\u673a\u5668\u4eba\u53ef\u4ee5\u6709\u591a\u6761\u4e0d\u540c\u7684\u8def\u5f84\u3002\u4f46\u662f\u4efb\u610f\u4e00\u6761\u8def\u5f84\u5728\u9ec4\u8272\u533a\u57df\u90fd\u6709\u4ea4\u96c6\uff0c\u8fd9\u88ab\u79f0\u4e3asymmetry\u3002\u53f3\u56fe\u4e2d\uff0c\u6a2a\u5750\u6807\u4ee3\u8868\u9ec4\u8272\u533a\u57df\u7684\u9762\u79ef\uff0c\u7eb5\u5750\u6807\u4ee3\u8868\u89e3\u51b3\u76f8\u649e\u95ee\u9898\u65f6CBS\u7684\u8282\u70b9\u4e2a\u6570\uff0c\u56fe\u50cf\u663e\u793a\u968f\u7740\u9762\u79ef\u589e\u52a0\uff0c\u8282\u70b9\u4e2a\u6570\u6307\u6570\u589e\u5927\uff0c\u5c24\u5176\u8d85\u8fc78\u00d78\u540e\u8d8b\u4e8e\u4e0d\u73b0\u5b9e\u3002<\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u56e0\u4e3a\u673a\u5668\u4eba\u4e0d\u80fd\u591f\u7cbe\u51c6\u7684\u4ee5\u9884\u5b9a\u901f\u5ea6\u6267\u884c\u547d\u4ee4\uff0c\u6240\u4ee5\u9700\u8981k-robust MAPF\u5236\u5b9a\u8ba1\u5212\uff0c\u5373\u5bf9\u4e8e\u4efb\u610f\u6570\u91cf\u7684agent\uff0c\u5ef6\u8fdf\u4e0d\u8d85\u8fc7k\u4e2a\u65f6\u95f4\u5355\u4f4d\uff0c\u4ecd\u7136\u53ef\u4ee5\u4fdd\u8bc1\u4e0d\u76f8\u649e\uff0c\u5728\u5de6\u56fe\u4e2d\u8868\u73b0\u4e3a\u540e\u9762\u7684\u5c3e\u5df4\u3002\u4f46\u662f\u8fd9\u6837\u4e5f\u9020\u6210\u4e86\u66f4\u591a\u7684\u5bf9\u79f0\u6027\u7f3a\u70b9\uff0c\u4e2d\u95f4\u56fe\u4e2d\u662f\u9ec4\u8272\u9762\u79ef\u56fe\u7684\u5ef6\u4f38\uff0c\u53ef\u4ee5\u770b\u5230\u968f\u7740k\u7684\u589e\u52a0\uff0cCBS\u9700\u8981\u7684\u8282\u70b9\u6570\u4e5f\u5728\u589e\u52a0\u3002\u800c\u53f3\u56fe\u663e\u793a\u7684\u662f\u968f\u7740k\u589e\u52a0\uff0crectangle symmetry\u51fa\u73b0\u7684\u9891\u7387\u4e5f\u5728\u589e\u52a0\uff0c\u4f1a\u4e25\u91cd\u5f71\u54cdCBS\u6548\u7387\u3002<\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u4e3a\u4e86\u89e3\u51b3\u4e0a\u8ff0\u95ee\u9898\uff0c\u6211\u4eec\u91c7\u7528\u4e86\u4e00\u79cd\u540d\u4e3asymmetry-breaking constraints\u7684\u60f3\u6cd5\uff0c<\/span><\/strong>\u5176\u8fd0\u7b97\u903b\u8f91\u662f\u901a\u8fc7\u8bbe\u8ba1constraint\u6765\u6d88\u9664symmetry\uff0c\u4ece\u800c\u7f29\u5c0f\u641c\u7d22\u7a7a\u95f4\uff0c\u52a0\u901f\u7b97\u6cd5\u3002\u5e94\u7528\u4e8eCBS\u4e2d\uff0c\u5f53\u51fa\u73b0\u4e00\u4e2asymmetry\u65f6\uff0c\u5c31\u5b50\u6811\u6dfb\u52a0\u591a\u4e2aconstraints\uff0c\u4ece\u800c\u6d88\u9664\u6f5c\u5728\u7684collision\u3002\u800cconstraint\u7684\u8bbe\u8ba1\u8981\u9075\u5faa\u4e24\u4e2a\u539f\u5219\uff0c\u7b2c\u4e00\u4e2a\u662f\u5c3d\u53ef\u80fd\u591a\u7684\u6d88\u9664collision\uff0c\u7b2c\u4e8c\u4e2a\u662f\u5c3d\u53ef\u80fd\u4fdd\u7559\u6f5c\u5728\u7684\u89e3\u3002<\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u672c\u7bc7\u6587\u7ae0\u7684\u6838\u5fc3\u662f\u5982\u4f55\u8bbe\u8ba1constraints\uff0c\u4e3b\u8981\u4ece\u4e09\u7c7bsymmetry\u5165\u624b\uff1a<\/span><\/strong><\/span><\/section>\n


      <\/p>\n

       1. \u7b2c\u4e00\u4e2a\u662frectangle\u3002<\/span><\/section>\n
       2. \u7b2c\u4e8c\u4e2acorridor symmetry\uff0c\u5b83\u9700\u8981\u89e3\u51b3\u4e24\u4e2a\u673a\u5668\u4eba\u5982\u4f55\u4ece\u4e0d\u540c\u65b9\u5411\u7ecf\u8fc7\u4e00\u4e2a\u72ed\u7a84\u7684\u8fc7\u9053\u3002<\/span><\/section>\n
       3. \u7b2c\u4e09\u4e2atarget symmetry\uff0c\u5b83\u9762\u5bf9\u7684\u662f\u4e00\u4e2aagent\u5df2\u7ecf\u5230\u4e86\u5b83\u7684\u76ee\u7684\u5730\u5e76\u4e14\u505c\u6b62\u8fd0\u52a8\uff0c\u53e6\u4e00\u4e2aagent\u5982\u4f55\u8d8a\u8fc7\u5b83\u3002<\/span><\/section>\n

      <\/span><\/section>\n
      \u6211\u4eec\u5728\u591a\u79cd\u5730\u56fe\u7684\u60c5\u51b5\u4e0b\u8fdb\u884c\u4e86\u6d4b\u8bd5\uff0c\u4f8b\u5982\u968f\u673a\u751f\u6210\u5730\u56fe\u3001\u6e38\u620f\u5730\u56fe\u3001\u4ed3\u5e93\u548c\u706b\u8f66\u7f51\u7edc\uff0c\u672c\u6587\u7684\u65b9\u6cd5\u5bf9CBS\u6709\u7740\u663e\u8457\u7684\u63d0\u9ad8\uff0c\u5bf9\u6bd4\u4e4b\u524d\u53ef\u4ee5\u5bf9\u591a\u4e00\u500d\u7684\u6570\u91cf\u6c42\u89e3\u3002<\/span><\/section>\n
      <\/p>\n
      \n

       <\/span><\/p>\n


      <\/span><\/p>\n<\/section>\n

      <\/span><\/section>\n

      \n
      \n
      \n
      \n
      \n

      <\/section>\n

      <\/section>\n
      \n
      <\/svg><\/section>\n<\/section>\n<\/section>\n
      \n

      \u56db\u3001Lifelong Multi-Agent Path Finding in Large-Scale Warehouses<\/strong><\/strong><\/span><\/p>\n<\/section>\n

      \n

      <\/section>\n

      <\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/h3>\n


      <\/p>\n<\/section>\n

      \n
      \n
      \n
      \n
      \u7b2c\u4e09\u4e2a\u662f\u5728\u4e9a\u9a6c\u900a\u5b9e\u4e60\u662f\u5b8c\u6210\u7684\uff0c\u79f0\u4e3aLifelong MAPF<\/span><\/strong>\uff0c\u610f\u56fe\u89e3\u51b3\u673a\u5668\u4eba\u5728\u5230\u8fbe\u76ee\u7684\u5730\u540e\u7acb\u5373\u83b7\u5f97\u65b0\u4efb\u52a1\u7684\u5b9e\u65f6\u52a8\u6001\u7cfb\u7edf\u3002<\/span><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n
      \n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u76ee\u524d\u6709\u4e09\u79cd\u65b9\u6cd5\uff1a<\/span><\/section>\n


      <\/p>\n

       1. \u7b2c\u4e00\u79cd\u4ece\u4e00\u4e2a\u89e3\u51b3\u65b0\u95ee\u9898\u7684\u89d2\u5ea6\u6765\u601d\u8003\uff0c\u4f46\u662f\u8fd9\u79cd\u7b97\u6cd5\u901f\u5ea6\u6781\u6162\uff0c\u56fe\u4e2d\u7684\u6587\u7ae0\u53ea\u80fd\u89e3\u51b320\u4e2aagent\u3002\u800c\u4e14\u8fd8\u9700\u8981\u77e5\u9053\u6240\u6709\u7684goal location\uff0c\u8fd9\u5bf9\u4e8e\u4ed3\u50a8\u7cfb\u7edf\u4e0d\u73b0\u5b9e\u3002<\/span><\/section>\n


      <\/p>\n

       2. \u7b2c\u4e8c\u79cd\u662f\u5728\u6bcf\u4e2a\u884c\u52a8\u70b9\u591a\u8fd0\u884c\u4e00\u6b21MAPF solver\uff0c\u8fd9\u4e2a\u65b9\u6cd5\u867d\u7136\u53ea\u5173\u5fc3\u8d77\u59cb\u70b9\uff0c\u4f46\u662f\u9700\u8981\u83b7\u5f97\u65b0\u4efb\u52a1\u540e\u91cd\u65b0\u8ba1\u7b97\uff0c\u9020\u6210\u91cd\u590d\u6027\u5de5\u4f5c\u3002\u6b64\u5916\u5b9e\u9645\u7cfb\u7edf\u4e2d\uff0c\u673a\u5668\u4eba\u4e0d\u4f1a\u5728\u6bcf\u4e2atime step\u4e2d\u7b49\u5f85\u7cfb\u7edf\u91cd\u65b0\u5236\u5b9a\u8ba1\u5212\u3002<\/span><\/section>\n


      <\/p>\n

       3. \u7b2c\u4e09\u79cd\u662f\u53ea\u9488\u5bf9\u6709\u65b0\u4efb\u52a1\u7684\u673a\u5668\u4eba\u505a\u8def\u5f84\u89c4\u5212\uff0c\u673a\u5668\u4eba\u4e25\u683c\u6267\u884c\u8fd9\u4e2a\u8ba1\u5212\uff0c\u5e76\u4e14\u4e0d\u4f1a\u8fdb\u884c\u6539\u53d8\u3002\u8fd9\u4e2a\u65b9\u6cd5\u7684\u7f3a\u70b9\u662f\u89e3\u7684\u8d28\u91cf\u5dee\uff0c\u4e14\u4f1a\u51fa\u73b0\u62e5\u5835\uff0c\u800c\u4e14\u56e0\u4e3a\u53ea\u6d89\u53ca\u4e00\u90e8\u5206agent\uff0c\u6240\u4ee5\u4f1a\u51fa\u73b0\u65e0\u89e3\u7684\u60c5\u51b5\uff0c\u53ea\u80fd\u4f7f\u7528\u4e8e\u67d0\u4e00\u7c7b\u5730\u56fe\uff0c\u800c\u4e14\u5b83\u540c\u6837\u8981\u6c42\u6bcf\u4e2a\u884c\u52a8\u70b9\u8fdb\u884creplan\u3002<\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u672c\u6587\u63d0\u4f9b\u4e86\u4e00\u4e2a\u65b0\u7684\u601d\u8def\u6765\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\uff0c\u79f0\u4e3aRolling-Horizon Collision Resolution\u3002<\/span><\/strong>\u8fd9\u4e2a\u7b97\u6cd5\u9996\u5148\u7531\u7528\u6237\u63d0\u4f9b\u53c2\u6570h\uff0c\u4e4b\u540e\u6bcfh timestep\u90fd\u8fdb\u884creplan\u3002\u56e0\u4e3a\u7cfb\u7edf\u662f\u5728\u52a8\u6001\u53d8\u5316\u7684\uff0c\u6240\u4ee5\u6211\u4eec\u5728\u5f53\u524dreplan\u53ea\u5904\u7406\u5f53\u524d\u7684collision\uff0c\u5373\u5728\u6bcfh timesteps\u53bb\u5904\u7406\u4e00\u4e2awindowed MAPF instance\u3002\u4e4b\u6240\u4ee5\u53ebwindowed MAPF\u57fa\u4e8e\u4e24\u70b9\uff0c\u7b2c\u4e00\u70b9\u662f\u524dw\u4e2a\u884c\u52a8\u70b9\u7684collision\uff0c\u5176\u4e2dw\u5927\u4e8e\u7b49\u4e8eh\uff1b\u7b2c\u4e8c\u70b9\u662f\u4e00\u4e2aagent\u53ef\u80fd\u4f1a\u6709\u591a\u4e2a\u76ee\u7684\u5730\uff0c\u4e3a\u7684\u662f\u5728h timestep\u4e4b\u524d\u80fd\u591f\u4fdd\u6301\u6301\u7eed\u884c\u52a8\u3002\u4e0a\u56fe\u662f\u4e00\u4e2a\u5927\u6982\u7684\u5c55\u793a\uff0c\u6a2a\u8f74\u4e3a\u65f6\u95f4\uff0c\u57280\u7684\u65f6\u523b\uff0c\u7ed9\u6240\u6709agent\u5b8c\u6574\u7684plan\uff0c\u4f46\u662f\u53ea\u5904\u7406\u524dw\u6b65\u7684collision\uff0c\u5230\u7b2ch\u4e2atimestep\u65f6\uff0c\u91cd\u590d\u4e0a\u8ff0\u6b65\u9aa4\u3002<\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u5bf9\u4e8e\u8fd9\u4e2a\u7b97\u6cd5\uff0c\u4e00\u5171\u8fdb\u884c\u4e86\u4e24\u7ec4\u5bf9\u6bd4\u5b9e\u9a8c\uff0c\u7b2c\u4e00\u7ec4\u662f\u548c\u4e4b\u524d\u7684\u65b9\u6cd5\u4e09\u505a\u5bf9\u6bd4\u3002\u53ef\u4ee5\u770b\u5230\u8d28\u91cf\u8981\u6bd4\u65b9\u6cd5\u4e09\u597d\uff0c\u4f46\u662f\u65f6\u95f4\u5728\u4e0d\u8003\u8651\u89e3\u7684\u8d28\u91cf\u65f6\u8981\u7565\u900a\u8272\u4e8e\u65b9\u6cd5\u4e09\u3002\u6240\u6709\u5bf9\u4e8e\u9002\u5408\u7684\u5730\u56fe\uff0c\u5e76\u4e14\u5355\u7eaf\u8ffd\u6c42\u901f\u5ea6\u7684\u8bdd\u53ef\u4ee5\u4f7f\u7528\u65b9\u6cd5\u4e09\uff0c\u4f46\u662f\u8ffd\u6c42\u8d28\u91cf\u7684\u8bdd\uff0c\u672c\u6587\u7684\u65b9\u6cd5\u66f4\u5408\u9002\u3002<\/span><\/section>\n


      <\/p>\n<\/section>\n

      \n
      <\/section>\n<\/section>\n
      \n


      <\/p>\n

      \u7b2c\u4e8c\u4e2a\u5b9e\u9a8c\u9009\u62e9\u4e86\u65b9\u6cd5\u4e09\u4e0d\u9002\u7528\u7684\u5730\u56fe\uff0c\u5728\u6b64\u57fa\u7840\u4e0a\u4f7f\u7528\u4e86\u4e0d\u540c\u7684w\u5927\u5c0f\uff0c\u89c2\u5bdf\u5bf9\u89e3\u7684\u8d28\u91cf\u7684\u5f71\u54cd\u3002\u9996\u5148\u89c2\u5bdf\u541e\u5410\u91cf\uff0c\u968f\u7740w\u7684\u589e\u52a0\uff0c\u541e\u5410\u91cf\u53d8\u5316\u4e0d\u5927\uff0c\u8fd9\u662f\u56e0\u4e3a\u53ea\u5904\u7406\u773c\u524d\u7684collision\u800c\u4e0d\u662f\u6240\u6709\u4e4b\u540e\u53ef\u80fd\u53d1\u751f\u7684collision\u3002\u53e6\u4e00\u65b9\u9762\uff0c\u7b97\u6cd5\u7684\u901f\u5ea6\u968f\u7740w\u7684\u589e\u52a0\u4f1a\u51cf\u6162\uff0c\u800c\u4e14\u8fd8\u6d89\u53ca\u4e86\u80fd\u591f\u5904\u7406agent\u7684\u6570\u91cf\uff0c\u4f8b\u5982\u5f53w\u8d8b\u4e8e\u65e0\u7a77\uff0c\u80fd\u89e3700\u4e2aagent\uff0c\u800cw\u4e3a5\u621610\u5c31\u53ef\u4ee5\u89e31000\u4e2a\u4ee5\u4e0a\u7684agent\u3002<\/span><\/section>\n


      <\/p>\n

      \u8fd9\u4e2a\u65b9\u6cd5\u67094\u4e2a\u4f18\u70b9\uff1a<\/span><\/section>\n
        \n
      • \n
        \u5b83\u9002\u7528\u4e8e\u4efb\u4f55\u5730\u56fe<\/span><\/section>\n<\/li>\n
      • \n
        \u6211\u4eec\u4e0d\u9700\u8981\u6bcf\u4e2a\u65f6\u523b\u90fd\u53bbreplan\uff0c\u800c\u662f\u7531\u7528\u6237\u51b3\u5b9a\u5176\u9891\u7387<\/span><\/section>\n<\/li>\n
      • \n
        \u6709\u4e86W\u4e4b\u540e\uff0c\u7b97\u6cd5\u901f\u5ea6\u63d0\u5347\u660e\u663e<\/span><\/section>\n<\/li>\n
      • \n
        \u5728\u63d0\u5347\u901f\u5ea6\u7684\u540c\u65f6\u80fd\u591f\u4fdd\u8bc1\u89e3\u7684\u8d28\u91cf<\/span><\/section>\n<\/li>\n<\/ul>\n<\/section>\n
        \n
        \n
        \n
        \n

        <\/section>\n
        <\/p>\n
        \n

         <\/span><\/p>\n<\/section>\n

        <\/span><\/section>\n

        \n
        \n
        \n
        \n
        \n

        <\/section>\n

        <\/section>\n
        \n
        <\/svg><\/section>\n<\/section>\n<\/section>\n
        \n

        \u4e94\u3001Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances<\/strong><\/strong><\/span><\/p>\n<\/section>\n

        \n

        <\/section>\n

        <\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/h3>\n


        <\/p>\n


        <\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n
        \n

        <\/section>\n
        \u6700\u540e\u4e00\u7bc7\u6587\u7ae0\u662f\u5982\u4f55\u5c06MAPF\u548c\u673a\u5668\u4eba\u7684\u5404\u79cdconstraint\u7ed3\u5408\uff0c\u79f0\u4e3amulti-robot motion planning\u3002<\/span><\/strong>\u8fd9\u91cc\u6709\u4e00\u4e2a\u6bd4\u8f83\u5178\u578b\u7684\u4e8c\u8f6e\u8f66\u6a21\u578b\uff0c\u6211\u4eec\u4f1a\u83b7\u5f97\u673a\u5668\u4eba\u6240\u5728\u4f4d\u7f6e\u7684x\u3001y\uff0c\u4ee5\u53ca\u65b9\u5411\u03b8\uff0c\u901f\u5ea6\u548c\u8f6c\u901f\u3002\u8f93\u5165\u662f\u4e24\u4e2acontrol input\uff0c\u4e00\u4e2a\u662f\u529b\uff0c\u4e00\u4e2a\u662f\u529b\u77e9\u3002\u56e0\u4e3a\u8003\u8651\u5230\u673a\u5668\u4eba\u4e0d\u4f1a\u7cbe\u786e\u6267\u884c\u6bcf\u4e00\u4e2a\u52a8\u4f5c\uff0c\u9762\u4e34\u975e\u7ebf\u6027\uff0cnonholonomic\uff0chigh-dimension dynamics\uff0c\u4ee5\u53ca\u5916\u754c\u5e72\u6270\u7684\u60c5\u51b5\uff0c\u6240\u4ee5\u6210\u4e3a\u4e00\u4e2a\u79bb\u6563\u7a7a\u95f4\u548c\u79bb\u6563\u65f6\u95f4\u7684\u95ee\u9898\u3002<\/span><\/section>\n


        <\/p>\n<\/section>\n

        \n
        <\/section>\n<\/section>\n
        \n


        <\/p>\n

        \u91cd\u65b0\u601d\u8003MAPF\u7b97\u6cd5\uff0c\u5176\u672c\u8d28\u5c31\u662f\u8003\u8651\u5f88\u591a\u8def\u5f84\u4f1a\u4e0d\u4f1a\u6709\u76f8\u649e\u60c5\u51b5\uff0c\u5982\u679c\u6709\u5c31\u5904\u7406\u5176\u4e2d\u7684conflict\u3002<\/span><\/strong>\u800c\u8fd9\u91cc\u6211\u4eec\u6ca1\u6709\u91c7\u7528CBS\uff0c\u56e0\u4e3a\u5176\u5bf9\u4e8e\u8fde\u7eed\u65f6\u95f4\u4e2d\uff0c\u53d6\u4e00\u4e2a\u70b9\uff0c\u4f1a\u4f7f\u5f97constraint\u6ca1\u6709\u610f\u4e49\uff0c\u56e0\u4e3a\u5176\u9700\u8981\u4e00\u4e2a\u4f4d\u7f6e\u548c\u4e00\u4e2atimestep\u3002\u6240\u4ee5\u6211\u4eec\u91c7\u7528\u4e86priority-based search\uff0c\u5373PBS\uff0c\u5176\u4e0eCBS\u7684\u533a\u522b\u5728\u4e8e\uff0c\u5f53\u6211\u4eec\u8981\u5904\u7406\u4e00\u4e2aconflict\u7684\u65f6\u5019\uff0c\u5b83\u7ed9\u4e24\u4e2a\u673a\u5668\u4eba\u7684\u5176\u4e2d\u4e00\u4e2a\u6307\u6d3e\u4e00\u4e2a\u66f4\u9ad8\u4f18\u5148\u7ea7\uff0c\u4f18\u5148\u7ea7\u4f4e\u7684\u90a3\u4e2a agent\u5c31\u8981\u53bb\u907f\u514d\u548c\u4f18\u5148\u7ea7\u9ad8\u7684\u90a3\u4e2aagent\u53bb\u649e\u3002\u5de6\u56fe\u5c31\u662fagent 1\u4f18\u5148\u7ea7\u9ad8\u4e8eagent 2\uff0c\u6240\u4ee5\u8981\u7ed9agent 2\u91cd\u65b0\u89c4\u5212\u8def\u5f84\u3002\u8fd9\u6837\u5bf9\u4e8ecollision\u7684\u95ee\u9898\u5c31\u8fce\u5203\u800c\u89e3\uff0c\u63a5\u4e0b\u6765\u5c31\u662f\u5728\u4e0d\u65ad\u7684plan\u548creplan\u7684\u60c5\u51b5\u4e0b\uff0c\u5982\u4f55\u4f7f\u5f97\u7b97\u6cd5\u8fd0\u884c\u5feb\u3002<\/span><\/section>\n


        <\/p>\n<\/section>\n

        \n
        <\/section>\n<\/section>\n
        \n


        <\/p>\n

        \u6211\u4eec\u5c06piecewise linear path\u4f5c\u4e3a\u4ecb\u8d28\uff0c\u79f0\u4e3aPWL path\u3002\u5b83\u5c06\u4e00\u4e2a\u65f6\u95f4\u70b9\u548c\u4f4d\u7f6e\uff0c\u5373x\uff0ct\u7ec4\u5408\u6210\u4e00\u4e2a\u5faepoint\uff0c\u4e24\u4e2a\u5faepoint\u4e4b\u95f4\u901a\u8fc7\u76f4\u7ebf\u6bb5\u8fde\u63a5\u3002\u5728\u673a\u5668\u4eba\u5b9e\u9645\u6267\u884c\u8fc7\u7a0b\u4e2d\uff0c\u6211\u4eec\u7528tracking controller\u4f5c\u4e3a\u8ddf\u8e2a\u5668\uff0c\u8ba9\u673a\u5668\u4eba\u8ddf\u968f\u8fd9\u6761\u8def\u5f84\u3002\u800c\u673a\u5668\u4eba\u4f1a\u6709\u8bef\u5dee\uff0c\u6240\u4ee5\u6211\u4eec\u505a\u4e86reachability envelop\u53bb\u5206\u6790\uff0c\u4f8b\u5982\u76f4\u7ebf\u60c5\u51b5\u4e0b\uff0c\u673a\u5668\u4eba\u7684\u504f\u79bb\u8bef\u5dee\uff0c\u5373maximum tracking error\uff0c\u4ee5\u53ca\u6700\u574f\u60c5\u51b5\u4e0b\uff0c\u5b83\u81f3\u5c11\u9700\u8981\u82b1\u591a\u4e45\u65f6\u95f4\uff0c\u4ece\u4e00\u4e2a\u70b9\u79fb\u5230\u53e6\u4e00\u4e2a\u70b9\uff0cminimum tracking duration\u3002\u8ba1\u7b97\u51fa\u8fd9\u4e24\u4e2a\u8bef\u5dee\u7684bound\u4e4b\u540e\uff0c\u901a\u8fc7MAPF solver\u83b7\u5f97\u6700\u7ec8\u89e3\u3002<\/span><\/section>\n


        <\/p>\n<\/section>\n

        \n
        <\/section>\n<\/section>\n
        \n


        <\/p>\n

        \u8fd9\u91cc\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u5982\u679c\u6709\u4e24\u4e2a\u673a\u5668\u4eba\uff0c\u8981\u901a\u8fc7\u4e2d\u95f4\u7684\u8fc7\u9053\u3002<\/span><\/section>\n


        <\/p>\n

        \u7b2c\u4e00\u6b65<\/span><\/strong>\u5148\u83b7\u5f97maximum tracking error\uff0c\u589e\u5927o1,o2\u969c\u788d\u7269\u9762\u79ef\uff0c\u4ece\u800c\u4fdd\u8bc1\u53ea\u8981\u673a\u5668\u4eba\u7684piecewise linear path\u5728\u767d\u8272\u533a\u57df\uff0c\u90a3\u4e48\u5c31\u4e0d\u4f1a\u4e0e\u969c\u788d\u7269\u76f8\u649e\u3002<\/span><\/section>\n


        <\/p>\n

        \u7b2c\u4e8c\u6b65<\/span><\/strong>\u7ed9\u6bcf\u4e2a\u673a\u5668\u4eba\u627e\u4e00\u6761piecewise linear path\uff0c\u901a\u8fc7PBS\u903b\u8f91\u68c0\u67e5\u662f\u5426\u4f1a\u76f8\u649e\u3002\u5f53\u524d\u60c5\u51b5\u4e0b\u4f1a\u76f8\u649e\uff0c\u4e8e\u662f\u8d4b\u4e88\u673a\u5668\u4eba1\u66f4\u9ad8\u7684\u4f18\u5148\u7ea7\uff0c\u5bf9\u4e8e\u673a\u5668\u4eba2\u6765\u8bf4\uff0c\u673a\u5668\u4eba1\u5c31\u662f\u79fb\u52a8\u7684\u969c\u788d\u7269\u3002\u540c\u65f6\u8003\u8651\u5230\u5176\u8986\u76d6\u9762\u79ef\uff0c\u7f16\u7801\u65f6\u901a\u8fc7\u8fd9\u4e9b\u7ea6\u675f\u5c31\u83b7\u5f97\u53e6\u4e00\u6761\u89c4\u5212\u8def\u5f84\u3002\u4e4b\u540e\u901a\u8fc7tracking controller\uff0c\u4f7f\u5f97\u673a\u5668\u4eba\u8ddf\u968f\u4e24\u6761\u8def\u5f84\uff0c\u5c31\u53ef\u4ee5\u4fdd\u8bc1\u4e0d\u76f8\u649e\u7684\u60c5\u51b5\u4e0b\u5230\u8fbe\u76ee\u7684\u5730\u3002<\/span><\/section>\n


        <\/p>\n<\/section>\n

        \n
        <\/section>\n<\/section>\n
        \n


        <\/p>\n

        \u4e0a\u56fe\u662f\u7b97\u6cd5\u7684\u6846\u67b6\u56fe\uff0c\u79f0\u4e3aS2M2\uff0c\u5b83\u5305\u542b\u4e86\u4e09\u90e8\u5206\uff1a<\/span><\/section>\n