TW202501192A - Path Generation System - Google Patents

Abstract

The path generation system includes: a controller that generates a path for the transport vehicle to travel from a departure point to a destination in a travel area. The controller sets a plurality of points in the travel area to be divided into three or more first blocks and a second block connected to the first block, extracts points included in the transport departure block, the transport destination block, and the second block, the transport departure block being one first block to which the departure point belongs among the first blocks, and the transport destination block being one first block to which the destination belongs among the first blocks, and generates a path from the extracted points.

Description

Path Generation System

The present disclosure relates to a path generation system for generating a travel path of a transport vehicle.

In the past, a route planning device and a transport system that can create a route plan in a short time are known. The route plan is to minimize the total transport time or total transport distance of a plurality of automated guided vehicles (AGVs) when they travel from an initial location to a transport destination location (destination) (for example, refer to Patent Document 1). [Prior Art Document] [Patent Document]

[Patent Document 1] Japanese Patent No. 4138541

[The problem the invention is trying to solve]

The above-mentioned conventional system creates all the transporter route plans in a short calculation time. When the travel area is expanded, the calculation of the route plan becomes huge. In the previous system, this point was not taken into account. The route plan in a wide travel area requires a huge calculation load. Depending on the situation, the memory volume used for path exploration may reach the upper limit of the available memory volume, making the generation of the path impossible.

This disclosure is to describe a path generation system that can reduce the load required for path generation even in a wide walking area. [Technical means for solving the problem]

One aspect of the present disclosure is a path generation system for generating a path for one or more transport vehicles to travel from a starting point to a destination in a travel area, and the system comprises: a controller for generating a path for the transport vehicle to travel, wherein the travel area has: a plurality of points where the transport vehicle can pass and stop, and the controller sets the plurality of points to be divided into three or more first blocks and a second block connected to the first block, and extracts points included in a transport departure block, a transport destination block, and a second block, wherein the transport departure block is a first block to which the departure point belongs among the first blocks, and the transport destination block is a first block to which the destination belongs among the first blocks, and generates a path from the extracted points.

According to the path generation system, the controller is set to divide the first block into three or more and the second block connected to the first blocks. That is, a plurality of points in the walking area belong to any one of the blocks. The controller extracts the points included in the transport departure block and the transport destination block and the second block in the three or more first blocks, and generates a path from the points. In this way, the area (point) explored by the controller when generating the path is not the entire walking area (all points) but is limited (restricted) to a part. In this way, the load required for path generation can be reduced even in a wide walking area.

The second block may be set to include a point with a high passing frequency based on the simulation of the full transport mode. In this case, the second block may be appropriately set based on the actual environment.

Alternatively, the controller may set the second block individually for each of the paths traveled by the plurality of transport vehicles. By changing the second block according to the transport vehicle, the frequency of interference between transport vehicles can be reduced.

Alternatively, an upper limit may be set for the number of points contained in each of the first blocks. In this case, the number of regions (points) to be explored by the controller during path generation is reduced, thereby further reducing the load required for path generation.

Alternatively, at least one point among a plurality of points in the walking area is connected to no more than three paths, and the second block includes the at least one point.

Alternatively, the second block may include: a plurality of points connected to four or more paths, respectively. [Effect of the invention]

According to the present disclosure, the load required to generate the path can be reduced even in a wide walking area.

Hereinafter, the embodiments of the present disclosure will be described with reference to the drawings. In the description of the drawings, the same elements are given the same symbols and repeated descriptions are omitted.

First, referring to FIG. 1 , an unmanned transport vehicle system 1 using a path generation system 6 (see FIG. 3 ) of the present embodiment will be described. As shown in FIG. 1 , the unmanned transport vehicle system 1 is a transport system that performs, for example, transporting items within a building 100 . The unmanned transport vehicle system 1 includes: a plurality of unmanned transport vehicles 10 for transporting items, and a walking area A where the unmanned transport vehicles 10 travel. In the example shown in FIG. 1 , the building 100 is provided with: for example, three processing devices (a first processing device 31 , a second processing device 32 , and a third processing device 33 ), a carry-out station 34 , and a carry-in station 35 . The walking area A is provided in an area other than the first processing device 31 to the third processing device 3 , the carry-out station 34 , and the carry-in station 35 . Articles handled in the robot system 1 are not particularly limited as long as they are parts or commodities that can be transported by each robot 10. Hereinafter, the robot system 1 is referred to as "robot system 1" and the robot 10 is referred to as "robot 10".

In the transport vehicle system 1, the first processing device 31 to the third processing device 3, the unloading station 34 and the loading station 35 are respectively arranged so that the articles can be transferred by the transport vehicle 10 traveling along a predetermined path in the walking area A. The transport vehicle system 1 may have: one or more automatic warehouses (not shown) for storing a plurality of articles. The automatic warehouse may have: a storage shelf that can carry a plurality of articles, a forklift crane that transfers the articles to the storage shelf, and a plurality of entry and exit ports (all not shown) that can transfer the articles by the transport vehicle 10. The number and arrangement of the processing devices and the walking area A can be freely determined and are not limited to the example shown in FIG. 1.

The transport vehicle 10 autonomously travels along a pre-set path 2. The transport vehicle 10 is, for example, an AGV (Automated Guided Vehicle).

Referring to Figures 2(a) and 2(b), the structure of the walking area A is explained. The walking area A is an area that is two-dimensionally developed on the floor surface (walking surface), and is an area where each transport vehicle 10 can walk. The walking area A has: a plurality of points P where each transport vehicle 10 can pass and stop, and a plurality of sections (passages) S that are set between these points P (in detail, between two adjacent points P) and are used to connect these points P. In order to allow the walking control unit 15 of each transport vehicle 10 to detect the position of the vehicle, a barcode or a two-dimensional code may be provided at each point P. Each transport vehicle 10 has a reading device (not shown). When a two-dimensional code is provided, each transport vehicle 10 detects the position of the vehicle by reading information from the two-dimensional code. The two-dimensional code may contain information for determining the direction. Alternatively, the two-dimensional code may not contain information for determining the direction, and each transport vehicle 10 may have a direction detection means such as a compass for determining the direction of the vehicle (the direction of travel).

The transport vehicle 10 may also move while detecting magnetic signals outputted from a magnetic tape or a magnetic marker. Alternatively, the transport vehicle 10 may generate light from a laser or the like, and move while detecting its own position by detecting reflected light reflected by a reflector mounted on a wall of a building. The transport vehicle 10 may also move while detecting its own position using information from GPS or the like. As a navigation method for the transport vehicle 10, SLAM (Simultaneous Localization and Mapping) technology may be used. The transport vehicle system 1 may be provided with: a charging point or charging station for supplying power to the transport vehicle 10.

Each straight line section S represented by a dotted line in the figure has a length equivalent to the distance (pitch) between two points P, that is, the interval length. The interval length of each section S may be constant or not constant in the travel area A. The interval length of a part of the section S may be longer than the (average) interval length of many other sections S, or vice versa. In the transport vehicle system 1, in order to achieve stable travel, for example, an upper limit is set for the length of the section S, that is, the interval length. The upper limit of the interval length is, for example, about 1000 mm to 3000 mm.

As shown in FIG2(b), as information required for exploring and generating the travel path of the transport vehicle 10, each point P is associated with the spin turn time (seconds). The spin turn time (seconds) is a time (spin time) set for the following two situations: the situation where the transport vehicle 10 stops at point P and rotates 90 degrees on the spot, and the situation where it rotates 180 degrees on the spot. Each road section S is associated with the interval length (mm) and the travel speed (mm/second). Based on these two pieces of information, the time (travel time) that the transport vehicle 10 spends traveling on the road section S is calculated. These rotation times and travel times are indicators used by the path generation unit 14 described later to perform path exploration processing, and are "costs" from another perspective. Each point P can also be called a "stop point".

As shown in FIG3 , the transport vehicle system 1 includes a path generation system 6 that generates a travel path R for each of the plurality of transport vehicles 10 to travel _from a starting point P from to a destination P _to in a travel area A. The starting point P _from and the destination P _to are any two points P in the travel area A.

As shown in FIG. 3 , the path generation system 6 includes: a plurality of transport vehicles 10 for transporting articles, a transport vehicle controller 20 for controlling the plurality of transport vehicles 10 , and a host controller 5 for issuing transport requests to the transport vehicle controller 20 .

When a transport instruction (described later) is assigned to the transport vehicle 10 from the transport vehicle controller 20, the transport vehicle 10 performs travel control and loading and unloading control for transporting articles from the departure point P _from to the destination P _to . In the path generation system 6, the transport vehicle controller 20 and the transport vehicle 10 cooperate to generate a travel path R from the departure point P _from to the destination P _to. That is, the function of the controller for generating the travel path R is distributed to the transport vehicle controller 20 and the transport vehicle 10. In the loading and unloading control, the transport vehicle 10 is loaded from each processing device or transfer station and unloaded from the transport vehicle 10 to each processing device or transfer station by raising and lowering the elevator of the transport vehicle 10.

The transport vehicle controller 20 is a control device for managing a plurality of transport vehicles 10. The transport vehicle controller 20 is a computer having: a ROM (Read Only Memory) storing programs, a RAM (Random Access Memory) storing data temporarily, a storage medium such as an HDD (Hard Disk Drive), a processor such as a CPU (Central Processing Unit), and a communication circuit such as a wireless LAN. The transport vehicle controller 20 can be configured in the form of software, which loads a program stored in the ROM into the RAM and is executed by the CPU. The transport vehicle controller 20 can also be configured in the form of hardware using electronic circuits, etc. The transport vehicle controller 20 can be configured by one device or by a plurality of devices. In the case where a plurality of devices are used, they are connected via a communication network such as the Internet or an intranet to logically construct a single transport vehicle controller 20.

The transport vehicle controller 20 is connected to the transport vehicle 10 and the upper controller 5 by wire or wireless. The transport vehicle controller 20 receives information related to the current position and current speed of the transport vehicle 10 from the transport vehicle 10. The transport vehicle controller 20 receives a transport request for transporting items from a certain processing device to another processing device from the upper controller 5. The transport request is generated, for example, when the item arrives at the front end of the outbound conveyor, or when the item arrives at the delivery station after being processed by the upstream equipment. The transport vehicle controller 20 generates a transport instruction according to the received transport request and distributes the transport instruction to the transport vehicle 10.

The transport instruction is a control instruction for transporting an object from a transport departure station to a transport destination station by means of the transport vehicle 10. The transport instruction includes information on the transport of an object at the transport departure station, the movement along the path 2 from the transport departure station to the transport destination station, and the transport of an object at the transport destination station.

As shown in FIG3 , the transport vehicle controller 20 includes: a transport request receiving unit 21, an information acquisition unit 23, a first block setting unit 24, an allocation determination unit 25, and a memory unit 27. The transport request receiving unit 21 receives a transport request from the upper controller 5, and generates a transport instruction according to the received transport request. The information acquisition unit 23 acquires information related to the walking area A, and acquires information related to the walking status of all transport vehicles 10. The allocation determination unit 25 allocates the transport request to a transport vehicle 10 that has no other transport request being executed, that is, an empty transport vehicle (empty unmanned transport vehicle). The first block setting unit 24 will be described later. The memory unit 27 stores information related to the divided blocks B1a to B1e (first block; see FIG. 4 ) set by the first block setting unit 24 for the walking area A.

The transport vehicle 10 has a transport instruction receiving unit 11, an area information acquiring unit 12, a second area setting unit 13, a path generating unit 14, and a travel control unit 15 as functions related to the travel control of the vehicle. The transport instruction receiving unit 11, the area information acquiring unit 12, the second area setting unit 13, the path generating unit 14, and the travel control unit 15 are all composed of a storage medium such as ROM, RAM, HDD, a processor such as CPU, and a communication circuit such as a wireless LAN. The transport instruction receiving unit 11 receives a transport instruction sent from the allocation determining unit 25 of the transport vehicle controller 20. The area information acquiring unit 12 acquires information related to the travel area A. The information acquired by the information acquisition unit 23 of the transport vehicle controller 20 and the area information acquisition unit 12 of the transport vehicle 10 includes information related to the above-mentioned points P and sections S. The second block setting unit 13 will be described later. The path generation unit 14 generates the travel path R of the vehicle based on the divided blocks B1a to B1e set by the first block setting unit 24 and the shared block B2 set by the second block setting unit 13.

Next, the setting of each block and the generation of the travel path R in the path generation system 6 will be described with reference to Fig. 3, Fig. 4 and Fig. 5. In the path generation system 6, when generating the travel path R of each transport vehicle 10 to perform the transport request, not all points P in the travel area A are used as the object of path exploration, but only a part of the points P are used as the object of path exploration.

As shown in FIG. 3 and FIG. 4 , the first block setting unit 24 of the transport vehicle controller 20 is to set all points P in the walking area A to be divided into three or more divided blocks B1a~B1e. For example, there are five divided blocks B1a~B1e in the manner of dividing the walking area A. For example, an upper limit is set for the number of points P contained in each divided block B1a~B1e. The upper limit number of points P that each divided block 1 can contain can be set to, for example, less than 50, less than 100, or less than 200. It can be determined according to the scale of the walking area A. The upper limit number can be determined according to the computing power or performance of the memory of the transport vehicle controller 20, etc. The number of partitions is not particularly limited, and in the example shown in FIG4 , the partitions are set so that the number of points P contained in each partition is about 9 to 17. For example, a plurality of partitions may be set such that the plurality of points existing around the carrying-in station and carrying-out station of each processing device are used as a reference and belong to one partition.

The second block setting unit 13 of the transport vehicle 10 sets a common block (second block) B2 to include a point P with a high passing frequency based on the simulation of the full transport mode as a preliminary preparation for the path generation unit 14 to generate the travel path R. The common block B2 is connected to the divided blocks B1a to B1e through a plurality of road sections S.

Furthermore, the first block setting unit 24 of the transport vehicle controller 20 can set the divided blocks B1a to B1e by dividing the area other than the shared block B2 after the second block setting unit 13 sets the shared block B2. The divided blocks (first blocks) and the shared block (second blocks) are set separately.

FIG4 shows the block setting X1 of the present embodiment. As shown in FIG4, in the current transport instruction (transport request), the numbers 3000 to 3100 are assigned to the points P included in the common block B2. Furthermore, the numbers other than 3000 to 3100 are assigned to the points P included in the divided blocks B1a to B1e. For example, the numbers 3201 to 3300 are assigned to the divided block B1a, the numbers 3301 to 3500 are assigned to the divided block B1b, the numbers 3501 to 3700 are assigned to the divided block B1c, the numbers 3701 to 3900 are assigned to the divided block B1d, and the numbers 3901 to 4100 are assigned to the divided block B1e.

As shown in FIG4 , the shared block B2 includes: a plurality of points P connected to only 3 or fewer road segments S. In particular, in the present embodiment, the shared block B2 includes only: a plurality of points P connected to only 3 or fewer road segments S. For example, the shared block B2 includes: a first type of point P1 connected to only 1 road segment S, a second type of point P2 connected to only 2 road segments S, and a third type of point P3 connected to only 3 road segments S. The shared block B2 is set as an area that must be passed through in order to travel between different divided blocks.

As shown in FIG5 , the path generation unit 14 of the transport vehicle 10 extracts the segment block B1b (transportation departure block) to which the departure point P _from (No. 3304) belongs, the segment block B1e (transportation destination block) to which the destination P _to (No. 4001) belongs, and the point P contained in the shared block B from the segment blocks B1a to B1e, and generates a travel path R from these points. The path generation unit 14 uses a well-known method such as Dijkstra's algorithm as a path search algorithm to find the shortest path. The shortest path is always found according to the Dijkstra's algorithm. The segment blocks other than these are not used for path search (considered as non-existent).

As a result of the route search, the route generation unit 14 generates a travel route R indicated by a bold arrow in Fig. 5. The travel route R includes a transport origin route R1b generated in the divided block B1b, a shared route R2 generated in the shared block B2, and a transport destination route R1e generated in the divided block B1e.

Furthermore, the setting of three or more divided blocks (first blocks) and the setting of one or more shared blocks (second blocks) can also be performed offline when the map data is created.

The travel control unit 15 allows the transport vehicle 10 to travel according to the travel path R generated by the path generation unit 14.

According to the transport vehicle system 1 and the path generation system 6 of the present embodiment, the first block setting unit 24 sets three or more divided blocks B1a to B1e, and the second block setting unit 13 sets the shared block B2. That is, all points P in the travel area A belong _to any one of the blocks. The path generation unit 14 extracts the points P included in the divided block B1b (transportation departure block) to which the departure point P _from belongs, the divided block B1e (transportation destination block) to which the destination P to belongs, and the shared block B, and generates a travel path R from these points. In this way, the area (point P) explored by the path generation unit 14 when generating the path is not the entire (all points) of the travel area A but is limited (restricted) to a part. In this way, even in a wide travel area A, the load required for path generation can be reduced.

The shared area B2 is set to include the point P with a high passing frequency based on the simulation of the full transport pattern. In this way, the shared area B2 can be appropriately set according to the actual environment.

The second block setting unit 13 sets a shared block B2 for each of the travel paths R traveled by the transport vehicles 10. By changing the shared block B2 according to the transport vehicles 10, the frequency of interference between the transport vehicles 10 can be reduced.

An upper limit is set for the number of points P included in each of the divided blocks B1a to B1e. In this way, the number of areas (points P) to be searched by the path generation unit 14 during path generation is reduced, thereby further reducing the load required for path generation.

The above is an explanation of the embodiments of the present disclosure, but the present invention is not limited to the embodiments. For example, according to the structure of the walking area A (the number and arrangement of points P, the number, length and arrangement of road sections S), and the size (scale) of the walking area A, more than three divided blocks (first blocks) and one or more shared blocks (second blocks) can be set in different ways.

For example, as shown in the block setting X2 in FIG. 6 , a shared block B2 may be set in which the five divided blocks B1a to B1e are connected to each other in an L-shaped block shape. In this case, the shared block B2 includes: a plurality of points P connected to four or more road sections S. Alternatively, a certain transport vehicle 10 may set such a shared block B2, while other transport vehicles 10 may set other shared blocks (for example, blocks that are offset from the shared block B2 in FIG. 6 ). In the figures below FIG. 6 , the point P is omitted, and the position of the point P is expressed as a grid point.

Alternatively, as in block setting X3 shown in FIG7(a), four partitioned blocks B1a to B1d may be connected by a common block B2. Alternatively, as in block setting X4 shown in FIG7(b), four partitioned blocks B1a to B1d may be connected by a cross-shaped common block B2. Alternatively, as in block setting X5 shown in FIG8(a), block settings X3 and X4 may be combined to connect each partitioned block to all other partitioned blocks with common blocks B2a and B2b. Alternatively, as in block setting X6 shown in FIG8(b), only a portion of the partitioned blocks may be connected to all other partitioned blocks with common blocks B2a and B2b.

As in the block setting X7 shown in FIG. 9 , the divided blocks B1a and B1b may be connected by the shared block B2a, which serves as a base and the four divided blocks B1c to B1f may be connected by the shared block B2b.

In the above-mentioned embodiment, the description is made of a mode in which the transport vehicle controller 20 and the transport vehicle 10 cooperate to generate the travel path R _from the departure point P from to the destination P _to . However, the travel path R may be generated only by the transport vehicle controller 20, or only by a controller installed in the transport vehicle 10, or only by a controller installed separately from the transport vehicle controller 20 and the transport vehicle 10. The travel path R may be generated by the transport vehicle controller 20 and other controllers in cooperation, or by the controller installed in the transport vehicle 10 and other controllers in cooperation.

The transport vehicle system 1 may include only one transport vehicle 10, and the path generation system 6 may generate the travel path R of the one transport vehicle 10. The transport vehicle 10 is not limited to an AGV, and may be, for example, an overhead traveling vehicle or a tracked vehicle.

The constituent elements of the present invention can be described as follows. [1] A path generation system generates a path for one or more transport vehicles to travel from a starting point to a destination in a travel area. The path generation system comprises: a controller for generating the path along which the transport vehicle travels. The travel area has: a plurality of points at which the transport vehicle can pass and stop. The controller. For the plurality of points, a first block divided into three or more and a second block connected to the first block are set. The transport departure block, the transport destination block and the aforementioned points included in the aforementioned second block are captured, the transport departure block being a first block to which the aforementioned departure point belongs among the aforementioned first blocks, and the transport destination block being a first block to which the aforementioned destination belongs among the aforementioned first blocks, and the aforementioned path is generated from the captured aforementioned points. [2] The path generation system as described in [1], wherein, the aforementioned second block is set in a manner to include points with a high passing frequency based on a simulation of a full transport pattern. [3] A path generation system as described in [1] or [2], wherein: the controller sets the second block individually for the path traveled by each of the plurality of transport vehicles. [4] A path generation system as described in any one of [1] to [3], wherein: an upper limit is set for the number of the aforementioned points contained in each of the aforementioned first blocks. [5] A path generation system as described in any one of [1] to [4], wherein: at least one point among the aforementioned plurality of points in the aforementioned travel area is connected to no more than three paths, and the second block includes the at least one point. [6] A path generation system as described in any one of [1] to [4], wherein the aforementioned second block includes: a plurality of points connected to four or more paths respectively.

1: Transport vehicle system (automatic transport vehicle system) 5: Host controller 6: Path generation system 10: Transport vehicle (automatic transport vehicle) 11: Transport instruction receiving unit 12: Area information acquisition unit 13: Second block setting unit 14: Path generation unit 15: Travel control unit 20: Transport vehicle controller 21: Transport request receiving unit 23: Information acquisition unit 24: First block setting unit 25: Allocation determination unit A: Travel area B1a, B1b, B1c, B1d, B1e, B1f: Divided block (first block) B2: Shared block (second block) P: Point P _from : Starting point P _to :Destination R: Walking path R1b: Transportation departure path R1e: Transportation destination path R2: Total path S: Section (access)

[FIG. 1] is a general diagram of an unmanned transport vehicle system using the path generation system disclosed herein. [FIG. 2(a)] shows a walking area (walking route), and [FIG. 2(b)] shows a unit of the walking area extracted for display. [FIG. 3] is a functional block diagram showing the functional configuration of a controller of an implementation form. [FIG. 4] is an explanatory diagram of a plurality of first blocks and a second block set by the controller. [FIG. 5] is an explanatory diagram of an area explored by the controller when a path is generated. [FIG. 6] shows the walking area and the first and second blocks of the first variant. [FIG. 7(a)] and [FIG. 7(b)] show the walking area and the first and second blocks of the second and third variants, respectively. [Figure 8(a)] and [Figure 8(b)] show the walking area and the 1st and 2nd blocks of the 4th and 5th variants, respectively. [Figure 9] shows the walking area and the 1st and 2nd blocks of the 6th variant.

A: Walking area

B1b, B1e: Split block (block 1)

B2: Shared block (block 2)

P _from : departure place

P _to : destination

R: Walking path

R1b: Transportation departure route

R1e: Transport destination path

R2: Shared path

X1: Block settings

3001,3101,3201,3203,3304,3402,3405,3501,3504,3602,3605,3701,3704,3802,3805,3903,3904,3905,3906,3907,4001,4002,4003: points

Claims (6)

A path generation system generates a path for one or more transport vehicles to travel from a starting point to a destination in a travel area. The path generation system comprises: a controller for generating the path for the transport vehicle to travel. The travel area has: a plurality of points where the transport vehicle can pass and stop. The controller, For the plurality of points, a first block divided into three or more and a second block connected to the first block are set. The transport departure block, the transport destination block and the aforementioned points contained in the aforementioned second block are captured, the transport departure block is a first block to which the aforementioned departure point belongs among the aforementioned first blocks, and the transport destination block is a first block to which the aforementioned destination belongs among the aforementioned first blocks, and the aforementioned path is generated from the captured aforementioned points. A path generation system as in request item 1, wherein the aforementioned second block is set in a manner to include points with high passing frequency based on a simulation of a full transport mode. A path generation system as in claim 1 or 2, wherein the controller sets the second block individually for each of the paths traveled by the plurality of transport vehicles. If the path generation system of request item 1 or 2 is generated, wherein, an upper limit is set for the number of the aforementioned points contained in each of the aforementioned first blocks. A path generation system as in claim 1 or 2, wherein, at least one point among the aforementioned plurality of points in the aforementioned walking area is connected to no more than three paths, and the aforementioned second block includes the at least one point. A path generation system as in request item 1 or 2, wherein, the aforementioned second block includes: a plurality of points connected to more than 4 paths respectively.

Images