DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 5,6, 18, and 19 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
The term “AT4“ and “e2” in claims 5 and 18 render the claim indefinite because the term “AT4” is not defined by the claim.
The term “AT5“ and “e2” in claims 6 and 19 render the claim indefinite because the term “AT4” is not defined by the claim.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 9, 10, and 11 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Zhao (US
20100299059 A1).
Regarding claim 9, Zhang teaches a multi-mobile vehicle control method(Zhang, paragraph 4, multi-vehicle path planning. Zhang, paragraph 61, controlling the vehicle to travel according to the planned path ), comprising:
updating an actual exit time of a mobile vehicle from a current path unit(Zhang teaches Time_out which corresponds to the exit time of the mobile vehicle and teaches updating the exit time based on wait time. Zhang, paragraph 96, the update[d] time window time-out is time-out + t_wait (z). Zhang, paragraph 90, the entering time time-in is the time of the path planning starting time adding the virtual site from the starting station to the entering z, the leaving time-out is the maximum passing time of time-in adding z.), and
compensating a time difference between the actual exit time and a planned exit time in a scheduled path timing of the mobile vehicle in a path server(Zhang discloses incorporating the time difference between panned road time window(tout) and extended node time window(t’out) which corresponds to the current exit time and planned exit time respectively. Zhang, paragraph 104, calculating the common node conflict caused by the waiting time t-wait + = tout-t (wherein, z represents the extended node, [tin, tout] is the planned road time window, [t'in, t ' out] is extended node time window). judging whether the time window of the last node has new conflict. Zhang, paragraph 96, twait (z) = tout-t-out + ε, (wherein, z represents the expansion node, [tin, tout] is the planned road section time window, [t'in, t ' out] is the extended node time window, ε is the time of the vehicle passing through the controlled parking of the distance safety and is reduced to 0. Zhang, paragraph 11, a time window-based path planning program stored on the memory and running on the processor ); and controlling the mobile vehicle to move along a planned path to a target node(Zhang, paragraph 61, controlling the vehicle to travel according to the planned path ).
Regarding claim 10, Zhang teaches the multi-mobile vehicle control method according to claim 9(Zhang, paragraph 4, multi-vehicle path planning. Zhang, paragraph 61, controlling the vehicle to travel according to the planned path), further comprising: determining whether there is a multi-mobile vehicle conflict or a path unit occupancy conflict with the at least other mobile vehicle in the scheduled path timing of the mobile vehicle(Zhang, paragraph 70, performing conflict judgment according to the expansion node and the expansion node time window to obtain the conflict judging result); and replanning the path unit where the multi-mobile vehicle conflict or the path unit occupancy conflict occurs(Zhang, paragraph 159, when detecting the time window is abnormal, it needs to be AGV re-planning path).
Regarding claim 11, Zhang teaches the multi-mobile vehicle control method according to claim 10(Zhang, paragraph 4, multi-vehicle path planning. Zhang, paragraph 61, controlling the vehicle to travel according to the planned path), wherein the path unit occupancy conflict includes a forward conflict, a cross conflict, or a head-on conflict(Zhang, paragraph 156, if the two AGVs are oppositely running on one bidirectional road section, and the time window is overlapped, then the road section is formed to face to conflict. Zhang, paragraph 94, the conflict judging comprises: intersection conflict judgment, long road section conflict judgment and short section and dead end conflict judgment).
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim 1 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Zhang (CN 113821039 A).
Regarding claim 1, Zhao teaches a multi-mobile vehicle control method (Zhao, paragraph 9, multi-AGV intelligent cooperative scheduling method ) comprising: calculating a plurality of transportation costs for a plurality of standby mobile vehicles to reach a target point(Zhao discloses a time cost that is determined by evaluating the shortest distance path to a starting point(target point), which is similar to transportation cost. Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point); selecting a target standby mobile vehicle with a minimum transportation cost from the standby mobile vehicles that have been determined to have a path(Zhao, paragraph 20, selecting the idle AGV car with the smallest estimated time cost reaching the task starting point from all the idle AGV cars to execute the current task ); and assigning a task to the target standby mobile vehicle with the minimum transportation cost and (Zhao, paragraph 20, selecting the idle AGV car with the smallest estimated time cost reaching the task starting point from all the idle AGV cars to execute the current task),
While Zhao discloses selecting a vehicle based on estimated travel cost, it fails to disclose
controlling the target standby mobile vehicle to move to the target point.
However, Zhang, which is in the same analogous art and that teaches about path planning for AGVs discloses controlling the target standby mobile vehicle to move to the target point(Zhang, paragraph 61, controlling the vehicle to travel according to the planned path).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao with Zhang to control the movement of a vehicle to a target point based on a defined path. Zhao discloses scheduling method and selecting an ideal vehicle with lower transportation(time) cost, but it fails to disclose controlling the vehicle to move to a location. Zhang addresses this deficiency by controlling the movement of a vehicle based on defied path. By controlling the movement of plurality of vehicles, it is possible to reduce vehicles conflict and abnormal time window by incorporating stop and wait time in re-planning of vehicle path.
Claims 2 and 4 are rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Zhang (CN 113821039 A) in further view of Zhu(CN 106251016 B).
Regarding claim 2, the combination of Zhao and Zhang teaches the multi-mobile vehicle control method according to claim 1(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Zhang, paragraph 61, controlling the vehicle to travel according to the planned path),
The combination of Zhao and Zhang specifically fails to disclose an AGV path planning method wherein, when it is determined that all of the standby mobile vehicles have no path, waiting.
However, Zhu, which is in the same analogous art and that teaches about dynamic time window-based parking for AGV, discloses an AGV path planning method wherein, when it is determined that all of the standby mobile vehicles have no path, waiting(Zhu, paragraph 60, If the algorithm times iterative search (in order to avoid the appearance of the closed loop, a program loop search time setting a maximum limit) still cannot find collision-free optimization path, the algorithm search process is finished, and the task loading to the task sequence table, waiting for system scheduling the next task allocation. Zhu, paragraph 145, For conflict avoiding intersection collision and conflict, waiting strategy can be adopted for the opposite cannot avoid the conflict in the conflict, it can adopt the planning path strategy again solves for stronger collision is deceleration and waiting strategy to solve. can be changed according to actual needs, using local path planning strategy for the conflict of the available routes for planning treatment again).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao and Zhang with Zhu to implement a waiting strategy when collision free path is not detected. Waiting strategy when no path is determined prevent the vehicle from colliding or deadlocking with other vehicles, reducing travel time and conserving of resources. (Zhu, paragraph 158, Head-on node conflicts can cause AGV deadlocks or collisions and should be avoided during planning. For ordinary node conflicts, refer to
Figure 26, which is a schematic diagram of ordinary node conflicts. For ordinary node conflicts occurring in intersection areas, two AGVs will occupy the intersection at the same time, causing one AGV to wait on the road segment until the other AGV passes through the intersection before proceeding. For ordinary node conflicts occurring in grid areas, two AGVs will occupy the grid simultaneously, causing one AGV to wait at the previous grid until the other AGV passes through before proceeding. This method can resolve ordinary node conflicts, and the waiting time will not be too long).
Regarding claim 4, the combination of Zhao and Zhang teaches the multi-mobile vehicle control method according to claim 1(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Zhang, paragraph 61, controlling the vehicle to travel according to the planned path),
further comprising: determining whether the target mobile vehicle and a first mobile vehicle encounter a forward conflict, a head-on conflict, or a cross conflict on a path unit(Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types. Zhu, paragraph 130, the overtaking conflict refers to the conflict caused by two AGVs running on the same path at the same time Zhu, paragraph 58, the system detects whether there is an unavoidable conflict in the head-on conflict between multiple AGVs );
when it is determined that the target mobile vehicle and the first mobile vehicle encounter the forward conflict on the path unit, waiting for the first mobile vehicle to leave the path unit before controlling the target mobile vehicle to travel the path unit (Zhu, paragraph 131, If the system does not take any control measures for overtaking conflicts, a rear-end collision will inevitably occur between the two AGVs operating on the same path. Therefore, for this type of conflict, a deceleration and waiting strategy can be adopted to resolve it.);
when it is determined that the target mobile vehicle and the first mobile vehicle encounter the head-on conflict on the path unit, selecting an alternative edge for the target mobile vehicle(Zhu, paragraph 131, Figure 5(b) shows an unavoidable conflict. For this type of conflict, the most effective solution strategy is to replan a new feasible path for AGV2); and
when it is determined that the target mobile vehicle and the first mobile vehicle encounter the cross conflict on the path unit, waiting for the first mobile vehicle to leave the path unit before controlling the target mobile vehicle to travel the path unit(Zhu, paragraph 52, Intersection conflict refers to a conflict caused by two or more AGVs sharing an intersection at the same time. For this type of conflict, the system generally adopts a waiting strategy to resolve it.).
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Zhang (CN 113821039 A) in further view of Lin(CN 114911205 A) in further view of Bai(CN 117270466 A).
Regarding claim 3, the combination of Zhao and Zhang teaches the multi-mobile vehicle control method according to claim 1(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Zhang, paragraph 61, controlling the vehicle to travel according to the planned path), wherein the transportation cost includes: a travel path distance (Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point),
The combination of Zhao and Zhang specifically fails to disclose determining the priority of an AGV based on a number of intersections with other mobile vehicles during movement.
However, Lin, which is in the same analogous art and that teaches about a multi-AGV multi-target path planning method discloses determining the priority of an AGV based on a number of intersections with other mobile vehicles during movement(Lin discloses prioritizing AGV with smaller number of conflicts that corresponds to selecting an AGV with smaller number of intersections with other AGVs. Lin, paragraph 84, The new collision number new may be a negative value, indicating a decrease in the number of collisions. Therefore, when a path conflict occurs, both AGVs need to calculate their respective total number of conflicts, and the priority with a smaller number of conflicts is higher).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao and Zhang with Lin to prioritize vehicles with lower amount of conflict/intersection. By selecting vehicles with least number of conflict, it is possible increase efficiency of the whole system by reducing disruption, wait time, and preventing a deadlock of multiple vehicles.
The combination of Zhao, Zhang, and Lin specifically fails to disclose determining the priority of an AGV based on time spent resolving conflicts.
However, Bai, which is in the same analogous art and that teaches about automatic container terminal scheduling discloses selecting AGVs based on time spent resolving conflicts(Bai, paragraph 22, S4: for each conflict path, enabling the conflict AGV with short avoidance time to enter the temporary avoidance point; Specifically, for the conflicting paths of the two AGV, the AGV with short avoidance time is allowed to enter the temporary avoidance point, and after the other AGV passes through the conflict point, the temporary avoidance point is driven out ).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Zhang, and Lin with Bai to prioritize AGV with short conflict avoidance time. By selecting an AGV with short avoidance time, it is possible to reduce the AGV collision, and reduce the total avoidance time, so that each AGV can reach the designated place as soon as possible. This greatly reduces the operation time extension and device energy consumption caused by AGV path collision.
Claims 5 and 6 are rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Zhang (CN 113821039 A) in further view of Zhu (CN 106251016 B) in further view of Kario(US 20220227367 A1) in further view of Sheng(CN 117146843 A).
Regarding claim 5, the combination of Zhao, Zhang, and Zhu teaches the multi-mobile vehicle control method according to claim 4(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Zhang, paragraph 61, controlling the vehicle to travel according to the planned path; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types), wherein, when the path unit that the target mobile vehicle intends to travel and the path unit that the first mobile vehicle intends to travel are in the same direction, it is determined that the target mobile vehicle and the first mobile vehicle have the forward conflict(Zhu, paragraph 131, If the system does not take any control measures for overtaking conflicts, a rear-end collision will inevitably occur between the two AGVs operating on the same path ),
The combination of Zhao, Zhang, and Zhu specifically fails to disclose adjusting the entry time point s1 of the target mobile vehicle to an adjusted entry time point s1’, AT4=s1’-s1=abs(e2-s1)+TT, where e2 is an exit time point of the first mobile vehicle from the path unit, abs(e2-s1) represents an absolute value of (e2-s1), and TT is a tolerance time, the transportation cost of the target mobile vehicle is AT4*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes.
However, Kario, which is in the same analogous art and that teaches about vehicle navigation discloses adjusting the entry time point s1 of the target mobile vehicle to an adjusted entry time point s1’, AT4=s1’-s1=abs(e2-s1)+TT, where e2 is an exit time point of the first mobile vehicle from the path unit, abs(e2-s1) represents an absolute value of (e2-s1), and TT is a tolerance time(Kario, paragraph 248, each car will arrive at point when a first part of the car passes the intersection point, and a certain amount of time will be required before the last part of the car passes through the intersection point. This amount of time separates the arrival time from the leaving time. Assuming that t.sub.1.sup.a<t.sub.2.sup.a (i.e., that the arrival time of vehicle 1 is less than the arrival time of vehicle 2), then we will want to ensure that vehicle 1 has left the intersection point prior to vehicle 2 arriving. Otherwise, a collision would result. Thus, a hard constraint may be implemented such that t.sub.1.sup.l>t.sub.2.sup.a. Moreover, to ensure that vehicle 1 and vehicle 2 do not miss one another by a minimal amount, an added margin of safety may be obtained by including a buffer time into the constraint (e.g., 0.5 seconds or another suitable value). A hard constraint relating to predicted intersection trajectories of two vehicles may be expressed as t.sub.1.sup.l>t.sub.2.sup.a+0.5. ),
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Zhang, and Zhu with Kario to reduce the risk of collision due to different vehicles occupying the same node by incorporating delay time after a first vehicle releases a node. Kario discloses applying constraints so that the host vehicle will avoid maintaining a collision course with one or more vehicles.
The combination of Zhao, Zhang, Zhu, and Kario specifically fails to disclose the transportation cost of the target mobile vehicle is AT4*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes.
However, Sheng, which is in the same analogous art and that teaches about unmanned vehicle path planning discloses the transportation cost of the target mobile vehicle is AT4*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes(Sheng, paragraph 10, the hybrid A* algorithm sets the issued cost function g(x) and the heuristic cost function h(x); the issued cost function g(x) contains two parameters. The first parameter is the distance from the starting point to the current node, which is obtained by multiplying the vehicle's speed by time… the heuristic cost function h(x) sets two cost calculation methods, and finally takes the larger value as the final cost; the first cost calculation conforms to vehicle kinematics but does not consider whether a collision occurs on the path. The first cost calculation is implemented using Reeds-Shepp curves. First, a Reeds-Shepp curve from the current pose to the target pose is generated, and the length of the Reeds-Shepp curve is used as the first cost ).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Zhang, Zhu, and Kario with Sheng to incorporate distance in the evaluation of transportation cost. By incorporating distance in cost evaluation, it is possible to improve the accuracy and efficiency of path planning to make it more intelligent and adaptive to changes in the environment.
Regarding claim 6, the combination of Zhao, Zhang, and Zhu teaches the multi-mobile vehicle control method according to claim 4(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Zhang, paragraph 61, controlling the vehicle to travel according to the planned path; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types), wherein, when the path unit that the target mobile vehicle intends to travel and a second path unit that the first mobile vehicle intends to travel reach the same connection point, it is determined that the target mobile vehicle and the first mobile vehicle have the cross conflict(Zhu, paragraph 52, Intersection conflict refers to a conflict caused by two or more AGVs sharing an intersection at the same time), adjusting the entry time point s1 of the target mobile vehicle to an adjusted entry time point s1’, AT5=s1’-s1=abs(e2-s1)+TT, abs(e2-s1) represents an absolute value of (e2-s1), and TT is a tolerance time(Kario, paragraph 248, each car will arrive at point when a first part of the car passes the intersection point, and a certain amount of time will be required before the last part of the car passes through the intersection point. This amount of time separates the arrival time from the leaving time. Assuming that t.sub.1.sup.a<t.sub.2.sup.a (i.e., that the arrival time of vehicle 1 is less than the arrival time of vehicle 2), then we will want to ensure that vehicle 1 has left the intersection point prior to vehicle 2 arriving. Otherwise, a collision would result. Thus, a hard constraint may be implemented such that t.sub.1.sup.l>t.sub.2.sup.a. Moreover, to ensure that vehicle 1 and vehicle 2 do not miss one another by a minimal amount, an added margin of safety may be obtained by including a buffer time into the constraint (e.g., 0.5 seconds or another suitable value). A hard constraint relating to predicted intersection trajectories of two vehicles may be expressed as t.sub.1.sup.l>t.sub.2.sup.a+0.5. ), the transportation cost of the target mobile vehicle is AT5*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes(Sheng, paragraph 10, the hybrid A* algorithm sets the issued cost function g(x) and the heuristic cost function h(x); the issued cost function g(x) contains two parameters. The first parameter is the distance from the starting point to the current node, which is obtained by multiplying the vehicle's speed by time….the heuristic cost function h(x) sets two cost calculation methods, and finally takes the larger value as the final cost; the first cost calculation conforms to vehicle kinematics but does not consider whether a collision occurs on the path. The first cost calculation is implemented using Reeds-Shepp curves. First, a Reeds-Shepp curve from the current pose to the target pose is generated, and the length of the Reeds-Shepp curve is used as the first cost).
Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Zhang (CN 113821039 A) in further view of Zhu (CN 106251016 B) in further view of Nawade (US 20210011487 A1).
Regarding claim 7, the combination of Zhao, Zhang, and Zhu teaches the multi-mobile vehicle control method according to claim 4(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Zhang, paragraph 61, controlling the vehicle to travel according to the planned path; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types), wherein, when the path unit that the target mobile vehicle intends to travel and the path unit that the first mobile vehicle intends to travel are in opposite directions, it is determined that the target mobile vehicle and the first mobile vehicle have the head-on conflict(Zhu, paragraph 54, a conflict caused by AGVs running in opposite directions on the same path competing for path resources within a certain time period.),
The combination of Zhao, Zhang, and Zhu specifically fails to disclose an AGV control method wherein when the head-on conflict occurs, an adjustment time for the target mobile vehicle makes the transportation cost for traveling the path unit higher than the transportation cost for traveling an adjacent path unit.
However, Nawade, which is in the same analogous art and that teaches about synchronizing movement of transport vehicles discloses an AGV control method wherein when the head-on conflict occurs, an adjustment time for the target mobile vehicle makes the transportation cost for traveling the path unit higher than the transportation cost for traveling an adjacent path unit(Nawade, paragraph, If the WCS 110 determines that a collision between the first and second transport vehicles 106a and 106b is likely, the WCS 110 may determine an alternate path that may be traversed by one of the first and second transport vehicles 106a and 106b for avoiding the collision. In some scenarios, the alternate path may be a sub-optimal path. In other words, there may be a penalty (such as a time penalty) associated with one of the first and second transport vehicles 106a and 106b traversing the alternate path. Consequently, the WCS 110 determines that the throughput may be affected when one of the first and second transport vehicles 106a and 106b traverses the alternate path. Consequently, the WCS 110 determines that the throughput may be affected when one of the first and second transport vehicles 106a and 106b traverses the alternate path. In such a scenario, the WCS 110 may perform a cost-benefit analysis to determine if the first and second transport vehicles 106a and 106b should traverse the first and second paths or if one of the first and second transport vehicles 106a and 106b should traverse the alternate path. In performing the cost-benefit analysis, the WCS 110 determines whether the alternate path is viable (i.e., whether a penalty associated with the alternate path is acceptable)).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Zhang, and Zhu with Nawade to shift the traveling path of a vehicle to an alternate path to avoid collision when collision route is detected. By switching to an alternate path, it is possible to reduce wait time, resource, and prevent unnecessary deadlock.
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Zhang (CN 113821039 A) in further view of Zhu (CN 106251016 B) in further view of Lang (CN 112748719 A).
Regarding claim 8, the combination of Zhao, Zhang, and Zhu teaches The multi-mobile vehicle control method according to claim 4(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Zhang, paragraph 61, controlling the vehicle to travel according to the planned path; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types),
The combination of Zhao, Zhang, and Zhu specifically fails to disclose a method wherein, when it is determined that there is no conflict between the target mobile vehicle and the first mobile vehicle, an adjusted transportation cost of the target mobile vehicle is related to a distance between two nodes.
However, Lang, which is in the same analogous art and that teaches about controlling transport vehicle discloses a method wherein, when it is determined that there is no conflict between the target mobile vehicle and the first mobile vehicle, an adjusted transportation cost of the target mobile vehicle is related to a distance between two nodes(Lang, paragraph 69, the second transportation cost s(a,y) can be determined based on the distance between the current position and the adjacent travel point. For example, if the distance between the current position and the adjacent travel point is 10, then the second transportation cost s(a,y) is 10 ).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings Zhao, Zhang, and Zhu with Lang to incorporate distance in the evaluation of transportation cost. By incorporating distance in cost evaluation, it is possible to improve the accuracy and efficiency of path planning making it more intelligent and adaptive to changes in the environment. Furthermore, it is possible to evaluate the shortest driving distance as the updated travel path, or the path with the least number of intersection between the non-travel path of the other transport vehicle as the updated travel path, or the path with the minimum loss as the updated travel path.
Claim 12 is rejected under 35 U.S.C. 103 as being unpatentable over Zhang (CN 113821039 A) in view of Zhu (CN 106251016 B).
Regarding claim 12, Zhang teaches the multi-mobile vehicle control method according to claim 10(Zhang, paragraph 4, multi-vehicle path planning. Zhang, paragraph 61, controlling the vehicle to travel according to the planned path), wherein, when the mobile vehicle starts to leave the current path unit:
when a conflict occurs in the current path unit after timing compensation, replanning the conflicted current path unit(Zhang discloses exit time (tout) is used to evaluate the whether a collision is caused, and waiting to avoid a collision indicates a replanning of travel path. Zhang, paragraph 96, judging whether the new section time window is included in a certain planned road section time window, if it is included, then waiting for avoiding collision, calculating the waiting time twait, wherein twait (z) = tout-t-out + ε, (wherein, z represents the expansion node, [tin, tout] is the planned road section time window, [t'in, t ' out] is the extended node time window, ε is the time of the vehicle passing through the controlled parking of the distance safety and is reduced to 0. Zhang, paragraph 70, performing conflict judgment according to the expansion node and the expansion node time window to obtain the conflict judging result. Zhang, paragraph 159, when detecting the time window is abnormal, it needs to be AGV re-planning path );
While Zhang teaches about incorporating time difference between existing exit time and current exit time, it fails to discloses occupying a next path unit; and releasing the current path unit,
and updating data of the occupied next path unit and the released current path unit in the path server.
However, Zhu, which is in the same analogous art and that teaches about dynamic time window-based parking for AGV, discloses occupying a next path unit(Zhu discloses determining whether an AGV has travelled to different road segment which indicates its capability to occupy a different path. Zhu, paragraph 49, the ground control system will receive the location, speed and running status information uploaded by the AGV in real time during the journey, and determine whether the AGV has left a road segment or an intersection and is heading to the next road segment or intersection based on this information); and releasing the current path unit(Zhu, paragraph 124, it is necessary from the time window vector table deleting the AGV in the table registration information. to release the road or the intersection resource for other AGV; in the step S4 so as to avoid in the time period occupied by the AGV, the other AGV to cause dead lock or collision ),
and updating data of the occupied next path unit and the released current path unit in the path server(Zhu discloses real-time processing of information when switching path and releasing path that indicates the updating of path data. Zhu, paragraph 49, in the step S4, a ground control system receiving the AGV will in real time in the running process of uploading position, speed and running state information….it is necessary from the time window vector table deleting the AGV in the table registration information to release the road or the intersection resource for other AGV; in the step S4 so as to avoid in the time period occupied by the AGV, the other AGV to cause dead lock or collision.).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhang with Zhu to teach the transfer of a vehicle to different path while releasing current path. By transferring to different path while releasing the path of current path, it is possible to delete the AGV in the table registration information so as to release the road or the intersection resource for other AGV when the AGV has left a certain road or certain intersection. Furthermore, conflict-free and time optimized route is evaluated and circularly updated by newly searched time window vector table of optimized route.
Claim 13 is rejected under 35 U.S.C. 103 as being unpatentable over Zhang (CN 113821039 A) in view of Zhu (CN 106251016 B) in further view of Sun (CN 116007624 A).
Regarding claim 13, Zhang teaches the multi-mobile vehicle control method according to claim 10(Zhang, paragraph 4, multi-vehicle path planning. Zhang, paragraph 61, controlling the vehicle to travel according to the planned path), wherein, when the mobile vehicle starts to enter the current path unit:
releasing a previous path unit(Zhu, paragraph 49, if the AGV has left a certain road or certain intersection, it is necessary from the time window vector table deleting the AGV in the table registration information so as to release the road or the intersection resource for other AGV );
While the combination of Zhang and Zhu specifically fails to disclose the updating of path based on exit time difference, it fail to disclose updating an actual entry time of the mobile vehicle into the current path unit, and compensating a time difference between the actual entry time and a planned entry time in a planned path schedule; when a conflict occurs in the current path unit after timing compensation, replanning the conflicted current path unit and occupying the current path unit, and updating data of the released previous path unit and the occupied current path unit in the path server.
However, Sun, which is in the same analogous art and that teaches about path planning method for AGVs discloses updating an actual entry time of the mobile vehicle into the current path unit(Sun, paragraph 138, a time window updating module, for determining the first entrance time point and the first exit time point of each path node in the new current planning path of the intelligent body to be planed, updating the first path time period corresponding to the to-be-planed intelligent body in the three-dimensional time window.), and compensating a time difference between the actual entry time and a planned entry time in a planned path schedule(Sun discloses an entry and exit time window wherein when determining collision, a delay and an updating of entry time is processed. The delay indicates a time different between planned entry and actual entry time. Sun, paragraph 89, it is assumed that the first driving time point of the planning agent under the current path node is Q1, the second driving-out time point of the target first type planned intelligent body under the current path node is P2, then the to-be-planned intelligent body under the current path node of the collision delay time delay Time=P2-Q1. Sun, paragraph 90, then, according to the collision delay time, it can set the first driving time point and the first driving-out time point of the intelligent body to be programmed under the current path node and each subsequent path node to delay the collision delay time, obtaining the new first driving time point and the first driving-out time point of the to-be-planned intelligent body under the current path node and each post-sequence path node, so as to update the corresponding channel time period information of the to-be-planned intelligent body in the three-dimensional time window); when a conflict occurs in the current path unit after timing compensation, replanning the conflicted current path unit and occupying the current path unit(Sun, paragraph 131, determining the collision pushing time length of the to-be-planned intelligent body under the current path node; according to the collision delay time. Sun, paragraph 132, updating the first driving time point and the first driving-out time point of the to-be-planned intelligent body under the current path node and each subsequent path node. ), and updating data of the released previous path unit and the occupied current path unit in the path server(Sun, paragraph 127, updating the target path sequence from the current path node to the target path node in the current planning path, obtaining a new current planning path and a new next path node, to continue to determine whether the second type collision exists in the current sub-path from the current path node to the new next path node by the to-be-planned intelligent body and any one of the second-type programmed intelligent body. Sun, paragraph 113, it needs to re-determine the first driving time point and the first driving-out time point of each path node in the new current planning path to be programmed, and updating the first path time period corresponding to the to-be-planned intelligent body in the three-dimensional time window ).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhang and Zhu with Sun to incorporate timing of planned entry and current entry time. By incorporating entry time difference, it is possible to implement waiting strategy to avoid conflicting path while initiating path re-planning strategy. Furthermore, It is possible to dynamically change low priority AVG’s running course so as to avoid collision and deadlock.
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Sun (CN 116007624 A).
Regarding claim 14, Zhao teaches a multi-mobile vehicle control system(Zhao, paragraph 9, multi-AGV intelligent cooperative scheduling method) comprising:
the control unit(Zhao, paragraph 82, processing unit,) is configured for:
calculating a plurality of transportation costs for a plurality of standby mobile vehicles to reach a target point(Zhao discloses a time cost that is determined by evaluating the shortest distance path to a starting point(target point), which is similar to transportation cost. Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point);
selecting a target standby mobile vehicle with a minimum transportation cost from the standby mobile vehicles that have been determined to have a path(Zhao, paragraph 20, selecting the idle AGV car with the smallest estimated time cost reaching the task starting point from all the idle AGV cars to execute the current task); and
assigning a task to the target standby mobile vehicle with the minimum transportation cost, and controlling the target standby mobile vehicle to move to the target point(Zhao, paragraph 20, selecting the idle AGV car with the smallest estimated time cost reaching the task starting point from all the idle AGV cars to execute the current task).
While Zhao discloses selecting a vehicle based on estimated travel cost, it fails to disclose
a path server; a control unit communicating with the path server; and
a plurality of mobile vehicles communicating with the path server and the control unit,
wherein the path server stores multiple entry-exit timing of each of the mobile vehicles on each path unit
However, Sun, which is in the same analogous art and that teaches about path planning method for AGVs discloses a path server( Sun discloses different storage medium that store instruction such server and data centers. These storage mediums can store path planning instructions. Sun, paragraph 159, the computer instruction can be stored in the computer readable storage medium, or from one computer readable storage medium to another computer readable storage medium transmission, for example, the computer instruction can be from a website site, a computer, a server. Sun, paragraph 15, a computer-readable storage medium for storing a computer program, the computer program causes a computer to perform a path planning);
a control unit communicating with the path server(Sun discloses a processor which is similar to a control unit that communicates with storage medium such as a server. Sun, paragraph 144, storage medium is located in the memory, the processor reads the information in the memory, combining the hardware to finish the steps in the method embodiment); and
a plurality of mobile vehicles communicating with the path server and the control unit(Sun, paragraph 61, a path planning method and device. device and storage medium, the three-dimensional time window realizes the non-collision path planning of any intelligent body under the multi-intelligent body task scheduling reduces the resource overhead of the multi-intelligent body path planning, improves the movement safety of any intelligent body under the target planning path. Sun, paragraph 159, the computer instruction can be stored in the computer readable storage medium, or from one computer readable storage medium to another computer readable storage medium transmission, for example, the computer instruction can be from a website site, a computer, a server),
wherein the path server stores multiple entry-exit timing of each of the mobile vehicles on each path unit(Sun, paragraph 45, it is necessary to avoid the collision between the multiple intelligent bodies as much as possible. Therefore, the present application needs to analyze each intelligent body through the route of each path node in the path of the intelligent body has been planned, and each path node corresponding to the passage period can include the entrance time point and the exit time point under the path node. Sun, paragraph 159, the computer instruction can be stored in the computer readable storage medium, or from one computer readable storage medium to another computer readable storage medium transmission, for example, the computer instruction can be from a website site, a computer, a server);
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao with Sun to incorporate server that stores instruction for path planning. By incorporating server to store path planning instruction, it is possible to remotely store multiple paths that can be used to control plurality vehicles.
Claims 15,17 are rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Sun (CN 116007624 A) in further view of Zhu (CN 106251016 B).
Regarding claim 15, the combination of Zhang and Sun teaches the multi-mobile vehicle control system according to claim 14(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server ),
The combination of Zhang and Sun specifically fails to disclose an AGV path planning system
wherein, when it is determined that all of the standby mobile vehicles have no path, waiting.
However, Zhu, which is in the same analogous art and that teaches about dynamic time window-based parking for AGV, discloses an AGV path planning system wherein, when it is determined that all of the standby mobile vehicles have no path, waiting(Zhu, paragraph 60, If the algorithm times iterative search (in order to avoid the appearance of the closed loop, a program loop search time setting a maximum limit) still cannot find collision-free optimization path, the algorithm search process is finished, and the task loading to the task sequence table, waiting for system scheduling the next task allocation. Zhu, paragraph 145, For conflict avoiding intersection collision and conflict, waiting strategy can be adopted for the opposite cannot avoid the conflict in the conflict, it can adopt the planning path strategy again solves for stronger collision is deceleration and waiting strategy to solve. can be changed according to actual needs, using local path planning strategy for the conflict of the available routes for planning treatment again).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhang and Sun with Zhu to implement a waiting strategy when collision free path is not detected. Waiting strategy when no path is determined prevent the vehicle from colliding or deadlocking with other vehicles, reducing travel time and conserving of resources.
Regarding claim 17, the combination of Zhao and Sun teaches The multi-mobile vehicle control system according to claim 14(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server),
wherein the control unit or the mobile vehicles execute are configured for: determining whether the target mobile vehicle and a first mobile vehicle encounter a forward conflict, a head-on conflict, or a cross conflict on a path unit(Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types. Zhu, paragraph 130, the overtaking conflict refers to the conflict caused by two AGVs running on the same path at the same time. Zhu, paragraph 58, the system detects whether there is an unavoidable conflict in the head-on conflict between multiple AGVs);
when it is determined that the target mobile vehicle and the first mobile vehicle encounter the forward conflict on the path unit, waiting for the first mobile vehicle to leave the path unit before controlling the target mobile vehicle to travel the path unit(Zhu, paragraph 131, If the system does not take any control measures for overtaking conflicts, a rear-end collision will inevitably occur between the two AGVs operating on the same path. Therefore, for this type of conflict, a deceleration and waiting strategy can be adopted to resolve it);
when it is determined that the target mobile vehicle and the first mobile vehicle encounter the head-on conflict on the path unit, selecting an alternative edge for the target mobile vehicle(Zhu, paragraph 131, Figure 5(b) shows an unavoidable conflict. For this type of conflict, the most effective solution strategy is to replan a new feasible path for AGV2); and
when it is determined that the target mobile vehicle and the first mobile vehicle encounter the cross conflict on the path unit, waiting for the first mobile vehicle to leave the path unit before controlling the target mobile vehicle to travel the path unit(Zhu, paragraph 52, Intersection conflict refers to a conflict caused by two or more AGVs sharing an intersection at the same time. For this type of conflict, the system generally adopts a waiting strategy to resolve it).
Claim 16 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Sun (CN 116007624 A) in further view of Lin (CN 114911205 A) in further view of Bai (CN 117270466 A).
Regarding claim 16, the combination of Zhao and Sun teaches the multi-mobile vehicle control system according to claim 14(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server), wherein the transportation cost includes: a travel path distance(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point),
The combination of Zhao and Sun specifically fails to disclose determining the priority of an AGV based on a number of intersections with other mobile vehicles during movement, and time spent resolving conflicts.
However, Lin, which is in the same analogous art and that teaches about a multi-AGV multi-target path planning method discloses determining the priority of an AGV based on a number of intersections with other mobile vehicles during movement, and time spent resolving conflicts(Lin discloses prioritizing AGV with smaller number of conflicts that corresponds to selecting an AGV with smaller number of intersections with other AGVs. Lin, paragraph 84, The new collision number new may be a negative value, indicating a decrease in the number of collisions. Therefore, when a path conflict occurs, both AGVs need to calculate their respective total number of conflicts, and the priority with a smaller number of conflicts is higher).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao and Sun with Lin to prioritize vehicles with lower amount of conflict/intersection. By selecting vehicles with least number of conflict, it is possible increase efficiency of the whole system by reducing disruption, wait time, and preventing a deadlock of multiple vehicles.
The combination of Zhao, Sun, and Lin specifically fails to disclose determining the priority of an AGV based on time spent resolving conflicts.
However, Bai, which is in the same analogous art and that teaches about automatic container terminal scheduling discloses selecting AGVs based on time spent resolving conflicts(Bai, paragraph 22, S4: for each conflict path, enabling the conflict AGV with short avoidance time to enter the temporary avoidance point; Specifically, for the conflicting paths of the two AGV, the AGV with short avoidance time is allowed to enter the temporary avoidance point, and after the other AGV passes through the conflict point, the temporary avoidance point is driven out).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Sun, and Lin with Bai to prioritize AGV with short conflict avoidance time. By selecting an AGV with short avoidance time, it is possible to reduce the AGV collision, and reduce the total avoidance time, so that each AGV can reach the designated place as soon as possible. This greatly reduces the operation time extension and device energy consumption caused by AGV path collision.
Claims 18 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Sun (CN 116007624 A) in further view of Zhu (CN 106251016 B) in further view of Kario(US 20220227367 A1) in further view of Sheng(CN 117146843 A).
Regarding claim 18, the combination of Zhao, Sun, and Zhu teaches the multi-mobile vehicle control system according to claim 17(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types), wherein, when the path unit that the target mobile vehicle intends to travel and the path unit that the first mobile vehicle intends to travel are in the same direction, it is determined that the target mobile vehicle and the first mobile vehicle have the forward conflict(Zhu, paragraph 131, If the system does not take any control measures for overtaking conflicts, a rear-end collision will inevitably occur between the two AGVs operating on the same path),
The combination of Zhao, Sun, and Zhu specifically fails to disclose adjusting the entry time point s1 of the target mobile vehicle to an adjusted entry time point s1’, AT4=s1’-s1=abs(e2-s1)+TT, where e2 is an exit time point of the first mobile vehicle from the path unit, abs(e2-s1) represents an absolute value of (e2-s1), and TT is a tolerance time, the transportation cost of the target mobile vehicle is AT4*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes.
However, Kario, which is in the same analogous art and that teaches about vehicle navigation discloses adjusting the entry time point s1 of the target mobile vehicle to an adjusted entry time point s1’, AT4=s1’-s1=abs(e2-s1)+TT, where e2 is an exit time point of the first mobile vehicle from the path unit, abs(e2-s1) represents an absolute value of (e2-s1), and TT is a tolerance time(Kario, paragraph 248, each car will arrive at point when a first part of the car passes the intersection point, and a certain amount of time will be required before the last part of the car passes through the intersection point. This amount of time separates the arrival time from the leaving time. Assuming that t.sub.1.sup.a<t.sub.2.sup.a (i.e., that the arrival time of vehicle 1 is less than the arrival time of vehicle 2), then we will want to ensure that vehicle 1 has left the intersection point prior to vehicle 2 arriving. Otherwise, a collision would result. Thus, a hard constraint may be implemented such that t.sub.1.sup.l>t.sub.2.sup.a. Moreover, to ensure that vehicle 1 and vehicle 2 do not miss one another by a minimal amount, an added margin of safety may be obtained by including a buffer time into the constraint (e.g., 0.5 seconds or another suitable value). A hard constraint relating to predicted intersection trajectories of two vehicles may be expressed as t.sub.1.sup.l>t.sub.2.sup.a+0.5.).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Sun, and Zhu with Kario to reduce the risk of collision due to different vehicles occupying the same node by incorporating delay time after a first vehicle releases a node. Kario discloses applying constraints so that the host vehicle will avoid maintaining a collision course with one or more vehicles.
The combination of Zhao, Sun, Zhu, and Kario specifically fails to disclose the transportation cost of the target mobile vehicle is AT4*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes.
However, Sheng, which is in the same analogous art and that teaches about unmanned vehicle path planning discloses the transportation cost of the target mobile vehicle is AT4*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes(Sheng, paragraph 10, the hybrid A* algorithm sets the issued cost function g(x) and the heuristic cost function h(x); the issued cost function g(x) contains two parameters. The first parameter is the distance from the starting point to the current node, which is obtained by multiplying the vehicle's speed by time… the heuristic cost function h(x) sets two cost calculation methods, and finally takes the larger value as the final cost; the first cost calculation conforms to vehicle kinematics but does not consider whether a collision occurs on the path. The first cost calculation is implemented using Reeds-Shepp curves. First, a Reeds-Shepp curve from the current pose to the target pose is generated, and the length of the Reeds-Shepp curve is used as the first cost).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Sun, and Zhu, and Kario with Sheng to incorporate distance in the evaluation of transportation cost. By incorporating distance in cost evaluation, it is possible to improve the accuracy and efficiency of path planning to make it more intelligent and adaptive to changes in the environment.
Regarding claim 19, the combination of Zhao, Sun, and Zhu teaches the multi-mobile vehicle control system according to claim 17(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types), wherein, when the path unit that the target mobile vehicle intends to travel and a second path unit that the first mobile vehicle intends to travel reach the same connection point, it is determined that the target mobile vehicle and the first mobile vehicle have the cross conflict(Zhu, paragraph 52, Intersection conflict refers to a conflict caused by two or more AGVs sharing an intersection at the same time), adjusting the entry time point s1 of the target mobile vehicle to an adjusted entry time point s1’, AT5=s1’-s1=abs(e2-s1)+TT, abs(e2-s1) represents an absolute value of (e2-s1), and TT is a tolerance time(Kario, paragraph 248, each car will arrive at point when a first part of the car passes the intersection point, and a certain amount of time will be required before the last part of the car passes through the intersection point. This amount of time separates the arrival time from the leaving time. Assuming that t.sub.1.sup.a<t.sub.2.sup.a (i.e., that the arrival time of vehicle 1 is less than the arrival time of vehicle 2), then we will want to ensure that vehicle 1 has left the intersection point prior to vehicle 2 arriving. Otherwise, a collision would result. Thus, a hard constraint may be implemented such that t.sub.1.sup.l>t.sub.2.sup.a. Moreover, to ensure that vehicle 1 and vehicle 2 do not miss one another by a minimal amount, an added margin of safety may be obtained by including a buffer time into the constraint (e.g., 0.5 seconds or another suitable value). A hard constraint relating to predicted intersection trajectories of two vehicles may be expressed as t.sub.1.sup.l>t.sub.2.sup.a+0.5. ), the transportation cost of the target mobile vehicle is AT5*V+D, where V represents a speed of the target mobile vehicle, and D represents a distance between two nodes(Sheng, paragraph 10, the hybrid A* algorithm sets the issued cost function g(x) and the heuristic cost function h(x); the issued cost function g(x) contains two parameters. The first parameter is the distance from the starting point to the current node, which is obtained by multiplying the vehicle's speed by time….the heuristic cost function h(x) sets two cost calculation methods, and finally takes the larger value as the final cost; the first cost calculation conforms to vehicle kinematics but does not consider whether a collision occurs on the path. The first cost calculation is implemented using Reeds-Shepp curves. First, a Reeds-Shepp curve from the current pose to the target pose is generated, and the length of the Reeds-Shepp curve is used as the first cost).
Claim 20 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Sun (CN 116007624 A) in further view of Zhu (CN 106251016 B) in further view of Nawade (US 20210011487 A1).
Regarding claim 20, the combination of Zhao, Sun, and Zhu teaches the multi-mobile vehicle control system according to claim 17(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types), wherein, when the path unit that the target mobile vehicle intends to travel and the path unit that the first mobile vehicle intends to travel are in opposite directions, it is determined that the target mobile vehicle and the first mobile vehicle have the head-on conflict(Zhu, paragraph 54, a conflict caused by AGVs running in opposite directions on the same path competing for path resources within a certain time period),
The combination of Zhao, Sun, and Zhu specifically fails to disclose an AGV control method wherein when the head-on conflict occurs, an adjustment time for the target mobile vehicle makes the transportation cost for traveling the path unit higher than the transportation cost for traveling an adjacent path unit.
However, Nawade, which is in the same analogous art and that teaches about synchronizing movement of transport vehicles discloses an AGV control system wherein when the head-on conflict occurs, an adjustment time for the target mobile vehicle makes the transportation cost for traveling the path unit higher than the transportation cost for traveling an adjacent path unit(Nawade, paragraph, If the WCS 110 determines that a collision between the first and second transport vehicles 106a and 106b is likely, the WCS 110 may determine an alternate path that may be traversed by one of the first and second transport vehicles 106a and 106b for avoiding the collision. In some scenarios, the alternate path may be a sub-optimal path. In other words, there may be a penalty (such as a time penalty) associated with one of the first and second transport vehicles 106a and 106b traversing the alternate path. Consequently, the WCS 110 determines that the throughput may be affected when one of the first and second transport vehicles 106a and 106b traverses the alternate path. Consequently, the WCS 110 determines that the throughput may be affected when one of the first and second transport vehicles 106a and 106b traverses the alternate path. In such a scenario, the WCS 110 may perform a cost-benefit analysis to determine if the first and second transport vehicles 106a and 106b should traverse the first and second paths or if one of the first and second transport vehicles 106a and 106b should traverse the alternate path. In performing the cost-benefit analysis, the WCS 110 determines whether the alternate path is viable (i.e., whether a penalty associated with the alternate path is acceptable)).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Sun, and Zhu with Nawade to shift the traveling path of a vehicle to an alternate path to avoid collision when collision route is detected. By switching to an alternate path, it is possible to reduce wait time, resource, and prevent unnecessary deadlock.
Claim 21 is rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Sun (CN 116007624 A) in further view of Zhu (CN 106251016 B) in further view of Lang (CN 112748719 A).
Regarding claim 21, the combination of Zhang, Sun, and Zhu teaches the multi-mobile vehicle control system according to claim 17(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types),
The combination of Zhao, Sun, and Zhu specifically fails to disclose a system wherein, when it is determined that there is no conflict between the target mobile vehicle and the first mobile vehicle, an adjusted transportation cost of the target mobile vehicle is related to a distance between two nodes.
However, Lang, which is in the same analogous art and that teaches about controlling transport vehicle discloses a system wherein, when it is determined that there is no conflict between the target mobile vehicle and the first mobile vehicle, an adjusted transportation cost of the target mobile vehicle is related to a distance between two nodes(Lang, paragraph 69, the second transportation cost s(a,y) can be determined based on the distance between the current position and the adjacent travel point. For example, if the distance between the current position and the adjacent travel point is 10, then the second transportation cost s(a,y) is 10 ).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings Zhao, Sun, and Zhu with Lang to incorporate distance in the evaluation of transportation cost. By incorporating distance in cost evaluation, it is possible to improve the accuracy and efficiency of path planning making it more intelligent and adaptive to changes in the environment. Furthermore, it is possible to evaluate the shortest driving distance as the updated travel path, or the path with the least number of intersection between the non-travel path of the other transport vehicle as the updated travel path, or the path with the minimum loss as the updated travel path.
Claims 22, 23, 24, and 25 are rejected under 35 U.S.C. 103 as being unpatentable over Zhao (CN 113780633 A) in view of Sun (CN 116007624 A) in further view of Zhu (CN 106251016 B) in further view of Zhang (CN-113821039A).
Regarding claim 22, the combination of Zhao, Sun, and Zhu teaches the multi-mobile vehicle control system according to claim 17(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types),
wherein in performing traffic path movement of multi-mobile vehicles(Zhao, paragraph 9, multi-AGV intelligent cooperative scheduling method),
The combination of Zhao, Sun, and Zhu specifically fails to disclose a system with the control unit or the mobile vehicles are configured for: updating an actual exit time of a mobile vehicle from a current path unit, and compensating a time difference between the actual exit time and a planned exit time in a scheduled path timing of the mobile vehicle in a path server; determining whether there is a multi-mobile vehicle conflict or a path unit occupancy conflict with the at least other mobile vehicle in the scheduled path timing of the mobile vehicle; replanning the path unit where the multi-mobile vehicle conflict or the path unit occupancy conflict occurs; and controlling the mobile vehicle to move along a planned path to a target node.
However, Zhang, which is in the same analogous art and that teaches about path planning for AGVs discloses the control unit or the mobile vehicles are configured for: updating an actual exit time of a mobile vehicle from a current path unit (Zhang teaches Time_out which corresponds to the exit time of the mobile vehicle and teaches updating the exit time based on wait time. Zhang, paragraph 96, the update[d] time window time-out is time-out + t_wait (z). Zhang, paragraph 90, the entering time time-in is the time of the path planning starting time adding the virtual site from the starting station to the entering z, the leaving time-out is the maximum passing time of time-in adding z), and
compensating a time difference between the actual exit time and a planned exit time in a scheduled path timing of the mobile vehicle in a path server(Zhang discloses incorporating the time difference between panned road time window(tout) and extended node time window(t’out) which corresponds to the current exit time and planned exit time. Zhang, paragraph 104, calculating the common node conflict caused by the waiting time t-wait + = tout-t (wherein, z represents the extended node, [tin, tout] is the planned road time window, [t'in, t ' out] is extended node time window). judging whether the time window of the last node has new conflict. Zhang, paragraph 96, twait (z) = tout-t-out + ε, (wherein, z represents the expansion node, [tin, tout] is the planned road section time window, [t'in, t ' out] is the extended node time window, ε is the time of the vehicle passing through the controlled parking of the distance safety and is reduced to 0. Zhang, paragraph 11, a time window-based path planning program stored on the memory and running on the processor);
determining whether there is a multi-mobile vehicle conflict or a path unit occupancy conflict with the at least other mobile vehicle in the scheduled path timing of the mobile vehicle(Zhang, paragraph 70, performing conflict judgment according to the expansion node and the expansion node time window to obtain the conflict judging result);
replanning the path unit where the multi-mobile vehicle conflict or the path unit occupancy conflict occurs(Zhang, paragraph 159, when detecting the time window is abnormal, it needs to be AGV re-planning path); and
controlling the mobile vehicle to move along a planned path to a target node(Zhang, paragraph 61, controlling the vehicle to travel according to the planned path).
Therefore, it would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the teachings of Zhao, Sun, and Zhu with Zhang to incorporate different time window for conflict prevention. By incorporating time window, it is possible to combine the time window information of each area to perform path planning, which can effectively prevent occurrence of conflict of different vehicles, improve the passing efficiency of the road network, and ensure the safety.
Regarding claim 23, the combination of Zhao, Sun, Zhu, and Zhang teaches the multi-mobile vehicle control system according to claim 22(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types; Zhang, paragraph 96, the update[d] time window time-out is time-out + t_wait (z)), wherein the path unit occupancy conflict includes a forward conflict, a cross conflict, or a head-on conflict(Zhang, paragraph 156, if the two AGVs are oppositely running on one bidirectional road section, and the time window is overlapped, then the road section is formed to face to conflict. Zhang, paragraph 94, the conflict judging comprises: intersection conflict judgment, long road section conflict judgment and short section and dead end conflict judgment).
Regarding claim 24, the combination of Zhao, Sun, Zhu, and Zhang teaches the multi-mobile vehicle control system according to claim 22(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types; Zhang, paragraph 96, the update[d] time window time-out is time-out + t_wait (z)), wherein, when the mobile vehicle starts to leave the current path unit: when a conflict occurs in the current path unit after timing compensation, replanning the conflicted current path unit; occupying a next path unit(Zhang discloses exit time (tout) is used to evaluate the whether a collision is caused, and waiting to avoid a collision indicates a replanning of travel path. Zhang, paragraph 96, judging whether the new section time window is included in a certain planned road section time window, if it is included, then waiting for avoiding collision, calculating the waiting time twait, wherein twait (z) = tout-t-out + ε, (wherein, z represents the expansion node, [tin, tout] is the planned road section time window, [t'in, t ' out] is the extended node time window, ε is the time of the vehicle passing through the controlled parking of the distance safety and is reduced to 0. Zhang, paragraph 70, performing conflict judgment according to the expansion node and the expansion node time window to obtain the conflict judging result. Zhang, paragraph 159, when detecting the time window is abnormal, it needs to be AGV re-planning path); and releasing the current path unit(Zhu, paragraph 124, it is necessary from the time window vector table deleting the AGV in the table registration information. to release the road or the intersection resource for other AGV; in the step S4 so as to avoid in the time period occupied by the AGV, the other AGV to cause dead lock or collision), and updating data of the occupied next path unit and the released current path unit in the path server(Zhu discloses real-time processing of information when switching path and releasing path that indicates the updating of path data. Zhu, paragraph 49, in the step S4, a ground control system receiving the AGV will in real time in the running process of uploading position, speed and running state information….it is necessary from the time window vector table deleting the AGV in the table registration information to release the road or the intersection resource for other AGV; in the step S4 so as to avoid in the time period occupied by the AGV, the other AGV to cause dead lock or collision.).
Regarding claim 25, the combination of Zhao, Sun, Zhu, and Zhang teaches the multi-mobile vehicle control system according to claim 22(Zhao, paragraph 19, calculating the shortest path of all idle AGV car dispatching to the task starting point, and determining the starting time and the time cost from the task sending to the arrival task starting point; Sun, paragraph 159, the computer instruction can be from a website site, a computer, a server; Zhu, paragraph 67, detect what kind of conflict exists in the optimized path of the suboptimal task, and select an appropriate conflict resolution strategy according to the different conflict types; Zhang, paragraph 96, the update[d] time window time-out is time-out + t_wait (z)), wherein, when the mobile vehicle starts to enter the current path unit: releasing a previous path unit(Zhu, paragraph 49, if the AGV has left a certain road or certain intersection, it is necessary from the time window vector table deleting the AGV in the table registration information so as to release the road or the intersection resource for other AGV); updating an actual entry time of the mobile vehicle into the current path unit(Sun, paragraph 138, a time window updating module, for determining the first entrance time point and the first exit time point of each path node in the new current planning path of the intelligent body to be planed, updating the first path time period corresponding to the to-be-planed intelligent body in the three-dimensional time window), and compensating a time difference between the actual entry time and a planned entry time in a planned path schedule(Sun discloses an entry and exit time window wherein when determining collision, a delay and an updating of entry time is processed. The delay indicates a time different between planned entry and actual entry time. Sun, paragraph 89, it is assumed that the first driving time point of the planning agent under the current path node is Q1, the second driving-out time point of the target first type planned intelligent body under the current path node is P2, then the to-be-planned intelligent body under the current path node of the collision delay time delay Time=P2-Q1. Sun, paragraph 90, then, according to the collision delay time, it can set the first driving time point and the first driving-out time point of the intelligent body to be programmed under the current path node and each subsequent path node to delay the collision delay time, obtaining the new first driving time point and the first driving-out time point of the to-be-planned intelligent body under the current path node and each post-sequence path node, so as to update the corresponding channel time period information of the to-be-planned intelligent body in the three-dimensional time window); when a conflict occurs in the current path unit after timing compensation, replanning the conflicted current path unit; and occupying the current path unit(Sun, paragraph 131, determining the collision pushing time length of the to-be-planned intelligent body under the current path node; according to the collision delay time. Sun, paragraph 132, updating the first driving time point and the first driving-out time point of the to-be-planned intelligent body under the current path node and each subsequent path node), and updating data of the released previous path unit and the occupied current path unit in the path server(Sun, paragraph 127, updating the target path sequence from the current path node to the target path node in the current planning path, obtaining a new current planning path and a new next path node, to continue to determine whether the second type collision exists in the current sub-path from the current path node to the new next path node by the to-be-planned intelligent body and any one of the second-type programmed intelligent body. Sun, paragraph 113, it needs to re-determine the first driving time point and the first driving-out time point of each path node in the new current planning path to be programmed, and updating the first path time period corresponding to the to-be-planned intelligent body in the three-dimensional time window).
Prior Art of Record
The prior art made of record and not relied upon is considered pertinent to applicant’s
disclosure.
Li (CN 116184996 A) discloses selecting robot with a conflict number value greater than the preset number as the target robot.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to BESUFEKAD LEMMA TESSEMA whose telephone number is (571)272-6850. The examiner can normally be reached Monday - Friday 9:00 am - 5:00 pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Hunter Lonsberry can be reached at 5712727298. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/BESUFEKAD LEMMA TESSEMA/Examiner, Art Unit 3665
/HUNTER B LONSBERRY/Supervisory Patent Examiner, Art Unit 3665
Prosecution Insights