路径规划搜索方法和计算装置与流程

摘要: 本技术涉及用于搜索用于使移动对象移动的路径规划的方法和处理器。背景技术:1、当在仓库、工厂等中通过使用无人驾驶载具或无人驾驶机器人(下文中,两者也统称为自动引导...
路径规划搜索方法和计算装置与流程

本技术涉及用于搜索用于使移动对象移动的路径规划的方法和处理器。

背景技术:

1、当在仓库、工厂等中通过使用无人驾驶载具或无人驾驶机器人(下文中,两者也统称为自动引导载具或agv)来运送货物、零件、产品等时,预先计算agv的移动路径并对其进行优化。

2、wo2022/097460a1出版物公开了一种用于通过简单的优化算法高速且有效地找到优化问题的最优解的技术,该技术具有:多个数据生成单元;波动设定单元,其将波动概率供应到数据生成单元,将由数据生成单元生成的数据的出现频率设定为非均匀的,并且将特定变量的出现频率设定为与其它变量的出现频率不同的值;多个数据转换单元,其读取由数据生成单元生成的数据并且将数据转换为信息;输出调节单元,其将输出调节信号发送到数据生成单元或者输出调节信号和波动概率的值;以及反馈控制单元,其在未获得最优解时重复地控制将输出调节信号发送到数据生成单元或者输出调节信号和波动概率的值的操作。

3、当根据仓库、工厂等的规模的增加而使用数百或数千个agv时,在agv之间经常发生拥堵,运送规划或过程变得不确定,并且运送或生产的吞吐量可能降低。

4、现有技术文献

5、专利文献

6、专利文献1:wo2022/097460小册子

7、专利文献2:日本专利第6029048号公报

8、专利文献3:日本专利第6011928号公报

9、专利文献4:日本待审专利第2015-184829号公报

10、专利文献5:日本待审专利第2019-198902号公报

11、专利文献6:日本待审专利第2019-198903号公报

12、专利文献7:wo2019/017412小册子

13、专利文献8:日本待审专利第2018-166194号公报

14、非专利文献

15、非专利文献1:m. aono等人,proceedings of nolta 2012,586-589(2012)

16、非专利文献2:kasai, s.、aono, m.和naruse, m.:amoeba-inspired computingarchitecture implemented using charge dynamics in parallel capacitancenetwork,appl. phys. lett.,vol. 103,163703(2013)

17、非专利文献3:ryo wakamiya、seiya kasai、masashi aono、makoto naruse、hiroyoshi miwa,“electronic circuit implementation of amoeba-inspired solutionsearch algorithm for optimization problems”,ieice technical report 114(442),pp.81-85(2015)

18、非专利文献4:a. h. ngoc nguyen、m. aono、y. hara-azumi,“fpga-basedamoeba-inspired sat solver for cyber-physical systems”,acm/ieee internationalconference on cyber-physical systems(iccps),316-317(2019)

19、非专利文献5:a. h. ngoc nguyen、m. aono、y. hara-azumi,“fpga-basedhardware/software co-design of a bio-inspired sat solver”,ieee access,doi:10.1109/access.2020.2980008(2020)

20、非专利文献6:y. j. yan、h. amano、m. aono、k. ohkoda、s. fukuda、k. saito、s. kasai,“resource-saving fpga implementation of the satisfiability problemsolver: amoebasatslim”,fpt2021:1-5(2021)

21、非专利文献7:p. huang、k. wei、h. amano、k. ohkoda、m. aono,implementingmulti agent path finding algorithm for smart factory on a multi-fpga system,ieice technical report(web),174(reconf2022 26-41),pp.17-18(2022)

22、非专利文献8:p. huang、k. wei、h. amano、k. ohkoda、m. aono,multi-boardfpga implementation to solve the satisfiability problem for multi-agent pathfinding in smart factory,2022 tenth international symposium on computing andnetworking workshops(candar),pp.406-410(2022)

23、非专利文献9:t. okuyama、h. amano、k. ohkoda、m. aono,“efficient fpgaimplementation of amoeba-inspired sat solver with feedback and bouncebackcontrol: harnessing variable-level parallelism for large-scale problemsolving in edge computing”,heart 2023(2023)

24、非专利文献10:n. takeuchi、m. aono、y. hara-azumi和c. l. ayala,“acircuit-level amoeba-inspired sat solver”,ieee transactions on circuits andsystems ii: express briefs:vol. 67,no. 10,pp. 2139-2143(2020)

25、非专利文献11:k. hara、n. takeuchi、m. aono、y. hara-azumi,“amoeba-inspired stochastic hardware sat solver”,international symposium on qualityelectronic design(isqed),(2019)

26、非专利文献12:masashi aono、yusei kujirai、hiroki nozaki,“amoeba-inspired computing paradigm for bridging the gap between cyber and physicalspaces”, journal of the japanese society for artificial intelligence,vol.33(5),pp.56-569(2018)

27、非专利文献13:l. zhu、s.-j. kim、m. hara、m. aono,“remarkable problem-solving ability of unicellular amoeboid organism and its mechanism”,royalsociety open science 5:180396(2018)

28、非专利文献14:saito、kasai、aono等人,the society of applied physics,poster presentation(2019)

29、非专利文献15:k. saito、m. aono、s. kasai,“amoeba-inspired analogelectronic computing system integrating resistance crossbar for solving thetravelling salesman problem”,scientific reports 10,20772(2020)

30、非专利文献16:m. aono,“amoeba-inspired combinatorial optimizationmachines”,japanese journal of applied physics 59,060502,(2020)

技术实现思路

1、技术问题

2、期望提供方法和处理器,其用于搜索路径规划,以最小化由于诸如货物的装载/卸载等的流量集中、由于早到达而等待以及甚至当使用许多agv时路径的合并而引起的拥堵的发生。

3、期望提供方法和处理器,其能够减少路径搜索的计算量,缩短路径搜索所需的时间,搜索更多的路径,或者其在确定路径规划时的组合。

4、当在确定路径规划的过程中在预定时间内及时搜索路径时,多个agv的交通堵塞可能发生在货物装载或卸载的目的地点或其附近。

5、另外,交通拥堵的发生可能导致agv中的延迟,该agv以高优先级或高紧急性运送货物等到达目的地点。

6、此外,还存在预先指定货物的到达时间和到达顺序等的情况。

7、期望消除或减少由agv引起的交通堵塞,并且期望在所需时间运输必要的货物。

8、在确定路径规划时,期望搜索将精确地在预定时间到达的路径。

9、另外,随着移动对象能够移动的空间的增加,用于搜索路径规划的计算量呈指数地增加,并且可能难以在合理的时间内搜索路径规划。即使在这种情况下,也需要一种能够控制路径规划搜索的计算量的方法。

10、期望提供一种即使当用于搜索路径规划的计算量减少时也能够有效地搜索更优的路径规划的方法。

11、问题的解决方案

12、该技术例如包括用于由计算机搜索用于使移动对象移动的路径规划的方法,该方法包括以下步骤:分别确定能够以第一速度移动的第一移动对象在第一时间出现的第一初始位置和所述第一移动对象在比所述第一时间晚的第二时间出现的第一到达位置;确定允许所述第一移动对象从所述第一时间的所述第一初始位置移动到所述第二时间的所述第一到达位置的第一多个路径规划,所述第一多个路径规划能由时间和位置的对来表示;确定在每个时间不包括在所述第一多个路径规划的任何一个中的位置;以及在所述第一时间和所述第二时间之间的第三时间确定至少一个第一移动位置,所述第一移动位置是在从所述第三时间起经过预定时间之后所述第一移动对象能够移动到的位置,所述第一移动位置排除不包括在所述第一多个路径规划中的任何一个中的位置。