技术领域technical field
本发明涉及避障路径规划技术领域，尤其涉及一种智能导购车行驶路径的规划方法、装置及智能导购车。 The invention relates to the technical field of obstacle avoidance path planning, in particular to a planning method and device for a driving path of an intelligent shopping guide vehicle and an intelligent shopping guide vehicle. the
背景技术Background technique
由于信息与工业的高速发展与信息技术的深入变革，具有智能处理功能的嵌入式终端已经大步走入平民生活，从简单的智能家居到复杂的通信设备再至庞大精密的工厂机床，嵌入式设备已经无处不在的环绕在人们身边。智能导购车是一种集导购、特价商品介绍、携带货物、信息交互等功能的智能终端，智能导购车的出现将方便顾客选购商品，提高超市运营效率。由于超市、商场等购物场所的布局是综合了超市所在建筑结构、顾客购物习惯、环境搭建成本、审美等多方面因素导致超市货架摆放具有一定的规律性和对称性，由此应用传统的避障路径算法可能会产生不必要的开销。 Due to the rapid development of information and industry and the in-depth transformation of information technology, embedded terminals with intelligent processing functions have made great strides into civilian life, from simple smart homes to complex communication equipment to huge and sophisticated factory machine tools, embedded Devices are everywhere around people. A smart shopping guide cart is an intelligent terminal that integrates functions such as shopping guide, introduction of special offers, carrying goods, and information interaction. Since the layout of shopping places such as supermarkets and shopping malls is a combination of various factors such as the building structure of the supermarket, customer shopping habits, environmental construction costs, and aesthetics, the placement of supermarket shelves has certain regularity and symmetry. Barrier path algorithms may generate unnecessary overhead. the
现有技术的智能导购车行驶路径的规划方法一般采用传统的可视图法来求解避障路径，进而得到智能导购车的行驶路径。图1为现有技术的智能导购车行驶路径的规划方法对应的示意图。如图1所示，传统的可视图法求解避障路径算法是连接起始点、目标点和所有障碍物顶点，保留不穿过任何障碍物的可视线，并在得到的加权图的基础之上通过单源最短路径算法求解起始点到目标点路径。 The prior art planning method for the driving path of the intelligent shopping guide vehicle generally adopts the traditional visualization method to solve the obstacle avoidance path, and then obtain the driving path of the intelligent shopping guide vehicle. FIG. 1 is a schematic diagram corresponding to a planning method for a driving route of an intelligent shopping guide vehicle in the prior art. As shown in Figure 1, the traditional visual graph method to solve the obstacle avoidance path algorithm is to connect the starting point, the target point and all obstacle vertices, retain the visible line that does not pass through any obstacle, and based on the obtained weighted graph Solve the path from the starting point to the goal point through the single-source shortest path algorithm. the
但是现有技术采用可视图法来规划智能导购车的行驶路径，是将障碍物的所有顶点与起点和目标点连接，这样的做法计算量很大，导致智能导购车行驶路径的规划效率较低，设备成本较高。 However, the existing technology uses the visual graph method to plan the driving path of the intelligent shopping guide car, which is to connect all the vertices of the obstacles with the starting point and the target point. , the equipment cost is higher. the
发明内容Contents of the invention
本发明的目的在于提出一种智能导购车行驶路径的规划方法、装置及智能导购车，以达到提高智能导购车行驶路径的规划效率，降低设备成本的目的。 The object of the present invention is to provide a planning method and device for the driving path of the intelligent shopping guide vehicle and the intelligent shopping guide vehicle, so as to improve the planning efficiency of the driving path of the intelligent shopping guide vehicle and reduce the equipment cost. the
本发明提供了一种智能导购车行驶路径的规划方法，所述方法包括： The present invention provides a method for planning the travel path of an intelligent shopping guide vehicle, the method comprising:
确定智能导购车的起点和目标点； Determine the starting point and target point of the smart shopping guide;
在空间环境中将所述起点与所述目标点通过一条直线进行连接，得到的空间中的虚拟连线； Connect the starting point and the target point through a straight line in the space environment to obtain a virtual connection in space;
将所述虚拟连线穿过的每一个障碍物的所有顶点、所述起点和所述目标点之间进行直线连接，并保留所有可视线，其中，所述可视线为不穿过任何障碍物的线段； Connect all vertices of each obstacle passed by the virtual line, the starting point and the target point with a straight line, and keep all visible lines, wherein the visible lines do not pass through any obstacles the line segment;
将每一条被保留的可视线进行连通，以形成候选路径； Connect each reserved visual line to form a candidate path;
计算每一条所述候选路径的长度，确定长度最短的候选路径为智能导购车的行驶路径。 The length of each candidate path is calculated, and the candidate path with the shortest length is determined as the driving path of the intelligent shopping guide vehicle. the
可选的，所述计算每一条所述候选路径的长度的方法包括：迪杰斯特拉算法、贝尔曼-福特算法、普利姆算法或弗洛伊德算法。 Optionally, the method for calculating the length of each candidate path includes: Dijkstra's algorithm, Bellman-Ford algorithm, Prim's algorithm or Floyd's algorithm. the
可选的，在所述计算每一条所述候选路径的长度，确定长度最短的候选路径为智能导购车的行驶路径之后，还包括： Optionally, after calculating the length of each of the candidate paths and determining that the shortest candidate path is the driving path of the intelligent shopping guide car, it also includes:
对确定的所述行驶路径进行加宽处理，并在所述行驶路径上设置均匀的子目标点。 The determined driving path is widened, and uniform sub-target points are set on the driving path. the
对应地，本发明还提供了一种智能导购车行驶路径的规划装置，所述装置包括： Correspondingly, the present invention also provides a planning device for a driving path of an intelligent shopping guide vehicle, the device comprising:
确定起止点模块，用于确定智能导购车的起点和目标点； Determine the starting and ending point module, which is used to determine the starting point and target point of the intelligent shopping guide car;
形成虚拟连线模块，用于在空间环境中将所述起点与所述目标点通过一条直线进行连接，得到的空间中的虚拟连线； Form a virtual connection module, which is used to connect the starting point and the target point through a straight line in the space environment to obtain a virtual connection in space;
形成可视线模块，用于将所述虚拟连线穿过的每一个障碍物的所有顶点、所述起点和所述目标点之间进行直线连接，并保留所有可视线，其中，所述可视线为不穿过任何障碍物的线段； forming a visual line module, which is used to connect all vertices of each obstacle passed by the virtual line, the starting point and the target point in a straight line, and retain all visible lines, wherein the visible line is a line segment that does not pass through any obstacle;
形成候选路径模块，用于将每一条被保留的可视线进行连通，以形成候选路径； Form a candidate path module, which is used to connect each reserved visual line to form a candidate path;
确定行驶路径模块，用于计算每一条所述候选路径的长度，确定长度最短的候选路径为智能导购车的行驶路径。 The determining driving path module is used to calculate the length of each of the candidate paths, and determine the candidate path with the shortest length as the driving path of the intelligent shopping guide vehicle. the
可选的，所述确定行驶路径模块，具体用于： Optionally, the module for determining the driving route is specifically used for:
通过迪杰斯特拉算法、贝尔曼-福特算法、普利姆算法或弗洛伊德算法计算每一条所述候选路径的长度。 The length of each candidate path is calculated by Dijkstra's algorithm, Bellman-Ford algorithm, Prim's algorithm or Floyd's algorithm. the
可选的，所述智能导购车行驶路径的规划装置，还包括： Optionally, the planning device for the driving path of the intelligent shopping guide car also includes:
确定模块，用于对确定的所述行驶路径进行加宽处理，并在所述行驶路径上设置均匀的子目标点。 A determining module, configured to widen the determined driving path, and set uniform sub-target points on the driving path. the
对应地，本发明还提供了一种智能导购车行，所述智能导购车包括本发明任意实施例提供的智能导购车行驶路径的规划装置。 Correspondingly, the present invention also provides a smart shopping guide car store, the smart shopping guide car includes the device for planning the travel path of the smart shopping guide car provided in any embodiment of the present invention. the
本发明提供的一种智能导购车行驶路径的规划方法、装置及智能导购车，通过在空间环境中将起点和目标点进行连接，并将虚拟连线通过的障碍物的所有顶点、起点和目标点进行直线连接，保留所有可视线，进一步得到候选路径，并通过迪杰斯特拉算法计算候选路径的长度，进而确定智能导购车的行驶路径，本发明与现有技术将所有障碍物的顶点与起点和目标点进行连接的情况相比，针对商场、超市等购物场所货品摆放具有对称性的结构特点，更具适用性，本发明能够减小规划行驶路径过程中的计算量，提高智能导购车行驶路径的规划效率，进而降低设备成本。并且本发明实施例提供的方法对确定的行驶路径进行加宽处理，并在行驶路径在设置均匀的子目标点，能够针对超市等局部人流复杂的状况，保证无碰的同时解决传统避障算法的“迷失”问题，整体提高了智能导购车的可用性。 The present invention provides a planning method, device and intelligent shopping guide car for the driving path of a smart shopping guide car. By connecting the starting point and the target point in the space environment, and connecting all vertices, starting points and targets of the obstacles passed by the virtual connection line Points are connected in a straight line, all visible lines are reserved, and the candidate path is further obtained, and the length of the candidate path is calculated by the Dijkstra algorithm, and then the driving path of the intelligent shopping guide car is determined. The present invention and the prior art combine the vertices of all obstacles Compared with the case of connecting the starting point and the target point, it is more applicable for the symmetrical structural characteristics of the placement of goods in shopping places such as shopping malls and supermarkets. The present invention can reduce the amount of calculation in the process of planning driving routes and improve intelligence The planning efficiency of the driving path of the shopping guide car, thereby reducing the cost of equipment. Moreover, the method provided by the embodiment of the present invention widens the determined driving path, and sets uniform sub-target points on the driving path, which can solve the traditional obstacle avoidance algorithm while ensuring no collision for the complex situation of local crowds such as supermarkets. The "lost" problem of the smart shopping guide cart improves the overall usability. the
附图说明Description of drawings
图1为现有技术的智能导购车行驶路径的规划方法对应的示意图； Fig. 1 is the schematic diagram corresponding to the planning method of the intelligent shopping guide vehicle driving path of the prior art;
图2为本发明实施例提供的智能导购车行驶路径的规划方法的实现流程图； Fig. 2 is the implementation flow diagram of the planning method of the intelligent shopping guide vehicle driving route that the embodiment of the present invention provides;
图3a-b为本发明实施例提供的智能导购车行驶路径的规划方法对应的示意图； Figure 3a-b is a schematic diagram corresponding to the planning method of the driving path of the intelligent shopping guide car provided by the embodiment of the present invention;
图4为本发明实施例提供的智能导购车行驶路径的规划方法在加宽处理和设置子目标点过程中对应的示意图； Fig. 4 is a corresponding schematic diagram in the process of widening and setting sub-target points in the planning method of the intelligent shopping guide vehicle driving path provided by the embodiment of the present invention;
图5为本发明实施例提供的智能导购车行驶路径的规划装置的结构示意图。 FIG. 5 is a schematic structural diagram of a device for planning a driving route of a smart shopping guide provided by an embodiment of the present invention. the
具体实施方式Detailed ways
为使本发明解决的技术问题、采用的技术方案和达到的技术效果更加清楚，下面结合附图和实施例对本发明作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅仅用于解释本发明，而非对本发明的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与本发明相关的部分而非全部内容。 In order to make the technical problems solved by the present invention, the technical solutions adopted and the technical effects achieved clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, but not to limit the present invention. In addition, it should be noted that, for the convenience of description, only parts related to the present invention are shown in the drawings but not all content. the
图2为本发明实施例提供的智能导购车行驶路径的规划方法的实现流程图。本发明实施例提供的智能导购车行驶路径的规划方法可以由本发明实施例提供的智能导购车行驶路径的规划装置来执行，该装置可以由软件和/或硬件来实现。如图2所示，本发明实施例提供的智能导购车行驶路径的规划方法包括： Fig. 2 is a flow chart of the implementation of the planning method for the driving route of the intelligent shopping guide car provided by the embodiment of the present invention. The method for planning the driving route of the intelligent shopping guide vehicle provided in the embodiment of the present invention can be executed by the device for planning the driving route of the intelligent shopping guide vehicle provided in the embodiment of the present invention, and the device can be realized by software and/or hardware. As shown in Figure 2, the planning method of the driving path of the intelligent shopping guide car provided by the embodiment of the present invention includes:
步骤201，确定智能导购车的起点和目标点。 Step 201, determine the starting point and target point of the intelligent shopping guide cart. the
其中，所述起点为智能导购车所在的位置点，所述目标点为客户想要购买的商品所在的位置点。起点的信息可以由智能导购车中具有定位功能的设备实现，目标点的信息可以由用户进行输入。 Wherein, the starting point is the location point of the intelligent shopping guide cart, and the target point is the location point of the commodity that the customer wants to buy. The information of the starting point can be realized by the device with positioning function in the intelligent shopping guide cart, and the information of the target point can be input by the user. the
步骤202，在空间环境中将所述起点与所述目标点通过一条直线进行连接，得到的空间中的虚拟连线。 Step 202, connect the starting point and the target point through a straight line in the space environment to obtain a virtual connection in space. the
图3a是本发明实施例提供的智能导购车行驶路径的规划方法在本步骤中对应的示意图。参照图3a，在空间环境中将所述起点与所述目标点通过一条直线进行连接，得到的空间中的虚拟连线。其中，在图3a中，起点用S表示，目标点用G表示，多个矩形表示超市的货架。将起点S和目标点G用直线连接起来，连接起点S和目标点G形成一条穿越障碍物的空间中的虚拟连线SG，虚拟连线SG穿过的障碍物组成了障碍物集合可以表示为：O＝{Oi|i＝1,2,…,K}。并且障碍物集合中障碍物将虚拟连线SG分割成了多条分线段，其中，所述分线段是虚拟连线SG被障碍物分割成的多条线段。所述分线段的集合L可以表示为：L＝{li|i＝1,2,…,K+1}。 Fig. 3a is a schematic diagram corresponding to this step of the planning method for the driving route of the intelligent shopping guide vehicle provided by the embodiment of the present invention. Referring to FIG. 3 a , in the space environment, the starting point and the target point are connected by a straight line to obtain a virtual connection in space. Wherein, in FIG. 3 a , the starting point is represented by S, the target point is represented by G, and multiple rectangles represent supermarket shelves. Connect the starting point S and the target point G with a straight line, and connect the starting point S and the target point G to form a virtual connection SG in the space passing through obstacles. The obstacles passed by the virtual connection SG form a set of obstacles, which can be expressed as : O={Oi |i=1,2,...,K}. And the obstacles in the obstacle set divide the virtual line SG into multiple line segments, wherein the line segments are multiple line segments into which the virtual line SG is divided by obstacles. The set L of the segmented line segments can be expressed as: L={li |i=1, 2, . . . , K+1}.
步骤203，将所述虚拟连线穿过的每一个障碍物的所有顶点、所述起点和所述目标点之间进行直线连接，并保留所有可视线。 Step 203, making a straight line connection between all vertices of each obstacle passed by the virtual connection line, the starting point and the target point, and keeping all visible lines. the
图3b是本发明实施例提供的智能导购车行驶路径的规划方法在本步骤中对应的示意图。参照图3b，将所述虚拟连线SG穿过的每一个障碍物Oi的所有顶点、 所述起点S和所述目标点G之间进行直线连接，并保留所有可视线。其中，所述可视线为不穿过任何障碍物的线段。在经过步骤203之后，除可视线以外的其它线段均被删除，并得到了如图3b所示的由可视线和分线段组成的联通网图。联通网图各边的权为实际距离与道路阻塞权衡下的权值。 Fig. 3b is a schematic diagram corresponding to this step of the planning method for the driving route of the intelligent shopping guide provided by the embodiment of the present invention. Referring to FIG. 3b, a straight line connection is made between all vertices of each obstacleOi passed by the virtual link SG, the starting point S and the target point G, and all visible lines are reserved. Wherein, the visible line is a line segment that does not pass through any obstacle. After step 203, all line segments except the visible line are deleted, and a China Unicom network diagram composed of visible lines and sub-line segments is obtained as shown in FIG. 3b. The weight of each side of the China Unicom network graph is the weight value under the trade-off between actual distance and road congestion.
步骤204，将每一条被保留的可视线进行连通，以形成候选路径。 Step 204, connect each reserved visual line to form a candidate path. the
其中，所述候选路径由多条能够联通起点到目标点的、首位相连的可视线组成。待确定的智能导购车的行驶路径可以从候选路径中选择。 Wherein, the candidate path is composed of a plurality of first connected visible lines that can connect the starting point to the target point. The driving route of the smart shopping guide vehicle to be determined can be selected from candidate routes. the
步骤205，计算每一条所述候选路径的长度，确定长度最短的候选路径为智能导购车的行驶路径。 Step 205, calculating the length of each candidate route, and determining the candidate route with the shortest length as the driving route of the intelligent shopping guide vehicle. the
在上述方案中，可选的，所述计算每一条所述候选路径的长度的方法包括：迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)、普利姆算法(Prim)或弗洛伊德算法(Floyd)。 In the above solution, optionally, the method for calculating the length of each of the candidate paths includes: Dijkstra algorithm (Dijkstra), Bellman-Ford algorithm (Bellman-Ford), Prim's algorithm ( Prim) or Floyd's algorithm (Floyd). the
其中，Dijkstra算法是比较经典的单元最短路径搜索算法，该算法可以在以一个确定点为起点的情况下，计算一个节点到其他所有节点的最短路径。算法的运行特点是在未找到起点到目标点的最短路径之前以起点为中心向外层逐层扩展，直到达到目标为止。Dijkstra算法能得出最短路径的最优解，他的时间复杂度为n2，它运算的时间与效率和节点数目有关。 Among them, the Dijkstra algorithm is a relatively classic unit shortest path search algorithm, which can calculate the shortest path from a node to all other nodes with a certain point as the starting point. The operation characteristic of the algorithm is that before the shortest path from the starting point to the target point is found, it will expand layer by layer from the starting point to the outer layer until the target point is reached. Dijkstra's algorithm can get the optimal solution of the shortest path, its time complexity is n2 , and its operation time is related to the efficiency and the number of nodes.
其中，确定的智能导购车的行驶路径，即为一条从起点到目标点的无碰路径，此基础上的无碰路径主要是为智能导购车选择一条在超市固定建筑物之间穿梭的最优路径。 Among them, the determined driving path of the intelligent shopping guide vehicle is a non-collision path from the starting point to the target point. path. the
可选的，在所述计算每一条所述候选路径的长度，确定长度最短的候选路径为智能导购车的行驶路径之后，还可以包括：对确定的所述行驶路径进行加宽处理，并在所述行驶路径上设置均匀的子目标点。图4为本发明实施例提供的智能导购车行驶路径的规划方法在加宽处理和设置子目标点过程中对应的示意图。参照图4，对确定的所述行驶路径进行加宽处理，并在所述行驶路径上设置均匀的子目标点。 Optionally, after calculating the length of each of the candidate paths and determining that the candidate path with the shortest length is the driving path of the intelligent shopping guide vehicle, it may also include: widening the determined driving path, and Uniform sub-target points are set on the driving path. Fig. 4 is a schematic diagram corresponding to the process of widening and setting sub-target points in the planning method of the driving route of the intelligent shopping guide provided by the embodiment of the present invention. Referring to FIG. 4 , the determined driving path is widened, and uniform sub-target points are set on the driving path. the
由于确定的所述行驶路径是由不同的点和点之间的连线构成的一条路径，对确定的所述行驶路径进行加宽处理的目的的将所述行驶路径进行“加宽”，在确定的所述行驶路径的两侧按照一定距离加宽形成一条从起点到目标点的“通道”，就是智能导购车的可行区域。 Since the determined driving path is a path composed of different points and the connection lines between the points, the purpose of widening the determined driving path is to "widen" the driving path. The two sides of the determined driving path are widened according to a certain distance to form a "channel" from the starting point to the target point, which is the feasible area of the intelligent shopping guide vehicle. the
为保持智能导购车在可行区域内行走，在所述行驶路径上按照一定的距离均匀的设置几个子目标点，则将智能导购车的行走变为从一个子目标点到另外一个子目标点的过程。子目标点的设置对整体的行驶路径规划和躲避障碍物碰撞具有非常重要的作用。智能导购车可以在可行区域内进行局部避障，只要不超出可行区域范围则认定智能导购车仍然是遵循既定路径朝向目标点前进的。子目标点的设定减小了两个节点之间的距离，较小的节点间距保证了当智能导购车因为避障而偏离方向的时候，尽快使智能导购车回归既定路径之上，保证了可行区域的有效性，并且有效的避免了智能导购车的自我迷失。例如，智能导购车以一个子目标点为当前目标前进，当智能导购车与当前子目标点的距离小于等于预设的举例阈值时，当前目标设置成沿路径的下一子目标点。 In order to keep the intelligent shopping guide vehicle walking within the feasible area, several sub-target points are evenly set according to a certain distance on the driving path, and the walking of the intelligent shopping guide vehicle becomes a step from one sub-target point to another sub-target point. process. The setting of sub-target points plays a very important role in the overall driving path planning and obstacle collision avoidance. The smart shopping guide car can perform local obstacle avoidance in the feasible area, as long as it does not exceed the feasible area, it is determined that the smart shopping guide car is still moving towards the target point following the established path. The setting of the sub-target point reduces the distance between the two nodes. The smaller node spacing ensures that when the smart shopping guide car deviates from the direction due to obstacle avoidance, the smart shopping guide car will return to the established path as soon as possible, ensuring The effectiveness of the feasible area, and effectively avoid the self-lost of the intelligent shopping guide car. For example, the smart shopping guide car moves forward with a sub-target point as the current target, and when the distance between the smart shopping guide car and the current sub-target point is less than or equal to a preset example threshold, the current target is set as the next sub-target point along the path. the
本发明实施例对行驶路径进行加宽处理和设置子目标的目的是保障智能导购车在所述行驶路径上行驶的基础之上躲避移动的小型障碍物，可保证智能导购车在确定的行驶路径之上，解决了可视图算法求避障路径的“迷失”问题。 In the embodiments of the present invention, the purpose of widening the driving path and setting sub-goals is to ensure that the smart shopping guide car avoids moving small obstacles on the basis of driving on the driving path, so as to ensure that the smart shopping guide car travels on the determined driving path. Above, it solves the "lost" problem of the visual graph algorithm seeking the obstacle avoidance path. the
本实施例提供的智能导购车行驶路径的规划方法，通过在空间环境中将起点和目标点进行连接，并将虚拟连线通过的障碍物的所有顶点、起点和目标点进行直线连接，保留所有可视线，进一步得到候选路径，并通过迪杰斯特拉算法计算候选路径的长度，进而确定智能导购车的行驶路径，本发明与现有技术将所有障碍物的顶点与起点和目标点进行连接的情况相比，针对商场、超市等购物场所货品摆放具有对称性的结构特点，更具适用性，本发明能够减小规划行驶路径过程中的计算量，提高智能导购车行驶路径的规划效率，进而降低设备成本。并且本发明实施例提供的方法对确定的行驶路径进行加宽处理，并在行驶路径在设置均匀的子目标点，能够针对超市等局部人流复杂的状况，保证无碰的同时解决传统避障算法的“迷失”问题，整体提高了智能导购车的可用性。 The planning method for the driving path of the intelligent shopping guide car provided in this embodiment, by connecting the starting point and the target point in the space environment, and connecting all vertices, starting points and target points of the obstacles passed by the virtual connection line in a straight line, retaining all Visible line, further get the candidate path, and calculate the length of the candidate path through the Dijkstra algorithm, and then determine the driving path of the intelligent shopping guide car. The present invention and the prior art connect the vertices of all obstacles with the starting point and the target point Compared with the situation of shopping malls, supermarkets and other shopping places with symmetrical structural characteristics, the present invention can reduce the amount of calculation in the process of planning the driving path and improve the planning efficiency of the driving path of the intelligent shopping guide car , thereby reducing equipment costs. Moreover, the method provided by the embodiment of the present invention widens the determined driving path, and sets uniform sub-target points on the driving path, which can solve the traditional obstacle avoidance algorithm while ensuring no collision for the complex situation of local crowds such as supermarkets. The "lost" problem of the smart shopping guide cart improves the overall usability. the
图5为本发明实施例提供的智能导购车行驶路径的规划装置的结构示意图。如图5所示，本发明实施例提供的智能导购车行驶路径的规划装置包括：确定起止点模块、形成虚拟连线模块、形成可视线模块、形成候选路径模块和确定 行驶路径模块。 FIG. 5 is a schematic structural diagram of a device for planning a driving route of a smart shopping guide provided by an embodiment of the present invention. As shown in Figure 5, the planning device for the travel path of the intelligent shopping guide car provided by the embodiment of the present invention includes: a module for determining the start and end point, a module for forming a virtual connection, a module for forming a visible line of sight, a module for forming a candidate path, and a module for determining the travel path. the
其中，所述确定起止点模块，用于确定智能导购车的起点和目标点；所述形成虚拟连线模块，用于在空间环境中将所述起点与所述目标点通过一条直线进行连接，得到的空间中的虚拟连线；所述形成可视线模块，用于将所述虚拟连线穿过的每一个障碍物的所有顶点、所述起点和所述目标点之间进行直线连接，并保留所有可视线，其中，所述可视线为不穿过任何障碍物的线段；所述形成候选路径模块，用于将每一条被保留的可视线进行连通，以形成候选路径；所述确定行驶路径模块，用于计算每一条所述候选路径的长度，确定长度最短的候选路径为智能导购车的行驶路径。 Wherein, the module for determining the start and end points is used to determine the starting point and target point of the intelligent shopping guide; the module for forming a virtual line is used to connect the starting point and the target point through a straight line in the space environment, The virtual connection in the obtained space; the forming visible line module is used to connect all vertices of each obstacle passed by the virtual connection, the starting point and the target point with a straight line, and Reserving all visible lines, wherein, the visible lines are line segments that do not pass through any obstacles; the forming candidate path module is used to connect each reserved visible line to form a candidate path; the determining driving The route module is used to calculate the length of each candidate route, and determine the candidate route with the shortest length as the driving route of the intelligent shopping guide vehicle. the
在上述方案中，可选的，所述确定行驶路径模块，具体用于：通过迪杰斯特拉算法、贝尔曼-福特算法、普利姆算法或弗洛伊德算法计算每一条所述候选路径的长度。 In the above solution, optionally, the module for determining the driving route is specifically configured to: calculate each of the candidate items by using the Dijkstra algorithm, the Bellman-Ford algorithm, the Prim algorithm or the Floyd algorithm. The length of the path. the
可选的，本发明实施例提供的智能导购车行驶路径的规划装置，还包括：确定模块，用于对确定的所述行驶路径进行加宽处理，并在所述行驶路径在设置均匀的子目标点。 Optionally, the device for planning travel paths of intelligent shopping guide vehicles provided in the embodiments of the present invention further includes: a determination module, configured to widen the determined travel paths, and set uniform sub-sections on the travel paths. Target. the
本实施例提供的智能导购车行驶路径的规划装置，通过确定起止点模块确定智能导购车的起点和目标点，通过形成虚拟连线模块在空间环境中将所述起点与所述目标点通过一条直线进行连接，得到的空间中的虚拟连线；通过形成可视线模块将所述虚拟连线穿过的每一个障碍物的所有顶点、所述起点和所述目标点之间进行直线连接，并保留所有可视线，通过形成候选路径模块将每一条被保留的可视线进行连通，以形成候选路径，通过确定行驶路径模块计算每一条所述候选路径的长度，确定长度最短的候选路径为智能导购车的行驶路径，本发明针对商场、超市等购物场所具有对称性的结构特点，更具适用行，本发明能够减小规划行驶路径过程中的计算量，提高智能导购车行驶路径的规划效率，进而降低设备成本。并且本发明实施例提供的确定模块能够对确定的行驶路径进行加宽处理，并在行驶路径在设置均匀的子目标点，能够针对超市等局部人流复杂的状况，保证无碰的同时解决传统避障算法的“迷失”问题，整体提高了智能导购车的可用性。 The planning device for the driving path of the intelligent shopping guide vehicle provided in this embodiment determines the starting point and the target point of the intelligent shopping guide vehicle through the module of determining the start and end points, and passes the starting point and the target point through a line in the space environment by forming a virtual connection module. Straight line is connected, and the virtual connection in the space that obtains; By forming visible line module, carry out straight line connection between all vertices of each obstacle that described virtual connection passes through, described starting point and described target point, and Reserving all visible lines, connecting each reserved visible line by forming a candidate path module to form a candidate path, calculating the length of each candidate path by determining the driving path module, and determining the candidate path with the shortest length as an intelligent shopping guide The driving path of the car, the present invention has symmetrical structural characteristics for shopping malls, supermarkets and other shopping places, and is more applicable. The present invention can reduce the amount of calculation in the process of planning the driving path, and improve the planning efficiency of the driving path of the intelligent shopping guide car. Thereby reducing equipment cost. Moreover, the determination module provided by the embodiment of the present invention can widen the determined driving path, and set uniform sub-target points on the driving path, which can solve the problem of traditional avoidance problems while ensuring no-collision for the complex situation of local crowd flow in supermarkets and the like. The "lost" problem of the obstacle algorithm has improved the usability of the smart shopping guide car as a whole. the
本发明实施例还提供一种智能导购车，所述智能导购车包括本发明任意实施例提供的智能导购车行驶路径的规划装置。 An embodiment of the present invention also provides a smart shopping guide car, which includes the device for planning a driving path of the smart shopping guide car provided in any embodiment of the present invention. the
最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。 Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than limiting them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: It is still possible to modify the technical solutions described in the foregoing embodiments, or perform equivalent replacements for some or all of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the technical solutions of the various embodiments of the present invention. scope. the
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201410324284.XACN104102219B (en) | 2014-07-09 | 2014-07-09 | Planning method and device for driving route of intelligent shopping guide vehicle and intelligent shopping guide vehicle |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201410324284.XACN104102219B (en) | 2014-07-09 | 2014-07-09 | Planning method and device for driving route of intelligent shopping guide vehicle and intelligent shopping guide vehicle |
| Publication Number | Publication Date |
|---|---|
| CN104102219Atrue CN104102219A (en) | 2014-10-15 |
| CN104102219B CN104102219B (en) | 2017-01-11 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201410324284.XAExpired - Fee RelatedCN104102219B (en) | 2014-07-09 | 2014-07-09 | Planning method and device for driving route of intelligent shopping guide vehicle and intelligent shopping guide vehicle |
| Country | Link |
|---|---|
| CN (1) | CN104102219B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104407613A (en)* | 2014-10-20 | 2015-03-11 | 河南工业职业技术学院 | Obstacle avoidance path smooth optimization method |
| US9534906B2 (en) | 2015-03-06 | 2017-01-03 | Wal-Mart Stores, Inc. | Shopping space mapping systems, devices and methods |
| CN106934388A (en)* | 2017-04-12 | 2017-07-07 | 无锡北斗星通信息科技有限公司 | Market go-cart feed system based on image procossing |
| US10017322B2 (en) | 2016-04-01 | 2018-07-10 | Wal-Mart Stores, Inc. | Systems and methods for moving pallets via unmanned motorized unit-guided forklifts |
| CN108512880A (en)* | 2017-02-28 | 2018-09-07 | 上海诺基亚贝尔股份有限公司 | Communication means and communication equipment |
| WO2018195932A1 (en)* | 2017-04-28 | 2018-11-01 | 深圳市元征科技股份有限公司 | Supermarket shopping cart control method and apparatus |
| CN109211258A (en)* | 2018-09-13 | 2019-01-15 | 上海宇佑船舶科技有限公司 | A kind of plane display mirror can be realized route planning |
| US10346794B2 (en) | 2015-03-06 | 2019-07-09 | Walmart Apollo, Llc | Item monitoring system and method |
| CN110018689A (en)* | 2019-05-15 | 2019-07-16 | 福州大学 | A kind of more virtual target point overall situation active path planning algorithms based on dynamic window |
| CN110044004A (en)* | 2019-04-25 | 2019-07-23 | 宁波奥克斯电气股份有限公司 | Mobile air conditioner intelligent drainage function control method, drain control unit and mobile air conditioner |
| US11046562B2 (en) | 2015-03-06 | 2021-06-29 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| CN113791610A (en)* | 2021-07-30 | 2021-12-14 | 河南科技大学 | Global path planning method for mobile robot |
| CN114690755A (en)* | 2020-12-25 | 2022-07-01 | 尚科宁家(中国)科技有限公司 | Cleaning robot and obstacle detouring method thereof |
| US12084824B2 (en) | 2015-03-06 | 2024-09-10 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| US12366043B2 (en) | 2015-03-06 | 2025-07-22 | Walmart Apollo, Llc | Overriding control of motorized transport unit systems, devices and methods |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101231714A (en)* | 2007-12-05 | 2008-07-30 | 中原工学院 | 3D Path Planning Method for Robot |
| US8482565B2 (en)* | 2009-05-15 | 2013-07-09 | Microsoft Corporation | Interactive connector routing between obstacles |
| US8543944B2 (en)* | 2010-06-14 | 2013-09-24 | Microsoft Corporation | Fast edge routing for interactive diagramming |
| CN103529843A (en)* | 2013-10-17 | 2014-01-22 | 电子科技大学中山学院 | Lambda path planning algorithm |
| CN103576680A (en)* | 2012-07-25 | 2014-02-12 | 中国原子能科学研究院 | Robot path planning method and device |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101231714A (en)* | 2007-12-05 | 2008-07-30 | 中原工学院 | 3D Path Planning Method for Robot |
| US8482565B2 (en)* | 2009-05-15 | 2013-07-09 | Microsoft Corporation | Interactive connector routing between obstacles |
| US8543944B2 (en)* | 2010-06-14 | 2013-09-24 | Microsoft Corporation | Fast edge routing for interactive diagramming |
| CN103576680A (en)* | 2012-07-25 | 2014-02-12 | 中国原子能科学研究院 | Robot path planning method and device |
| CN103529843A (en)* | 2013-10-17 | 2014-01-22 | 电子科技大学中山学院 | Lambda path planning algorithm |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104407613B (en)* | 2014-10-20 | 2017-03-22 | 河南工业职业技术学院 | Obstacle avoidance path smooth optimization method |
| CN104407613A (en)* | 2014-10-20 | 2015-03-11 | 河南工业职业技术学院 | Obstacle avoidance path smooth optimization method |
| US10336592B2 (en) | 2015-03-06 | 2019-07-02 | Walmart Apollo, Llc | Shopping facility assistance systems, devices, and methods to facilitate returning items to their respective departments |
| US10815104B2 (en) | 2015-03-06 | 2020-10-27 | Walmart Apollo, Llc | Recharging apparatus and method |
| US9757002B2 (en) | 2015-03-06 | 2017-09-12 | Wal-Mart Stores, Inc. | Shopping facility assistance systems, devices and methods that employ voice input |
| US9801517B2 (en) | 2015-03-06 | 2017-10-31 | Wal-Mart Stores, Inc. | Shopping facility assistance object detection systems, devices and methods |
| US9875502B2 (en) | 2015-03-06 | 2018-01-23 | Wal-Mart Stores, Inc. | Shopping facility assistance systems, devices, and methods to identify security and safety anomalies |
| US9875503B2 (en) | 2015-03-06 | 2018-01-23 | Wal-Mart Stores, Inc. | Method and apparatus for transporting a plurality of stacked motorized transport units |
| US9896315B2 (en) | 2015-03-06 | 2018-02-20 | Wal-Mart Stores, Inc. | Systems, devices and methods of controlling motorized transport units in fulfilling product orders |
| US9908760B2 (en) | 2015-03-06 | 2018-03-06 | Wal-Mart Stores, Inc. | Shopping facility assistance systems, devices and methods to drive movable item containers |
| US9994434B2 (en) | 2015-03-06 | 2018-06-12 | Wal-Mart Stores, Inc. | Overriding control of motorize transport unit systems, devices and methods |
| US12366043B2 (en) | 2015-03-06 | 2025-07-22 | Walmart Apollo, Llc | Overriding control of motorized transport unit systems, devices and methods |
| US12123155B2 (en) | 2015-03-06 | 2024-10-22 | Walmart Apollo, Llc | Apparatus and method of monitoring product placement within a shopping facility |
| US10071891B2 (en) | 2015-03-06 | 2018-09-11 | Walmart Apollo, Llc | Systems, devices, and methods for providing passenger transport |
| US10071893B2 (en) | 2015-03-06 | 2018-09-11 | Walmart Apollo, Llc | Shopping facility assistance system and method to retrieve in-store abandoned mobile item containers |
| US10071892B2 (en) | 2015-03-06 | 2018-09-11 | Walmart Apollo, Llc | Apparatus and method of obtaining location information of a motorized transport unit |
| US10081525B2 (en) | 2015-03-06 | 2018-09-25 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods to address ground and weather conditions |
| US12084824B2 (en) | 2015-03-06 | 2024-09-10 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| US10130232B2 (en) | 2015-03-06 | 2018-11-20 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| US10138100B2 (en) | 2015-03-06 | 2018-11-27 | Walmart Apollo, Llc | Recharging apparatus and method |
| US10351400B2 (en) | 2015-03-06 | 2019-07-16 | Walmart Apollo, Llc | Apparatus and method of obtaining location information of a motorized transport unit |
| US10189691B2 (en) | 2015-03-06 | 2019-01-29 | Walmart Apollo, Llc | Shopping facility track system and method of routing motorized transport units |
| US10189692B2 (en) | 2015-03-06 | 2019-01-29 | Walmart Apollo, Llc | Systems, devices and methods for restoring shopping space conditions |
| US11840814B2 (en) | 2015-03-06 | 2023-12-12 | Walmart Apollo, Llc | Overriding control of motorized transport unit systems, devices and methods |
| US10239740B2 (en) | 2015-03-06 | 2019-03-26 | Walmart Apollo, Llc | Shopping facility assistance system and method having a motorized transport unit that selectively leads or follows a user within a shopping facility |
| US10239739B2 (en) | 2015-03-06 | 2019-03-26 | Walmart Apollo, Llc | Motorized transport unit worker support systems and methods |
| US10239738B2 (en) | 2015-03-06 | 2019-03-26 | Walmart Apollo, Llc | Apparatus and method of monitoring product placement within a shopping facility |
| US10280054B2 (en) | 2015-03-06 | 2019-05-07 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| US10287149B2 (en) | 2015-03-06 | 2019-05-14 | Walmart Apollo, Llc | Assignment of a motorized personal assistance apparatus |
| US10315897B2 (en) | 2015-03-06 | 2019-06-11 | Walmart Apollo, Llc | Systems, devices and methods for determining item availability in a shopping space |
| US11761160B2 (en) | 2015-03-06 | 2023-09-19 | Walmart Apollo, Llc | Apparatus and method of monitoring product placement within a shopping facility |
| US10570000B2 (en) | 2015-03-06 | 2020-02-25 | Walmart Apollo, Llc | Shopping facility assistance object detection systems, devices and methods |
| US11679969B2 (en) | 2015-03-06 | 2023-06-20 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| US11046562B2 (en) | 2015-03-06 | 2021-06-29 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| US10351399B2 (en) | 2015-03-06 | 2019-07-16 | Walmart Apollo, Llc | Systems, devices and methods of controlling motorized transport units in fulfilling product orders |
| US11034563B2 (en) | 2015-03-06 | 2021-06-15 | Walmart Apollo, Llc | Apparatus and method of monitoring product placement within a shopping facility |
| US10358326B2 (en) | 2015-03-06 | 2019-07-23 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods |
| US10435279B2 (en) | 2015-03-06 | 2019-10-08 | Walmart Apollo, Llc | Shopping space route guidance systems, devices and methods |
| US10486951B2 (en) | 2015-03-06 | 2019-11-26 | Walmart Apollo, Llc | Trash can monitoring systems and methods |
| US10508010B2 (en) | 2015-03-06 | 2019-12-17 | Walmart Apollo, Llc | Shopping facility discarded item sorting systems, devices and methods |
| US10346794B2 (en) | 2015-03-06 | 2019-07-09 | Walmart Apollo, Llc | Item monitoring system and method |
| US10597270B2 (en) | 2015-03-06 | 2020-03-24 | Walmart Apollo, Llc | Shopping facility track system and method of routing motorized transport units |
| US10611614B2 (en) | 2015-03-06 | 2020-04-07 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods to drive movable item containers |
| US10633231B2 (en) | 2015-03-06 | 2020-04-28 | Walmart Apollo, Llc | Apparatus and method of monitoring product placement within a shopping facility |
| US10669140B2 (en) | 2015-03-06 | 2020-06-02 | Walmart Apollo, Llc | Shopping facility assistance systems, devices and methods to detect and handle incorrectly placed items |
| US10875752B2 (en) | 2015-03-06 | 2020-12-29 | Walmart Apollo, Llc | Systems, devices and methods of providing customer support in locating products |
| US9534906B2 (en) | 2015-03-06 | 2017-01-03 | Wal-Mart Stores, Inc. | Shopping space mapping systems, devices and methods |
| US10017322B2 (en) | 2016-04-01 | 2018-07-10 | Wal-Mart Stores, Inc. | Systems and methods for moving pallets via unmanned motorized unit-guided forklifts |
| US10214400B2 (en) | 2016-04-01 | 2019-02-26 | Walmart Apollo, Llc | Systems and methods for moving pallets via unmanned motorized unit-guided forklifts |
| CN108512880A (en)* | 2017-02-28 | 2018-09-07 | 上海诺基亚贝尔股份有限公司 | Communication means and communication equipment |
| CN106934388A (en)* | 2017-04-12 | 2017-07-07 | 无锡北斗星通信息科技有限公司 | Market go-cart feed system based on image procossing |
| WO2018195932A1 (en)* | 2017-04-28 | 2018-11-01 | 深圳市元征科技股份有限公司 | Supermarket shopping cart control method and apparatus |
| CN109211258A (en)* | 2018-09-13 | 2019-01-15 | 上海宇佑船舶科技有限公司 | A kind of plane display mirror can be realized route planning |
| CN110044004A (en)* | 2019-04-25 | 2019-07-23 | 宁波奥克斯电气股份有限公司 | Mobile air conditioner intelligent drainage function control method, drain control unit and mobile air conditioner |
| CN110018689A (en)* | 2019-05-15 | 2019-07-16 | 福州大学 | A kind of more virtual target point overall situation active path planning algorithms based on dynamic window |
| CN110018689B (en)* | 2019-05-15 | 2020-07-07 | 福州大学 | Dynamic window-based multi-virtual target point global dynamic path planning algorithm |
| CN114690755B (en)* | 2020-12-25 | 2025-05-20 | 尚科宁家(中国)科技有限公司 | Cleaning robot and obstacle avoidance method thereof |
| CN114690755A (en)* | 2020-12-25 | 2022-07-01 | 尚科宁家(中国)科技有限公司 | Cleaning robot and obstacle detouring method thereof |
| CN113791610B (en)* | 2021-07-30 | 2024-04-26 | 河南科技大学 | Global path planning method for mobile robot |
| CN113791610A (en)* | 2021-07-30 | 2021-12-14 | 河南科技大学 | Global path planning method for mobile robot |
| Publication number | Publication date |
|---|---|
| CN104102219B (en) | 2017-01-11 |
| Publication | Publication Date | Title |
|---|---|---|
| CN104102219B (en) | Planning method and device for driving route of intelligent shopping guide vehicle and intelligent shopping guide vehicle | |
| KR102624371B1 (en) | Extended object tracking using radar | |
| CN106041931B (en) | A kind of robot cooperated anticollision method for optimizing route of the more AGV of more space with obstacle | |
| CN106461768B (en) | System and method for localization, mapping and data management by using crowdsourcing | |
| JP7330142B2 (en) | Method, Apparatus, Device and Medium for Determining Vehicle U-Turn Path | |
| KR101465493B1 (en) | Navigation system for vehicle and route determining method for destination of vehicle | |
| CN105208616B (en) | Adaptive more copy method for routing based on road topology in vehicular ad hoc network | |
| CN104914862B (en) | Path Planning Algorithm Based on Target Direction Constraint | |
| JP2019529209A (en) | System, method and non-transitory computer readable storage medium for parking a vehicle | |
| US20140207376A1 (en) | Computer-implemented systems and methods for planning a route | |
| CN109131318A (en) | A kind of autonomous parking path coordination approach based on topological map | |
| KR20180047210A (en) | Apparatus and method for detecting parking slot | |
| Antsfeld et al. | Finding multi-criteria optimal paths in multi-modal public transportation networks using the transit algorithm | |
| CN103344248B (en) | A Calculation Method of Optimal Route for Vehicle Navigation System | |
| CA2949867A1 (en) | Route generation program, route generation method and route generation apparatus | |
| CN106228819A (en) | The traffic signal optimization control method of a kind of multi-intersection and device | |
| CN103529843A (en) | Lambda path planning algorithm | |
| CN107837044A (en) | Subregion clean method, device and the robot of clean robot | |
| CN109115220B (en) | A method for path planning of parking lot systems | |
| US20160153787A1 (en) | Method and system for division of road network | |
| CN114115292A (en) | Travel control method, system, storage medium, and computer device | |
| EP4332713A1 (en) | Obstacle avoidance method and apparatus for automatic walking device, medium, and electronic device | |
| CN114264313B (en) | Potential energy-based lane-level path planning method, system, equipment and storage medium | |
| CN115562272A (en) | Method and device for planning robot travel path | |
| CN115716482A (en) | U-turn trajectory planning method, device, equipment and storage medium |
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee | Granted publication date:20170111 Termination date:20190709 |