本发明涉及一种路径规划系统、路径规划方法、路线图构建装置、模型生成装置及模型生成方法。
背景技术：
1、存在对多个主体(agent)分别向目的地移动的路径进行规划的多主体的路径规划问题。主体例如是自主移动的移动体(例如搬送机器人、清扫机器人、自动驾驶车辆、无人驾驶飞机等)、人、人所操作的装置、操纵器(manipulator)等。以往，多主体的路径规划问题是在预先规定的栅格图(grid map)(栅格空间)上求解。例如，非专利文献1中提出了一种方法：使用通过机器学习进行了训练的模型，在栅格图上进行各主体的路径规划。
2、根据使用所述栅格图的方法，各主体的可移动位置是被预先规定的，因此能够相对较简单地找到各主体的路径。但是，各主体的移动受预先规定的栅格限制。因此，对于各主体要获得更佳的路径(例如实际空间内的最短路径)存在极限。
3、因此，正在探讨并非在预先规定的栅格空间而是在各主体可移动到自由位置的连续空间上对多主体的路径规划问题求解的方法。在连续空间上对路径规划问题求解的情况下，常常采用构建路线图并在所构建的路线图上搜索各主体的路径的方法(approach)(例如非专利文献2)。
4、路线图包含节点及边缘，确定搜索各主体的路径的范围。节点表示可移动位置，边缘将节点彼此连结，表示所连结的节点间可移动。在构建所述路线图时，可对应于搜索路径的对象的连续空间而在任意的位置配置节点。因此，与使用可移动位置被预先固定的栅格图的方法相比，在所述连续空间上搜索路径的方法有可能对于各主体获得更佳的路径。
5、现有技术文献
6、非专利文献
7、非专利文献1：梅裕尔·达马尼、罗志尧、爱默生·温泽尔、纪尧姆·萨托雷蒂“primal2通过强化和模仿多智能体学习寻路-终身”，ieee机器人与自动化快报，第6卷第2期，第2666-2673页，2021年(mehul damani,zhiyao luo,emerson wenzel,guillaumesartoretti,“primal2 pathfinding via reinforcement and imitation multi-agentlearning--lifelong”,ieeerobotics and automation letters,volume 6,issue 2,p.2666-2673,2021)
8、非专利文献2：费利佩·费利克斯·阿里亚斯、布瑞恩·安德鲁·伊齐特、亚历山大·浮士德、南希·m·阿马托，“动态环境中运动规划的避免临界概率路线图”，ieee机器人与自动化国际会议，2021年(felipe felix arias,brian andrew ichter,aleksandrafaust,nancy m.amato,“avoidance critical probabilistic roadmaps for motionplanning in dynamic environments”,ieeeinternational conference on roboticsand automation,2021)
技术实现思路
1、发明所要解决的问题
2、本技术发明人等发现：在连续空间上对多主体的路径规划问题求解的所述以往的方法中，存在如下的问题。即，以往的方法中，通过在连续空间整体配置节点来对各主体构建共同的路线图。一例中，节点是随机地配置在整个连续空间内。作为另一例，非专利文献2中提出的方法中，使用通过机器学习进行了训练的模型，从而在障碍物附近在可避开其他主体的位置配置节点。无论是哪种方法，基本上，节点均是配置在整个连续空间内。
3、此时，通过在连续空间上稠密地配置节点，对于各主体可采用的路径的组合增加。因此，能够通过所述路线图来发现各主体的进而最佳路径的可能性变高。但是，若稠密地配置节点，则与此相应地，节点数将增加，因此路径的搜索所耗费的成本(计算成本及时间成本)增大。因此，若稀疏地配置节点，则尽管能够降低搜索所耗费的成本，但能够发现最佳路径的可能性变低。在最差的情况(case)下，还可能产生无法发现可绕过障碍物或其他主体的路径的事态。因此，以往的方法中，存在难以兼顾进而最佳路径的发现及搜索成本降低的问题。
4、另外，此问题的产生并不限于搜索多主体的移动路径的场景。各节点可构成为，表示位置以外的其他状态(例如速度、方向等)。在此情况下，在连续状态空间中搜索从各主体的开始状态直至目标状态为止的迁移路径的场景中也可能同样地产生所述问题。
5、本发明在一方面是有鉴于此种状况而完成，其目的在于提供一种技术，在连续状态空间上对多主体的路径规划问题求解时，提高能够针对主体发现进而最佳路径的可能性，并且实现搜索所耗费的成本的降低。
6、解决问题的技术手段
7、为了解决所述课题，本发明采用以下的结构。
8、即，本发明的一方面的路径规划系统包括信息获取部、图构建部及搜索部。信息获取部构成为，获取对象信息，所述对象信息包含多个主体各自在连续状态空间中的开始状态及目标状态。图构建部构成为，使用训练完毕的路线图构建模型，根据所获取的所述对象信息，针对每个所述主体来构建路线图。搜索部构成为，在针对每个所述主体所构建的所述路线图上，搜索从所述开始状态直至所述目标状态为止的所述各主体的路径。
9、路线图构建模型包括第一处理模块、第二处理模块及推测模块。第一处理模块构成为，根据对象主体信息来生成第一特征信息，所述对象主体信息包含对象主体的目标状态及对象时间步中的候选状态。第二处理模块构成为，根据其他主体信息来生成第二特征信息，所述其他主体信息包含所述对象主体以外的其他主体的目标状态及所述对象时间步中的候选状态。推测模块构成为，根据所生成的所述第一特征信息及所述第二特征信息，推测所述对象主体在所述对象时间步的下个时间步中的一个以上的候选状态。训练完毕的所述路线图构建模型是通过使用由多个学习用主体的正解路径所获得的学习数据的机器学习而生成。
10、针对每个所述主体来构建所述路线图的步骤是通过将所述多个主体分别各别地指定为所述对象主体来执行下述处理而构成，即：将所述多个主体中的任一个主体处理为所述对象主体，将所述多个主体中的剩余主体的至少一部分处理为所述其他主体，将由所获取的所述对象信息所示的所述任一个主体的开始状态指定为所述对象主体在最开始的对象时间步中的候选状态，通过训练完毕的所述路线图构建模型来推测下个时间步中的一个以上的候选状态，且将所推测出的下个时间步中的一个以上的候选状态分别指定为新的对象时间步中的候选状态，并重复通过训练完毕的所述路线图构建模型所进行的下个时间步的候选状态的推测，直至所述任一个主体的所述目标状态或其附近状态包含在所推测的下个时间步中的一个以上的候选状态中为止。
11、候选状态与构成路线图的节点对应。即，推测模块构成为，针对对象主体，根据对象时间步的各特征信息来推测在连续状态空间上可迁移至下个时间步的一个以上的节点的配置。对象时间步中的候选状态与通过推测所得的下个时间步中的候选状态通过边缘而连结。边缘表示可从某候选状态(节点)向其他候选状态(节点)迁移。
12、所述结构中，使用训练完毕的路线图构建模型来构建每个主体的路线图。所使用的训练完毕的路线图构建模型是通过使用由多个学习用主体的正解路径所获得的学习数据的机器学习而生成。根据所述机器学习，路线图构建模型可获得结合主体的从开始直至目标为止的适当路径来构建路线图的能力。因此，根据所述结构，能够针对每个主体来构建在各主体的从开始状态直至目标状态为止的适当路径(即，想要搜索的路径)及其周边范围配置有节点的路线图。即，根据所述结构，通过使用学习了正解路径的训练完毕的路线图构建模型，能够对每个主体获得适合的路线图。与此相对，所述以往的方法中，通过在整个连续状态空间中配置节点，从而构建所有主体共同的路线图。与所述以往的方法相比，在通过所述结构获得的路线图中，能够将配置节点的范围收缩为各主体的适当范围。即，对于各主体的搜索路径而言，能够省去朝向无用位置的节点配置。因此，即便在路线图上稠密地配置节点，也能够抑制节点数的增加。因而，根据所述结构，在连续状态空间上对多主体的路径规划问题求解时，能够提高可对主体发现进而最佳路径的可能性，并且能够实现搜索所耗费的成本的降低。
13、所述一方面的路径规划系统中，所述路线图构建模型可还包括第三处理模块，所述第三处理模块构成为，根据包含与障碍物相关的信息的环境信息来生成第三特征信息。所述推测模块可构成为，根据所生成的所述第一特征信息、所述第二特征信息及所述第三特征信息，推测所述下个时间步中的一个以上的候选状态。所获取的所述对象信息可构成为，进而包含与存在于所述连续状态空间内的所述障碍物相关的信息。使用训练完毕的所述路线图构建模型的步骤可包含：由所获取的所述对象信息中所含的所述信息来构成所述环境信息，并将所构成的所述环境信息提供给所述第三处理模块。所述结构中，能够考虑包含障碍物的环境的状况，来推测构成各主体的路线图的节点的配置。因此，即便在存在障碍物的环境下，也能够对各主体构建适合的路线图。因而，根据所述结构，能够进一步提高在连续状态空间上对主体发现最佳路径的可能性，并且能够实现搜索所耗费的成本的进一步降低。
14、所述一方面的路径规划系统中，所述对象主体信息可构成为，进而包含所述对象主体在比所述对象时间步更前的时间步中的候选状态。所述其他主体信息可构成为，进而包含所述其他主体在比所述对象时间步更前的时间步中的候选状态。所述结构中，能够一边按时间序列来考虑各主体的状态迁移，一边推测构成各主体的路线图的节点的配置。因此，能够对从开始经过多个时间步到达目标的主体构建适合的路线图。因而，根据所述结构，能够进一步提高在连续状态空间上对主体发现最佳路径的可能性，并且能够实现搜索所耗费的成本的进一步降低。
15、所述一方面的路径规划系统中，所述对象主体信息可构成为，进而包含所述对象主体的属性。
16、以往的方法中，在路径搜索中使用各主体共同的路线图，因此难以考虑各主体的个体差异(即，处理属性不同的主体)。作为一例，设想在存在细窄的通路的连续空间上搜索作为移动体的各主体的移动路径的场景。此场景中，若各主体的尺寸也可不同，则可能产生下述情形(case)，即，一部分主体能够通过所述通路，但剩余主体无法通过所述通路。所述情形下，在以往的方法中，若将构成路线图的节点配置于所述通路，则有可能对无法通过所述通路的主体搜索到实际上无法移动的路径。另一方面，若不将构成路线图的节点配置于所述通路，则无法对可通过所述通路的主体搜索最佳路径的可能性变高。如此，以往的方法中，难以处理属性不同的主体。
17、与此相对，所述结构中，一边考虑各主体的属性，一边针对每个主体来推测构成路线图的节点的配置。由此，即便在存在属性不同的主体的情况下，也能够针对每个主体来构建适合的路线图。在所述情形下，能够对可通过所述通路的主体(所述通路存在于最佳路径上或其周边范围的情况下)构建将节点配置于所述通路的路线图，而对无法通过所述通路的主体构建不将节点配置于所述通路的路线图。因此，根据所述结构，即便在混合存在属性不同的主体的情况下，也能够对连续状态空间上的多主体的路径规划问题适当求解。
18、所述一方面的路径规划系统中，所述对象主体的属性可包含大小、形状、最大速度及重量中的至少任一个。根据所述结构，即便在混合存在大小、形状、最大速度及重量中的至少任一个不同的主体的情况下，也能够对连续状态空间上的多主体的路径规划问题适当求解。
19、所述一方面的路径规划系统中，所述其他主体信息可构成为，进而包含所述其他主体的属性。所述结构中，能够考虑其他主体的属性来推测构成对象主体的路线图的节点的配置。因此，即便在存在具备多种多样的属性的主体的环境下，也能够对各主体构建适合的路线图。因而，根据所述结构，能够进一步提高在连续状态空间上对主体发现最佳路径的可能性，并且能够实现搜索所耗费的成本的进一步降低。
20、所述一方面的路径规划系统中，所述其他主体的属性可包含大小、形状、最大速度及重量中的至少任一个。根据所述结构，即便在存在大小、形状、最大速度及重量中的至少任一个不同的主体的环境下，也能够对各主体构建适合的路线图。由此，能够进一步提高在连续状态空间上对主体发现最佳路径的可能性，并且能够实现搜索所耗费的成本的进一步降低。
21、所述一方面的路径规划系统中，所述对象主体信息可构成为，进而包含方向标记，所述方向标记表示所述对象主体在所述连续状态空间中迁移的方向。若获得用于机器学习的学习数据的正解路径的迁移方向发生了偏颇，则训练完毕的路线图构建模型有可能对各主体构建出仅在偏颇的方向上配置有节点的路线图。若节点被被配置在偏颇的方向上，则状态迁移的选择幅度将变窄，因此存在无法对至少任一个主体发现最佳路径的可能性。与此相对，所述结构中，通过提供给路线图构建模型的方向标记，能够对构成各主体的路线图的节点的配置方向进行控制。由此，能够抑制在各主体的路线图中，在偏颇的方向上配置节点的现象。其结果，能够进一步提高在连续状态空间上对主体发现最佳路径的可能性。
22、所述一方面的路径规划系统中，所述多个主体各自可为构成为自主移动的移动体。根据所述结构，在对多个移动体的路径规划问题求解的场景中，能够提高可对各移动体发现进而最佳路径的可能性，并且能够实现搜索所耗费的成本的降低。另外，移动体可为构成为可通过机械控制来自主移动的任意装置。移动体例如可为移动机器人、自动驾驶车辆、无人驾驶飞机等。
23、本发明的形态可不限于路径规划系统，所述路径规划系统构成为，使用训练完毕的路线图构建模型来构建每个主体的路线图以搜索各主体的路径。本发明的一方面也可为构成为在所述任一形态中构建各主体的路线图的路线图构建装置、或者构成为生成在所述任一形态中使用的训练完毕的路线图构建模型的模型生成装置。
24、例如，本发明的一方面的路线图构建装置包括：信息获取部，构成为，获取对象信息，所述对象信息包含多个主体各自在连续状态空间中的开始状态及目标状态；以及图构建部，构成为，使用训练完毕的路线图构建模型，根据所获取的所述对象信息，针对每个所述主体来构建路线图。根据所述结构，通过使用学习了正解路径的训练完毕的路线图构建模型，能够对每个主体获得适合的路线图。由此，在连续状态空间上对多主体的路径规划问题求解时，能够提高可对主体发现进而最佳路径的可能性，并且能够实现搜索所耗费的成本的降低。
25、例如，本发明的一方面的模型生成装置包括：数据获取部，构成为，获取由多个学习用主体的正解路径所生成的学习数据；以及学习处理部，构成为，使用所获取的学习数据来实施路线图构建模型的机器学习。所述学习数据包含所述各学习用主体在所述正解路径中的目标状态及多个数据集。所述多个数据集各自包含所述各学习用主体在第一时间步中的状态及在第二时间步中的状态的组合。所述第二时间步为所述第一时间步的下个时间步。所述路线图构建模型的机器学习是通过下述处理而构成，即：将所述多个学习用主体中的任一个学习用主体处理为所述对象主体；将所述多个学习用主体中的剩余的学习用主体的至少一部分处理为所述其他主体；以及对于所述各数据集，将所述任一个学习用主体在所述第一时间步中的状态作为所述对象主体在所述对象时间步中的候选状态而提供给所述第一处理模块，将所述剩余的学习用主体的至少一部分在所述第一时间步中的状态作为所述其他主体在所述对象时间步中的候选状态而提供给所述第二处理模块，由此来训练所述路线图构建模型，以使由所述推测模块所推测的所述对象主体在下个时间步中的候选状态符合所述任一个学习用主体在所述第二时间步中的状态。根据所述结构，能够生成获得了对每个主体构建适合的路线图的能力的、训练完毕的路线图构建模型。通过使用所述训练完毕的路线图构建模型，在连续状态空间上对多主体的路径规划问题求解时，能够提高可对主体发现进而最佳路径的可能性，并且能够实现搜索所耗费的成本的降低。
26、所述一方面的模型生成装置中，所述对象主体信息可构成为，进而包含方向标记，所述方向标记表示所述对象主体在所述连续状态空间中迁移的方向。所述各数据集可构成为，进而包含训练标记，所述训练标记表示所述连续状态空间内的所述第一时间步的状态至所述第二时间步的状态的方向。所述路线图构建模型的机器学习可包含：对于所述各数据集，推测所述对象主体在下个时间步中的候选状态时，将所述任一个学习用主体的所述训练标记作为所述对象主体的方向标记而提供给所述第一处理模块。
27、所述结构中，能够基于各数据集中所含的训练标记来管理在机器学习中使用的各数据集的迁移方向。借助所述训练标记，以无遗漏地训练各方向的迁移的方式将各数据集用于机器学习，由此，能够生成配置节点的方向难以偏颇的训练完毕的路线图构建模型。而且，通过在对象主体信息中包含方向标记的项目，能够生成获得了通过方向标记对配置节点的方向进行控制的能力的、训练完毕的路线图构建模型。通过使用此训练完毕的路线图构建模型，能够避免在各主体的路线图中配置节点的方向发生偏颇，由此，能够避免状态迁移的选择幅度变窄。其结果，能够进一步提高在连续状态空间上对主体发现最佳路径的可能性。
28、作为所述各形态的路径规划系统、路线图构建装置及模型生成装置的其他形态，本发明的一方面也可为实现以上的各结构的全部或其一部分的信息处理方法，也可为信息处理系统，也可为程序，或者还可为存储有此种程序的、计算机或其他装置、机械等可读取的存储介质。此处，所谓计算机等可读取的存储介质，是指通过电、磁、光学、机械或化学作用来保存程序等信息的介质。
29、例如，本发明的一方面的路径规划方法是由计算机执行下述步骤的信息处理方法，即：获取对象信息，所述对象信息包含多个主体各自在连续状态空间中的开始状态及目标状态；使用训练完毕的路线图构建模型，根据所获取的所述对象信息，针对每个所述主体来构建路线图；以及在针对每个所述主体所构建的所述路线图上，搜索从所述开始状态直至所述目标状态为止的所述各主体的路径。
30、例如，本发明的一方面的路径规划程序是用于使计算机执行下述步骤的程序，即：获取对象信息，所述对象信息包含多个主体各自在连续状态空间中的开始状态及目标状态；使用训练完毕的路线图构建模型，根据所获取的所述对象信息，针对每个所述主体来构建路线图；以及在针对每个所述主体所构建的所述路线图上，搜索从所述开始状态直至所述目标状态为止的所述各主体的路径。
31、例如，本发明的一方面的路线图构建方法是由计算机执行下述步骤的信息处理方法，即：获取对象信息，所述对象信息包含多个主体各自在连续状态空间中的开始状态及目标状态；以及使用训练完毕的路线图构建模型，根据所获取的所述对象信息，针对每个所述主体来构建路线图。
32、例如，本发明的一方面的路线图构建程序是用于使计算机执行下述步骤的程序，即：获取对象信息，所述对象信息包含多个主体各自在连续状态空间中的开始状态及目标状态；以及使用训练完毕的路线图构建模型，根据所获取的所述对象信息，针对每个所述主体来构建路线图。
33、例如，本发明的一方面的模型生成方法是由计算机执行下述步骤的信息处理方法，即：获取由多个学习用主体的正解路径所生成的学习数据；以及使用所获取的学习数据来实施路线图构建模型的机器学习。
34、例如，本发明的一方面的模型生成程序是用于使计算机执行下述步骤的程序，即：获取由多个学习用主体的正解路径所生成的学习数据；以及使用所获取的学习数据来实施路线图构建模型的机器学习。
35、发明的效果
36、根据本发明，在连续状态空间上对多主体的路径规划问题求解时，能够提高可对主体发现进而最佳路径的可能性，并且能够实现搜索所耗费的成本的降低。
1.一种路径规划系统，包括：
2.根据权利要求1所述的路径规划系统，其中
3.根据权利要求1或2所述的路径规划系统，其中
4.根据权利要求1至3中任一项所述的路径规划系统，其中
5.根据权利要求4所述的路径规划系统，其中
6.根据权利要求1至5中任一项所述的路径规划系统，其中
7.根据权利要求6所述的路径规划系统，其中
8.根据权利要求1至7中任一项所述的路径规划系统，其中
9.根据权利要求1至8中任一项所述的路径规划系统，其中
10.一种路径规划方法，由计算机执行下述步骤：
11.一种路线图构建装置，包括：
12.一种模型生成装置，包括：
13.根据权利要求12所述的模型生成装置，其中
14.一种模型生成方法，由计算机执行下述步骤：
