DETAILED ACTION
This communication is a Non-Final Office Action rejection on the merits. Claims 1-11 and 15 are currently pending and have been addressed below.
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 .
Status of Claims
Applicant’s amendment date 11/17/2025, Amending Claims 1 and 15.
Patent Subject Matter Eligibility
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-11 and 15 are not rejected under 35 U.S.C. 101 because the claimed invention includes an additional element that integrates the judicial exception into a practical application.
Claims 1 and 15 are eligible. The additional element of Graph Neural Network (GNN) is used to dynamically output assignment instructions for autonomously controlling each vehicle which is assigned to a transport task according to the selected optimized assignment to perform the transport task (see Paragraphs 0004 & 0084). As explained in the specification, this allows a service provider to autonomously execute a transport task in a highly dynamic scenario. Therefore, it is possible to optimize allocation of vehicles to transport tasks based on real-time changes in the weights (Paragraph 0003, possible benefits include customer satisfaction, efficient operation and energy consumption, efficient approaches for controlling vehicles, etc.). The additional element adds a meaningful limitation that integrates the judicial exception into a practical application. The claim is eligible.
Dependent claims 2-11 are eligible because their dependency on independent claim 1.
Response to Arguments
Applicant's arguments filed on 11/17/2025 (related to the 103 Rejection) have been fully considered but are moot in view of new grounds of rejection. Applicant's amendments necessitated the new ground(s) of rejection presented in this Office action. Rejection based on a newly cited reference(s) follows.
Claim Rejections - 35 USC § 103
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 set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied 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.
Claims 1, 3-4, 6-7, 9-11, and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Tang et al. (US 2022/0270488 A1), in view of Taitler et al. (US 2021/0312280 A1).
Regarding claim 1 (Currently Amended), Tang et al. discloses a method for controlling vehicles to perform transport tasks comprising (Paragraph 0001, The disclosure relates generally to vehicle dispatching in a ride-hailing platform, specifically, real-time order dispatching and vehicle repositioning in a mobility-on-demand (MoD) platform with reinforcement learning; Paragraph 0045, In one embodiment, the vehicle may be autonomous, and the data 128 may be sent to an in-vehicle computer, causing the in-vehicle computer to send instructions to various components (e.g., motor, steering component) of the vehicle to proceed to a location to pick up a passenger for the assigned transportation trip; Paragraph 0080, FIG. 4A illustrates an exemplary method 400 for vehicle dispatching in a ride-hailing platform, in accordance with various embodiments):
supplying information about the vehicles and information about the transport tasks to a … neural network by associating each vehicle with a graph node of a vehicle graph and each transport task with a graph node of a transport task graph (Paragraph 0048, In some embodiments, the online system 210 includes an online state value network 212, and a dispatching engine 214. The online system 210 may be associated with a vehicle fleet 216. The vehicle fleet 216 includes a plurality of vehicles that are either serving ride orders or waiting for dispatching. The online state value network 212 may include an online-trained neural network that predicts a state value for a given vehicle state. Here, the “vehicle state” may include various information, such as temporal information and spatial information of the vehicle (e.g., the current time and the current location of the vehicle), features of the vehicle, other contextual features (e.g., weather, event, supply-demand in the neighboring area), or any combination thereof. The online state value network 212 may be used for determining vehicle dispatching for the vehicles in the vehicle fleet 216, and be trained in real-time based on the state transitions caused by the vehicle dispatching; Paragraph 0067, Order-dispatching subsystem 364 of ride-hailing platforms may be a multi-agent environment with multiple drivers making sequential decisions; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite matching problem that maximizes an objective function; Examiner notes that a bipartite matching problem is a graph problem with nodes and edges. In this case, each vehicle/driver is associated with a current or predicted location and time. Also, each passenger/order is associated with a requested time and location);
processing the vehicle graph and the transport task graph by the … neural network, wherein the … neural network trained to determine a feature for each graph node of a graph it processes (Paragraph 0048, In some embodiments, the online system 210 includes an online state value network 212, and a dispatching engine 214. The online system 210 may be associated with a vehicle fleet 216. The vehicle fleet 216 includes a plurality of vehicles that are either serving ride orders or waiting for dispatching. The online state value network 212 may include an online-trained neural network that predicts a state value for a given vehicle state. Here, the “vehicle state” may include various information, such as temporal information and spatial information of the vehicle (e.g., the current time and the current location of the vehicle), features of the vehicle, other contextual features (e.g., weather, event, supply-demand in the neighboring area), or any combination thereof; Paragraph 0050, As shown in FIG. 2, the offline system 202 may include a historical data collector 231 and the offline state value network 230 (e.g., a neural network) trained based on historical data collected by the historical data collector 231. For example, the historical data collector 231 may collect vehicle trajectories for a period of time, each vehicle trajectory includes a series of vehicle state transitions as a result of vehicle dispatching and corresponding rewards. The offline state value network 230 may be trained based on these series of vehicle state transitions to predict rewards for given vehicle states);
determining, by the … neural network, for each pair of a graph node of the transport task graph and a graph node of the vehicle graph, a weight representing a similarity between the feature determined for the graph node of the transport task graph and the graph node of the vehicle graph (Paragraph 0046, FIG. 2 illustrates an exemplary diagram of a self-learning online vehicle dispatching system 200, in accordance with various embodiments of the disclosure; Paragraph 0049, Each sub-engine may construct its objective function defining one or more metrics to be maximized (e.g. , a cumulative reward) or minimized (e.g., a waiting time) as a result of the corresponding dispatching decisions; Paragraph 0053, Based on the unified state value network 330, a unified optimization framework may be constructed for making decisions for order dispatching 310 and online vehicle repositioning 320; Paragraph 0054, In some embodiments, the state value network 330 may be trained online based on vehicle states of the plurality of vehicles observed before and after the dispatching and rewards associated with the dispatching; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite marching problem that maximizes an objective function 364A; Examiner interprets the “utility score” or “reward” as the “weight representing a similarity between the transport task and the vehicle graph”);
…;
selecting an assignment between graph nodes of the transport task graph and graph nodes of the vehicle graph from a set of possible assignments, …, wherein the selected assignment maximizes, among the possible assignments, a sum, over pairs of graph node of the transport task graph and graph node of the vehicle graph which are assigned to each other, of weights of the pairs (Paragraph 0068, In some embodiments, the process for determining the order/vehicle pairings may include: for each dispatching pair comprising a pending ride order and one of the one or more vehicles, determining a dispatching value using the online state value network; constructing an objective function comprising a plurality of dispatching values respectively corresponding to a plurality of decision variables; determining the plurality of decision variables that maximizes the objective function; and dispatching the one or more of the plurality of vehicles to serve the one or more pending ride orders according to the plurality of decision variables; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite marching problem that maximizes an objective function 364A; Paragraph 0071, weighted by the parameter Ω, e.g., the objective of minimizing the waiting time for the passenger may be obtained by including negative forms of the driver-passenger distances in U.sub.ij);
and autonomously controlling each vehicle which is assigned to a transport task according to the selected assignment to perform the transport task (Paragraph 0045, In one embodiment, the vehicle may be autonomous, and the data 128 may be sent to an in-vehicle computer, causing the in-vehicle computer to send instructions to various components (e.g., motor, steering component) of the vehicle to proceed to a location to pick up a passenger for the assigned transportation trip).
Tang et al. discloses a neural network used for determining a feature for each graph node (Paragraph 0048, predicting a state value of the vehicle). Although Tang further discloses wherein the matching problem may be solved by using a bipartite matching problem that maximizes an objective function (Paragraphs 0068-0069) or using a self-learning decision engine that maximizes an objective function based on cumulative rewards (Paragraphs 0048 & 0052-0055), Tang et al. does not specifically disclose wherein the self-learning decision engine is a graph neural network (see Applicant’s specification, Paragraphs 0035-0037).
However, Taitler et al. discloses supplying information about the [machines] and information about the [jobs] to a graph neural network by associating each [job] with a graph node of a [job] graph and each [job] with a graph node of a [job] graph (Paragraph 0015, It is provided that the GNN receives as input a, in particular bipartite and undirected, graph, which comprises two disjoint independent sets of nodes (U,V), where the first set of node (U) comprises for each machine its current state and the second set of node (V) comprises the features of each job within the set of jobs. Furthermore, the graph comprises a set of edges (E), wherein the edges characterize a connection between nodes of the first set of nodes with nodes of the second set of nodes. Additionally, the graph comprises a global information vector relevant for the entire graph. It can be initialized to zero);
processing the [machine] graph and the [job] task graph by the graph neural network, wherein the graph neural network is a neural network trained to determine a feature for each graph node of a graph it processes (Paragraph 0014, The GNN outputs a, in particular expected cumulative discounted, reward for the set of jobs if hypothetically launched on the machines, which states are inputted into the GNN. It can be said that the greater the reward the lower the expected total completion time. The job for the free machine is selected depending on the Graph Neural Network output, which achieves the highest reward. Then, one of the free machines or the free machine can receive a command to carry out the selected job; Paragraph 0059, For learning the Q function, a simulator of the machines is applied that models the problem as a discrete event simulation. Preferably, a simulated factory, a.k.a. “digital twin”, is applied that reflects the dynamics of a real factory, i.e., how the state of the factory changes when a job is started on a machine and how additional tasks arrive over time. In an alternative embodiment, recorded data from the machines or from the factory can be used as training data for learning the Q function or the recoded data can be used to build the simulator. As already stated above, the DGN learning is preferably utilized to learn the Q function and train the GNN; Paragraph 0060, After the GNN is trained, it can be straight forward applied to schedule jobs on a plurality of machines. For example, if a decision point occurs, the above described inputs of the GNN are proceed of the current situation at the point of time when the decision point occurs. Depending on the output of the GNN, from the set of waiting jobs, the next job is selected with the highest Q value. This procedure can be applied each time, if decision points occur. Interestingly, this procedure is neither limited to static nor to dynamic settings);
determining, by the graph neural network, for each pair of a graph node of the [job] graph and a graph node of the [machine], a weight representing a similarity between the feature determined for the graph node of the [job] graph and the graph node of the [machine] graph (Paragraph 0014, The GNN outputs a, in particular expected cumulative discounted, reward for the set of jobs if hypothetically launched on the machines, which states are inputted into the GNN. It can be said that the greater the reward the lower the expected total completion time. The job for the free machine is selected depending on the Graph Neural Network output, which achieves the highest reward. Then, one of the free machines or the free machine can receive a command to carry out the selected job.; Paragraph 0035, Note that said job scheduler can be readily extended to other online combinatorial problems such as the travelling salesperson problem and vehicle routing problems; Paragraph 0075, If the queue of jobs is subsequently proceeded, if a decision point is reached, either the MCTS can be again applied and the next job is not selected from the order of the queue, instead the next job is selected via the updated queue determined by the MCTS search tree, or the next job is selected only depending on the Q value of the GNN, or the order of the queue is further utilized; Examiner interprets the “job with the highest reward” as the “weight.” In this case, the GNN is used to learn which features achieve the highest reward (e.g., weight) for a graph matching problem. See paragraph 0037 of Applicant’s specification);
capturing, by the graph neural network, dynamic real-time changes in the weights (Paragraph 0012, The job is selected as follows. A Graph Neural Network (GNN) receives as input the set of jobs and a current state of at least the machine which is free. The GNN is trained to estimate a reward, which would be obtained when carry out a job such that the total completion time is minimized. More precisely, the GNN is trained to output a high reward for a small completion time of the set of jobs; Paragraph 0059, For learning the Q function, a simulator of the machines is applied that models the problem as a discrete event simulation. Preferably, a simulated factory, a.k.a. “digital twin”, is applied that reflects the dynamics of a real factory, i.e., how the state of the factory changes when a job is started on a machine and how additional tasks arrive over time. In an alternative embodiment, recorded data from the machines or from the factory can be used as training data for learning the Q function or the recoded data can be used to build the simulator. As already stated above, the DGN learning is preferably utilized to learn the Q function and train the GNN; Paragraph 0060, After the GNN is trained, it can be straight forward applied to schedule jobs on a plurality of machines. For example, if a decision point occurs, the above described inputs of the GNN are proceed of the current situation at the point of time when the decision point occurs. Depending on the output of the GNN, from the set of waiting jobs, the next job is selected with the highest Q value. This procedure can be applied each time, if decision points occur. Interestingly, this procedure is neither limited to static nor to dynamic settings; Examiner interprets the “job with the highest reward” as the “weight.” In this case, the GNN is used to learn which features achieve the highest reward (e.g., weight) for a graph matching problem. See paragraph 0037 of Applicant’s specification);
selecting an assignment between graph nodes of the [job] graph and graph nodes of the [machine] graph from a set of possible assignments, based on the real-time changes in the weights, wherein the selected assignment maximizes, among the possible assignments, a sum, over pairs of graph node of the [job] graph and graph node of the [machine] graph which are assigned to each other, of weights of the pairs (Paragraph 0012, The job is selected as follows. A Graph Neural Network (GNN) receives as input the set of jobs and a current state of at least the machine which is free. The GNN is trained to estimate a reward, which would be obtained when carry out a job such that the total completion time is minimized. More precisely, the GNN is trained to output a high reward for a small completion time of the set of jobs; Paragraph 0059, For learning the Q function, a simulator of the machines is applied that models the problem as a discrete event simulation. Preferably, a simulated factory, a.k.a. “digital twin”, is applied that reflects the dynamics of a real factory, i.e., how the state of the factory changes when a job is started on a machine and how additional tasks arrive over time. In an alternative embodiment, recorded data from the machines or from the factory can be used as training data for learning the Q function or the recoded data can be used to build the simulator. As already stated above, the DGN learning is preferably utilized to learn the Q function and train the GNN; Paragraph 0060, After the GNN is trained, it can be straight forward applied to schedule jobs on a plurality of machines. For example, if a decision point occurs, the above described inputs of the GNN are proceed of the current situation at the point of time when the decision point occurs. Depending on the output of the GNN, from the set of waiting jobs, the next job is selected with the highest Q value. This procedure can be applied each time, if decision points occur. Interestingly, this procedure is neither limited to static nor to dynamic settings; Examiner interprets the “job with the highest reward” as the “weight.” In this case, the GNN is used to learn which features achieve the highest reward (e.g., weight) for a graph matching problem. See paragraph 0037 of Applicant’s specification);
and … each [machine] which is assigned to a [job] according to the selected assignment to perform the [job] (Paragraph 0036, In general, the job scheduler shall be able to solve an online scheduling, a particular online combinatorial problem. Note that said job scheduler can be readily extended to other online combinatorial problems such as the travelling salesperson problem and vehicle routing problems, e.g. where the destinations are added online. The online combinatorial optimization problems, including online logistics problems (e.g., planning the route of a courier through a city, where additional points to pick up/drop off items are added while the courier is on his way).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein a neural network is used to predict a vehicle state value and a bipartite graph or self-learning decision engine is used to select a vehicle by solving a vehicle-passenger matching problem that maximizes an objective function of the invention of Tang et al. to further specify wherein a Graph Neural Network (GNN) is used to make a scheduling decisions based on dynamic real-time changes in the weights of the invention of Taitler et al. because doing so would allow the method to use a GNN to achieve better performance when decisions need to be made quickly, wherein the GNN may be used to solve vehicle routing problems (see Taitler et al., Paragraphs 0007 & 0036). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 3 (Previously Amended), which is dependent of claim 1, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 1. Tang et al. further discloses wherein selecting the assignment comprises applying an assignment problem algorithm to a bipartite graph having the vehicle graph as first graph component, the transport task graph as second graph component, and edges between the first graph component and the second graph component with the determined weights (Paragraph 0068, In some embodiments, the process for determining the order/vehicle pairings may include: for each dispatching pair comprising a pending ride order and one of the one or more vehicles, determining a dispatching value using the online state value network; constructing an objective function comprising a plurality of dispatching values respectively corresponding to a plurality of decision variables; determining the plurality of decision variables that maximizes the objective function; and dispatching the one or more of the plurality of vehicles to serve the one or more pending ride orders according to the plurality of decision variables; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite marching problem that maximizes an objective function 364A; Paragraph 0071, weighted by the parameter Ω, e.g., the objective of minimizing the waiting time for the passenger may be obtained by including negative forms of the driver-passenger distances in U.sub.ij; Paragraph 0044, The computing device 110 may be associated with a passenger seeking a carpool transportation ride. The query 124 may comprise information such as current date and time, trip information (e.g., origin, destination, fees), etc. In the meanwhile, the system 102 may have been collecting data 126 from a plurality of computing devices such as the computing device 111. The computing device 111 may be associated with a driver of a vehicle described herein (e.g., taxi, a service-hailing vehicle). The data 126 may comprise information such as a current location of the vehicle, a current time, an on-going trip (origin, destination, time, fees) associated with the vehicle, etc.; Examiner notes that a bipartite matching problem is a graph problem with nodes and edges. In this case, each vehicle/driver is associated with a current or predicted location and time. Also, each passenger/order is associated with a requested time and location).
Regarding claim 4 (Original), which is dependent of claim 3, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 3. Tang et al. further discloses wherein the assignment problem algorithm is a min-sum or a max-sum algorithm (Paragraph 0068, In some embodiments, the process for determining the order/vehicle pairings may include: for each dispatching pair comprising a pending ride order and one of the one or more vehicles, determining a dispatching value using the online state value network; constructing an objective function comprising a plurality of dispatching values respectively corresponding to a plurality of decision variables; determining the plurality of decision variables that maximizes the objective function; and dispatching the one or more of the plurality of vehicles to serve the one or more pending ride orders according to the plurality of decision variables; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite marching problem that maximizes an objective function 364A; Paragraph 0071, weighted by the parameter Ω, e.g., the objective of minimizing the waiting time for the passenger may be obtained by including negative forms of the driver-passenger distances in U.sub.ij).
Regarding claim 6 (Previously Amended), which is dependent of claim 3, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 3. Although Tang et al. discloses applying an assignment problem algorithm, Tang et al. does not specifically disclose wherein the assignment problem algorithm is differentiable.
However, Taitler et al. further discloses wherein the assignment problem algorithm is differentiable (Paragraph 0054, A GNN is utilized as Q function approximation in the DQN algorithm implementation. GNN is a common name for a framework, where a neural network or a set of neural networks is repetitively applied to the graph representation of the input data; Paragraph 0060, After the GNN is trained, it can be straight forward applied to schedule jobs on a plurality of machines. For example, if a decision point occurs, the above described inputs of the GNN are proceed of the current situation at the point of time when the decision point occurs. Depending on the output of the GNN, from the set of waiting jobs, the next job is selected with the highest Q value. This procedure can be applied each time, if decision points occur. Interestingly, this procedure is neither limited to static nor to dynamic settings; Examiner interprets “using a GNN to approximate a function” as the “differentiable algorithm,” see Paragraph 0049 of Applicant’s specification. As known by an ordinary skill in the art, “differentiable” means that the function can be approximated locally by a linear function).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein scheduling/selecting the vehicle comprises applying an assignment problem algorithm to a bipartite graph or self-learning decision engine of the invention of Tang et al. to further specify wherein the assignment problem algorithm is differentiable of the invention of Taitler et al. because doing so would allow the method to use a trained GNN to select a job/task that achieves the highest reward (see Taitler et al., Paragraph 0014). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 7 (Previously Amended), which is dependent of claim 1, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 1. Tang et al. further discloses supplying, for each vehicle, information about the vehicle as one or more input feature values for the graph node of the vehicle graph associated with the vehicle to the … neural network, and, for each transport task, information about the transport task as one or more input feature values for the graph node of the transport task graph associated with the transport task to the … neural network (Paragraph 0048, In some embodiments, the online system 210 includes an online state value network 212, and a dispatching engine 214. The online system 210 may be associated with a vehicle fleet 216. The vehicle fleet 216 includes a plurality of vehicles that are either serving ride orders or waiting for dispatching. The online state value network 212 may include an online-trained neural network that predicts a state value for a given vehicle state. Here, the “vehicle state” may include various information, such as temporal information and spatial information of the vehicle (e.g., the current time and the current location of the vehicle), features of the vehicle, other contextual features (e.g., weather, event, supply-demand in the neighboring area), or any combination thereof. The online state value network 212 may be used for determining vehicle dispatching for the vehicles in the vehicle fleet 216, and be trained in real-time based on the state transitions caused by the vehicle dispatching; Paragraph 0067, Order-dispatching subsystem 364 of ride-hailing platforms may be a multi-agent environment with multiple drivers making sequential decisions; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite matching problem that maximizes an objective function; Examiner notes that a bipartite matching problem is a graph problem with nodes and edges. In this case, each vehicle/driver is associated with a current or predicted location and time. Also, each passenger/order is associated with a requested time and location).
Although Tang et al. discloses a trained neural network for determining a feature for each graph node (e.g., predicting a state value for a given vehicle state), Tang et al. does not specifically disclose wherein the neural network is a graph neural network.
However, Taitler et al. discloses supplying, for each [machine], information about the [machines] as one or more input feature values for the graph node of the [machine] graph associated with the [machine] to the graph neural network, and, for each [job], information about the [job] as one or more input feature values for the graph node of the [job] graph associated with the [job] to the graph neural network (Paragraph 0014, The GNN outputs a, in particular expected cumulative discounted, reward for the set of jobs if hypothetically launched on the machines, which states are inputted into the GNN. It can be said that the greater the reward the lower the expected total completion time. The job for the free machine is selected depending on the Graph Neural Network output, which achieves the highest reward. Then, one of the free machines or the free machine can receive a command to carry out the selected job; Paragraph 0015, It is provided that the GNN receives as input a, in particular bipartite and undirected, graph, which comprises two disjoint independent sets of nodes (U,V), where the first set of node (U) comprises for each machine its current state and the second set of node (V) comprises the features of each job within the set of jobs. Furthermore, the graph comprises a set of edges (E), wherein the edges characterize a connection between nodes of the first set of nodes with nodes of the second set of nodes. Additionally, the graph comprises a global information vector relevant for the entire graph. It can be initialized to zero).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein a neural network is used to predict a vehicle state value and a bipartite graph or self-learning decision engine is used to select a vehicle by solving a vehicle-passenger matching problem that maximizes an objective function of the invention of Tang et al. to further incorporate using a Graph Neural Network (GNN) of the invention of Taitler et al. because doing so would allow the method to use a trained GNN to select a job/task that achieves the highest reward (see Taitler et al., Paragraph 0014). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 9 (Previously Amended), which is dependent of claim 1, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 1. Tang et al. further discloses wherein, for at least some of the vehicles, the information about the vehicles comprises location information of the vehicles (Paragraph 0044, The computing device 111 may be associated with a driver of a vehicle described herein (e.g., taxi, a service-hailing vehicle). The data 126 may comprise information such as a current location of the vehicle, a current time, an on-going trip (origin, destination, time, fees) associated with the vehicle, etc.).
Regarding claim 10 (Previously Amended), which is dependent of claim 1, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 1. Tang et al. further discloses wherein each transport task comprises picking up an object or person to transport and, for at least some of the transport tasks, the information about the transport tasks comprises location information about where the object or person needs to be picked up (Paragraph 0044, The computing device 110 may be associated with a passenger seeking a carpool transportation ride. The query 124 may comprise information such as current date and time, trip information (e.g., origin, destination, fees), etc. In the meanwhile, the system 102 may have been collecting data 126 from a plurality of computing devices such as the computing device 111; It can be noted that the claim language is written in alternative form. The limitation taught by Tang et al. is based on “picking up a person").
Regarding claim 11 (Previously Amended), which is dependent of claim 1, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 1. Although Tang et al. discloses training a neural network using reinforcement learning (see at least Paragraph 0050, train a neural network for predicting rewards for given vehicle states), Tang et al. does not specifically disclose training a graph neural network using reinforcement learning.
However, Taitler et al. discloses training the graph neural network using reinforcement learning (Paragraph 0023, In accordance with an example embodiment of the present invention, it is further provided that a parametrization e of the Graph Neural Network is optimized by reinforcement learning, in particular by deep Q-Network learning. Preferably, a simulated factory, referred to as a digital twin, is used for the reinforcement learning that reflects the dynamics of the real factory, more precisely, how the state of a factory changes when a job is started. It can be said that the simulated factory corresponds to an environment in which an agent of the reinforcement learning algorithms operates and optimizes its policy).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein a neural network is used to predict a vehicle state value and a bipartite graph or self-learning decision engine is used to select a vehicle by solving a vehicle-passenger matching problem that maximizes an objective function of the invention of Tang et al. to further incorporate using a Graph Neural Network (GNN) of the invention of Taitler et al. because doing so would allow the method to use a trained GNN to select a job/task that achieves the highest reward (see Taitler et al., Paragraph 0014). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Regarding claim 15 (Currently Amended), Tang et al. discloses a non-transitory computer-readable medium comprising program instructions, which, when executed by one or more processors, cause the one or more processors to perform a method for controlling vehicles to perform transport tasks, the method comprising (Paragraph 0004, Various embodiments of the specification include, but are not limited to, cloud-based systems, methods, and non-transitory computer-readable media for vehicle dispatching in ride-hailing platform; Paragraph 0037, As shown in FIG. 1A, the exemplary system 100 may comprise at least one computing system 102 that includes one or more processors 104 and one or more memories 106; Paragraph 0045, In one embodiment, the vehicle may be autonomous, and the data 128 may be sent to an in-vehicle computer, causing the in-vehicle computer to send instructions to various components (e.g., motor, steering component) of the vehicle to proceed to a location to pick up a passenger for the assigned transportation trip;):
supplying information about the vehicles and information about the transport tasks to a … neural network by associating each vehicle with a graph node of a vehicle graph and each transport task with a graph node of a transport task graph (Paragraph 0048, In some embodiments, the online system 210 includes an online state value network 212, and a dispatching engine 214. The online system 210 may be associated with a vehicle fleet 216. The vehicle fleet 216 includes a plurality of vehicles that are either serving ride orders or waiting for dispatching. The online state value network 212 may include an online-trained neural network that predicts a state value for a given vehicle state. Here, the “vehicle state” may include various information, such as temporal information and spatial information of the vehicle (e.g., the current time and the current location of the vehicle), features of the vehicle, other contextual features (e.g., weather, event, supply-demand in the neighboring area), or any combination thereof. The online state value network 212 may be used for determining vehicle dispatching for the vehicles in the vehicle fleet 216, and be trained in real-time based on the state transitions caused by the vehicle dispatching; Paragraph 0067, Order-dispatching subsystem 364 of ride-hailing platforms may be a multi-agent environment with multiple drivers making sequential decisions; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite matching problem that maximizes an objective function; Examiner notes that a bipartite matching problem is a graph problem with nodes and edges. In this case, each vehicle/driver is associated with a current or predicted location and time. Also, each passenger/order is associated with a requested time and location);
processing the vehicle graph and the transport task graph by the … neural network, wherein the … neural network trained to determine a feature for each graph node of a graph it processes (Paragraph 0048, In some embodiments, the online system 210 includes an online state value network 212, and a dispatching engine 214. The online system 210 may be associated with a vehicle fleet 216. The vehicle fleet 216 includes a plurality of vehicles that are either serving ride orders or waiting for dispatching. The online state value network 212 may include an online-trained neural network that predicts a state value for a given vehicle state. Here, the “vehicle state” may include various information, such as temporal information and spatial information of the vehicle (e.g., the current time and the current location of the vehicle), features of the vehicle, other contextual features (e.g., weather, event, supply-demand in the neighboring area), or any combination thereof; Paragraph 0050, As shown in FIG. 2, the offline system 202 may include a historical data collector 231 and the offline state value network 230 (e.g., a neural network) trained based on historical data collected by the historical data collector 231. For example, the historical data collector 231 may collect vehicle trajectories for a period of time, each vehicle trajectory includes a series of vehicle state transitions as a result of vehicle dispatching and corresponding rewards. The offline state value network 230 may be trained based on these series of vehicle state transitions to predict rewards for given vehicle states);
determining, by the … neural network, for each pair of a graph node of the transport task graph and a graph node of the vehicle graph, a weight representing a similarity between the feature determined for the graph node of the transport task graph and the graph node of the vehicle graph (Paragraph 0046, FIG. 2 illustrates an exemplary diagram of a self-learning online vehicle dispatching system 200, in accordance with various embodiments of the disclosure; Paragraph 0049, Each sub-engine may construct its objective function defining one or more metrics to be maximized (e.g. , a cumulative reward) or minimized (e.g., a waiting time) as a result of the corresponding dispatching decisions; Paragraph 0053, Based on the unified state value network 330, a unified optimization framework may be constructed for making decisions for order dispatching 310 and online vehicle repositioning 320; Paragraph 0054, In some embodiments, the state value network 330 may be trained online based on vehicle states of the plurality of vehicles observed before and after the dispatching and rewards associated with the dispatching; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite marching problem that maximizes an objective function 364A; Examiner interprets the “utility score” or “reward” as the “weight representing a similarity between the transport task and the vehicle graph”);
…;
selecting an assignment between graph nodes of the transport task graph and graph nodes of the vehicle graph from a set of possible assignments, …, wherein the selected assignment maximizes, among the possible assignments, a sum, over pairs of graph node of the transport task graph and graph node of the vehicle graph which are assigned to each other, of weights of the pairs (Paragraph 0068, In some embodiments, the process for determining the order/vehicle pairings may include: for each dispatching pair comprising a pending ride order and one of the one or more vehicles, determining a dispatching value using the online state value network; constructing an objective function comprising a plurality of dispatching values respectively corresponding to a plurality of decision variables; determining the plurality of decision variables that maximizes the objective function; and dispatching the one or more of the plurality of vehicles to serve the one or more pending ride orders according to the plurality of decision variables; Paragraph 0069, For example, a utility score ρ.sub.ij may be determined as a value for matching a driver i and an order j. Accordingly, a global order dispatching strategy 364B in each dispatching round may be determined by solving a bipartite marching problem that maximizes an objective function 364A; Paragraph 0071, weighted by the parameter Ω, e.g., the objective of minimizing the waiting time for the passenger may be obtained by including negative forms of the driver-passenger distances in U.sub.ij);
and controlling each vehicle which is assigned to a transport task according to the selected assignment to perform the transport task (Paragraph 0045, In one embodiment, the vehicle may be autonomous, and the data 128 may be sent to an in-vehicle computer, causing the in-vehicle computer to send instructions to various components (e.g., motor, steering component) of the vehicle to proceed to a location to pick up a passenger for the assigned transportation trip).
Tang et al. discloses a neural network used for determining a feature for each graph node (Paragraph 0048, predicting a state value of the vehicle). Although Tang further discloses wherein the matching problem may be solved by using a bipartite matching problem that maximizes an objective function (Paragraphs 0068-0069) or using a self-learning decision engine that maximizes an objective function based on cumulative rewards (Paragraphs 0048 & 0052-0055), Tang et al. does not specifically disclose wherein the self-learning decision engine is a graph neural network (see Applicant’s specification, Paragraphs 0035-0037).
However, Taitler et al. discloses supplying information about the [machines] and information about the [jobs] to a graph neural network by associating each [job] with a graph node of a [job] graph and each [job] with a graph node of a [job] graph (Paragraph 0015, It is provided that the GNN receives as input a, in particular bipartite and undirected, graph, which comprises two disjoint independent sets of nodes (U,V), where the first set of node (U) comprises for each machine its current state and the second set of node (V) comprises the features of each job within the set of jobs. Furthermore, the graph comprises a set of edges (E), wherein the edges characterize a connection between nodes of the first set of nodes with nodes of the second set of nodes. Additionally, the graph comprises a global information vector relevant for the entire graph. It can be initialized to zero);
processing the [machine] graph and the [job] task graph by the graph neural network, wherein the graph neural network is a neural network trained to determine a feature for each graph node of a graph it processes (Paragraph 0014, The GNN outputs a, in particular expected cumulative discounted, reward for the set of jobs if hypothetically launched on the machines, which states are inputted into the GNN. It can be said that the greater the reward the lower the expected total completion time. The job for the free machine is selected depending on the Graph Neural Network output, which achieves the highest reward. Then, one of the free machines or the free machine can receive a command to carry out the selected job; Paragraph 0059, For learning the Q function, a simulator of the machines is applied that models the problem as a discrete event simulation. Preferably, a simulated factory, a.k.a. “digital twin”, is applied that reflects the dynamics of a real factory, i.e., how the state of the factory changes when a job is started on a machine and how additional tasks arrive over time. In an alternative embodiment, recorded data from the machines or from the factory can be used as training data for learning the Q function or the recoded data can be used to build the simulator. As already stated above, the DGN learning is preferably utilized to learn the Q function and train the GNN; Paragraph 0060, After the GNN is trained, it can be straight forward applied to schedule jobs on a plurality of machines. For example, if a decision point occurs, the above described inputs of the GNN are proceed of the current situation at the point of time when the decision point occurs. Depending on the output of the GNN, from the set of waiting jobs, the next job is selected with the highest Q value. This procedure can be applied each time, if decision points occur. Interestingly, this procedure is neither limited to static nor to dynamic settings);
determining, by the graph neural network, for each pair of a graph node of the [job] graph and a graph node of the [machine], a weight representing a similarity between the feature determined for the graph node of the [job] graph and the graph node of the [machine] graph (Paragraph 0014, The GNN outputs a, in particular expected cumulative discounted, reward for the set of jobs if hypothetically launched on the machines, which states are inputted into the GNN. It can be said that the greater the reward the lower the expected total completion time. The job for the free machine is selected depending on the Graph Neural Network output, which achieves the highest reward. Then, one of the free machines or the free machine can receive a command to carry out the selected job.; Paragraph 0035, Note that said job scheduler can be readily extended to other online combinatorial problems such as the travelling salesperson problem and vehicle routing problems; Paragraph 0075, If the queue of jobs is subsequently proceeded, if a decision point is reached, either the MCTS can be again applied and the next job is not selected from the order of the queue, instead the next job is selected via the updated queue determined by the MCTS search tree, or the next job is selected only depending on the Q value of the GNN, or the order of the queue is further utilized; Examiner interprets the “job with the highest reward” as the “weight.” In this case, the GNN is used to learn which features achieve the highest reward (e.g., weight) for a graph matching problem. See paragraph 0037 of Applicant’s specification);
capturing, by the graph neural network, dynamic real-time changes in the weights (Paragraph 0012, The job is selected as follows. A Graph Neural Network (GNN) receives as input the set of jobs and a current state of at least the machine which is free. The GNN is trained to estimate a reward, which would be obtained when carry out a job such that the total completion time is minimized. More precisely, the GNN is trained to output a high reward for a small completion time of the set of jobs; Paragraph 0059, For learning the Q function, a simulator of the machines is applied that models the problem as a discrete event simulation. Preferably, a simulated factory, a.k.a. “digital twin”, is applied that reflects the dynamics of a real factory, i.e., how the state of the factory changes when a job is started on a machine and how additional tasks arrive over time. In an alternative embodiment, recorded data from the machines or from the factory can be used as training data for learning the Q function or the recoded data can be used to build the simulator. As already stated above, the DGN learning is preferably utilized to learn the Q function and train the GNN; Paragraph 0060, After the GNN is trained, it can be straight forward applied to schedule jobs on a plurality of machines. For example, if a decision point occurs, the above described inputs of the GNN are proceed of the current situation at the point of time when the decision point occurs. Depending on the output of the GNN, from the set of waiting jobs, the next job is selected with the highest Q value. This procedure can be applied each time, if decision points occur. Interestingly, this procedure is neither limited to static nor to dynamic settings; Examiner interprets the “job with the highest reward” as the “weight.” In this case, the GNN is used to learn which features achieve the highest reward (e.g., weight) for a graph matching problem. See paragraph 0037 of Applicant’s specification);
selecting an assignment between graph nodes of the [job] graph and graph nodes of the [machine] graph from a set of possible assignments, based on the real-time changes in the weights, wherein the selected assignment maximizes, among the possible assignments, a sum, over pairs of graph node of the [job] graph and graph node of the [machine] graph which are assigned to each other, of weights of the pairs (Paragraph 0012, The job is selected as follows. A Graph Neural Network (GNN) receives as input the set of jobs and a current state of at least the machine which is free. The GNN is trained to estimate a reward, which would be obtained when carry out a job such that the total completion time is minimized. More precisely, the GNN is trained to output a high reward for a small completion time of the set of jobs; Paragraph 0059, For learning the Q function, a simulator of the machines is applied that models the problem as a discrete event simulation. Preferably, a simulated factory, a.k.a. “digital twin”, is applied that reflects the dynamics of a real factory, i.e., how the state of the factory changes when a job is started on a machine and how additional tasks arrive over time. In an alternative embodiment, recorded data from the machines or from the factory can be used as training data for learning the Q function or the recoded data can be used to build the simulator. As already stated above, the DGN learning is preferably utilized to learn the Q function and train the GNN; Paragraph 0060, After the GNN is trained, it can be straight forward applied to schedule jobs on a plurality of machines. For example, if a decision point occurs, the above described inputs of the GNN are proceed of the current situation at the point of time when the decision point occurs. Depending on the output of the GNN, from the set of waiting jobs, the next job is selected with the highest Q value. This procedure can be applied each time, if decision points occur. Interestingly, this procedure is neither limited to static nor to dynamic settings; Examiner interprets the “job with the highest reward” as the “weight.” In this case, the GNN is used to learn which features achieve the highest reward (e.g., weight) for a graph matching problem. See paragraph 0037 of Applicant’s specification);
and … each [machine] which is assigned to a [job] according to the selected assignment to perform the [job] (Paragraph 0036, In general, the job scheduler shall be able to solve an online scheduling, a particular online combinatorial problem. Note that said job scheduler can be readily extended to other online combinatorial problems such as the travelling salesperson problem and vehicle routing problems, e.g. where the destinations are added online. The online combinatorial optimization problems, including online logistics problems (e.g., planning the route of a courier through a city, where additional points to pick up/drop off items are added while the courier is on his way; Examiner notes that the art taught by Taitler et al. can be applied to vehicle routing problems. Therefore, it would be obvious to try using a GNN to make vehicle routing decisions based a learned reward – as claimed).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein a neural network is used to predict a vehicle state value and a bipartite graph or self-learning decision engine is used to select a vehicle by solving a vehicle-passenger matching problem that maximizes an objective function of the invention of Tang et al. to further specify wherein a Graph Neural Network (GNN) is used to make a scheduling decisions based on dynamic real-time changes in the weights of the invention of Taitler et al. because doing so would allow the method to use a GNN to achieve better performance when decisions need to be made quickly, wherein the GNN may be used to solve vehicle routing problems (see Taitler et al., Paragraphs 0007 & 0036). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Claim 2 is rejected under 35 U.S.C. 103 as being unpatentable over Tang et al. (US 2022/0270488 A1), in view of Taitler et al. (US 2021/0312280 A1), in further view of Janakiraman et al. (US 2021/0287273 A1).
Regarding claim 2 (Original), which is dependent of claim 1, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 1. Although Tang et al. discloses a weight between the feature determined for the graph node of the transport task graph and the graph node of the vehicle graph (e.g., utility score representing a similarity between the transport task and the vehicle graph), Tang et al. does not specifically disclose wherein the weight between the feature determined for the graph node of the transport task graph and the graph node of the vehicle graph is given by the inner product of the feature determined for the graph node of the transport task graph and the graph node of the vehicle graph.
However, Janakiraman et al. discloses wherein each feature is a vector of a predetermined dimension and the weight between the feature determined for the graph node of the [user] task graph and the graph node of the [item] graph is given by the inner product of the feature determined for the graph node of the [user] task graph and the graph node of the [item] graph (Paragraph 0014, In general, embodiments of the invention are directed to recommending an item to a target user. For example, an item may be an object (e.g., a product or a service) to be purchased, or a merchant from whom an object is purchased. The recommendation may be based on scores calculated for paths through a bipartite graph that represents interactions between users and items. A bipartite graph is a graph whose nodes may be divided into two disjoint sets (e.g., user nodes and item nodes) such that each edge connects a node in one set to a node in the other set. Edge weights may be calculated for the edges in a path to de-emphasize bias corresponding to popular items and/or influential users (e.g., users who interact with many items). For example, an edge weight may be de-biased by multiplying by the inverse of the degree of the user node connected to the edge and/or the inverse of the degree of the item node connected to the edge. The degree of a node is the number of edges connected to the node, and thus may be a measure of the popularity of an item and/or the activity of a user. The path scores may be calculated efficiently using matrix multiplication techniques. The recommendation may further be based on similarities among user features and/or item features. An explanation may be generated for the recommendation based on interior nodes included in the paths between the target user and the recommended item. For example, the explanation may list common items corresponding to interior nodes that both the target user and other users interacted with. Continuing this example, the contribution of each common item to the recommendation may be quantified. A machine learning model may be trained to learn a nonlinear scoring function used to score the paths as well as learn how to use user and item features to influence the recommendation; Paragraph 0044, In one or more embodiments, the numerical values for the common items may be calculated using the dot product of the row corresponding to the target user in the user/item matrix A described in Step 208 above and the column corresponding to the recommended item in the matrix resulting from multiplying A.sup.T by A. For example, the terms added together in the dot product may correspond to the edge weights of the edges connected to the interior points (e.g., the common item nodes) in the paths between the target user node and the recommended item node).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein a neural network is used to predict a vehicle state value and a bipartite graph or self-learning decision engine is used to select a vehicle by solving a vehicle-passenger matching problem that maximizes an objective function of the invention of Tang et al. to further specify wherein the weight of the bipartite graph is calculated using a vector inner product of the invention of Janakiraman et al. because doing so would allow the method to provide recommendations based on similarities among user features and/or item features (see Janakiraman et al., Paragraphs 0014 & 0044). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Claim 5 is rejected under 35 U.S.C. 103 as being unpatentable over Tang et al. (US 2022/0270488 A1), in view of Taitler et al. (US 2021/0312280 A1), in further view of Di Lorenzo et al. (US 2021/0334722 A1).
Regarding claim 5 (Previously Amended), which is dependent of claim 3, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 3. Although Tang et al. discloses applying an assignment problem algorithm, Tang et al. does not specifically disclose wherein the assignment problem algorithm has a fixed number of iterations.
However, Di Lorenzo et al. discloses wherein the assignment problem algorithm has a fixed number of iterations (Paragraph 0067, In some implementations, the suggestion system 115 determines the final assignment of driver-passenger pairs based on performing a predetermined number of iterations of modifications (e.g., 2, 10, 100, and/or the like), based on an amount of time having elapsed (e.g., 30 seconds, 1 minute, 5 minutes, 1 hour, and/or the like), based on a cost associated with a modified solution satisfying (e.g., being less than) a threshold cost, and/or the like. The suggestion system 115 may determine the modified solution, generated in any of the iterations of modifications, associated with the lowest cost. The suggestion system 115 may determine the final assignment of driver-passenger pairs based on the driver-passenger pairs included in the modified solution associated with the lowest cost).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein scheduling/selecting the vehicle comprises applying an assignment problem algorithm to a bipartite graph or self-learning decision engine of the invention of Tang et al. to further specify wherein the assignment problem algorithm has a fixed number of iterations of the invention of Di Lorenzo et al. because doing so would allow the method to determine the final assignment of driver-passenger pairs based on performing a predetermined number of iterations (see Di Lorenzo et al., Paragraph 0067). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over Tang et al. (US 2022/0270488 A1), in view of Taitler et al. (US 2021/0312280 A1), in further view of Nurseptiani (Nurseptiani, A., Satria, Y. and Burhan, H., 2021, March. Application of agglomerative hierarchical clustering to optimize matching problems in ridesharing for maximize total distance savings. In Journal of Physics: Conference Series (Vol. 1821, No. 1, p. 012016). IOP Publishing).
Regarding claim 8 (Previously Amended), which is dependent of claim 7, the combination of Tang et al. and Taitler et al. discloses all the limitations in claim 7. Although Tang et al. discloses applying an assignment problem algorithm, Tang et al. does not specifically disclose clustering the vehicle graph and the transport task graph prior the matching process.
However, Nurseptiani discloses wherein the vehicle graph comprises edges between graph nodes depending on a similarity of the input features values of the graph nodes and wherein the transport task graph comprises edges between graph nodes depending on the similarity of the input feature values of the graph nodes (Page 2, Introduction, An alternative solution in dealing with the high level of ridesharing demand, where the number of participants is very large and the short of optimization time, is to cluster the origin and destination points of each participant. According to Apeh and Gabrys (2006)[6], clustering is an alternative technique that promises to reduce the burden of recording all comparisons in the matching process. For this reason, this paper will discuss clustering using the agglomerative hierarchical clustering (AHC) method with the aim of classifying participants from the ridesharing system. AHC is a bottom-up clustering technique, where this algorithm combines n objects into a single cluster by paying attention to the proximity between objects. Furthermore, the single cluster is partitioned into several clusters as needed. Different from K-means clustering, in AHC the number of clusters to be formed does not affect the cluster formation process; Page 4, 3.1 Pre-processing, At the pre-processing stage, we need to select the possible match of driver-rider by using AHC. Let (𝑑, 𝑟) as pair of driver 𝑑 and rider 𝑟. (𝑑, 𝑟) is said to be possible match if it satisfies a criterion, which is their origin are belong in the same cluster and their destination are belong in the same cluster. The goal of using this method is to reduce computation of (𝑑, 𝑟) combinations that will be optimized. Also, the criteria of possible match assures the proximity of both driver’s and rider’s origin and destination. The algorithm of determining the set of possible match will be shown in figure 2).
It would have been obvious to one ordinary skill in the art before the effective filing date to modify the method for scheduling and controlling vehicles to perform transport tasks, wherein scheduling/selecting the vehicle comprises applying an assignment problem algorithm to a bipartite graph or self-learning decision engine of the invention of Tang et al. to further specify clustering the vehicle graph and the transport task graph prior the matching process of the invention of Nurseptiani because doing so would allow the method to assure the proximity of both driver’s and rider’s origin and destination by using clustering techniques (see Nurseptiani, Page 4, 3.1 Pre-processing). Further, the claimed invention is merely a combination of old elements, and in combination each element would have performed the same function as it did separately, and one of ordinary skill in the art would have recognized that the results of the combination were predictable.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
Ho et al. (US-20190120640-A1) – discloses clustering the first plurality of passengers according to their assigned candidate pick-up locations and drop-off locations (see at least Paragraph 0049).
Li (Li, Z., Shen, X., Jiao, Y., Pan, X., Zou, P., Meng, X., Yao, C. and Bu, J., 2020, April. Hierarchical bipartite graph neural networks: Towards large-scale e-commerce applications. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) (pp. 1677-1688). IEEE) – discloses graph neural networks (GNNs) have gained a high reputation of obtaining state-of-the-art results through effectively learned node embeddings of non-linear interactions in tasks such as node classification and link prediction [8]–[17] (see at least Page 1677, I. Introduction).
Chen (CN 111754095 A) - discloses scheduling vehicle based on artificial intelligence comprises obtaining riding information of each passenger, obtaining vehicle information of each vehicle, processing the riding information and the vehicle information based on artificial intelligence to obtain receiving information matched with each of the passengers, and where the processing the riding information and the vehicle information based on artificial intelligence to obtain the receiving information matched with each of the passengers comprises using genetic algorithm to process the riding information and the vehicle information to obtain the receiving information matched with each of the passenger (see at least Abstract).
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MARJORIE PUJOLS-CRUZ whose telephone number is (571)272-4668. The examiner can normally be reached Mon-Thru 7:30 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, Patricia H Munson can be reached at (571)270-5396. 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.
/MARJORIE PUJOLS-CRUZ/Examiner, Art Unit 3624