US-20260127662-A1 - ARTIFICIAL INTELLIGENCE (AI) ENABLED BID ADJUDICATION SYSTEM USING GRAPH NEURAL NETWORKS

US20260127662A1US 20260127662 A1US20260127662 A1US 20260127662A1US-20260127662-A1

Abstract

The artificial intelligence enabled bid adjudication system uses graph neural networks (GNNs) to infer/approximate courses of action (COAs). The COA winner decision process (WDP) is modeled as a bi-partite graph. A GNN model is trained using previously generated data (e.g., achieved from a previous brute force calculation). The trained GNN model is then used to solve the COA WDP. From the solution, the top n COAs and associate WDP solution scores are calculated. The top n inferred solution scores are then ranked to determine the solution of the COA WDP. The AI enabled bid adjudication system may be utilized with any battle management system (BMS) with a mathematical or heuristic COA scoring decision process.

Inventors

Ivan D CACERES
Ariane Jamie S. KRUMEL
Daniel Jackson BURSCH
Gregory DEVOS

Assignees

NORTHROP GRUMMAN SYSTEMS CORPORATION

Dates

Publication Date: 20260507
Application Date: 20241104

Claims (9)

1 . A method of performing bid adjudication using graph neural networks (GNNs), the method comprising: receiving a plurality of bids and associated parameters related to a winner determination problem in real time; converting the received plurality of bids to a plurality bidder nodes and associated parameters to a plurality of associated bid node features; estimating a plurality of courses of action (COAs) by inputting the plurality of bidder nodes and the plurality of associated bid node features using a GNN, wherein the plurality of COAs are outputs of the GNN; ranking a predetermined number of the plurality of COAs; and selecting at least one COA from the predetermined number of COAs for execution; and executing the at least one COA.
2 . The method according to claim 1 , wherein the GNN is trained on less inputs than the received plurality of bids.
3 . The method according to claim 1 , wherein the plurality of bidder nodes are arranged in a bipartite graph during the estimating.
4 . The method according to claim 3 , wherein edges of the bipartite graph are assigned the plurality of associated bid node features.
5 . The method according to claim 1 , wherein a plurality of the predetermined number of COAs are executed in addition to the at least one COA.
6 . The method according to claim 1 , wherein the GNN is trained on training data generated by an exact combinatorial solution.
7 . The method according to claim 6 , wherein the exact combinatorial solution utilizes a brute force method.
8 . The method according to claim 1 , further comprising: comparing an accuracy of the plurality of COAs to a predetermined threshold at regular intervals; and retraining the GNN if the accuracy falls below the predetermined threshold.
9 . The method according to claim 1 , wherein a timing to determine the plurality of COAs by the GNN is approximately linear with a number of bidder nodes.

Description

FIELD OF THE INVENTION The present invention relates to performing bid adjudication using graph neural networks (GNN) to estimate the best solution to the auction using course of action (COA) calculations. BACKGROUND Combinatorial auctions (CA) are efficient for determining resource allocation in different fields, such as in multi-domain mission managers or multi-domain battle mangers. First, single and two-bid combinations are evaluated before additional combinatorial analysis is performed using brute force methods or score improvement heuristic methods to calculate COA, where the COAs are the equivalents of bids in a CA. In some systems, an engagement adjudication engine (EAE) is utilized to determine the best COAs for given scenarios. Typically, when low number of factors are involved, brute forcing combinatoric calculations is feasible, but this practice quickly becomes intractable as the number of combinatorics increases, requiring other heuristic methods. The EAE evaluates all submitted bids as two-bid combinations and continues with higher-order combinations as long as score improvement continues (e.g., EAE checks for at least 0.01% score improvement or terminates combination analysis). Unfortunately, this combinatorial analysis process can be incredibly computational expensive as characterization experiments have demonstrated increasing number of potential COAs/bids evaluated by the EAE significantly increases time required for analysis. While these methods are suitable for CAs with small numbers of bids (e.g., less than 50 bids), increasing the number of bids significantly increases the time required to determine the ideal solution to the winner determination problem. The problem of allocating items among the bidders to maximize the auctioneers' revenue is referred to as the winner determination problem (WDP), which is NP-complete to solve and inapproximable. For example, FIG. 1A depicts a graph showing the time required to reach a solution based on the number of bids using a brute force method for 50 bids. When the number of bids is ≤20, the time required is generally linear (but always exponential). However, as the number of bids increases, the time to reach a solution increases exponentially. This is especially true for larger number of bids. For example, while 50 bids takes ˜800 ms to compute a solution, 100 bids takes ˜9000 ms (FIG. 1B) to compute and 250 bids takes ˜225,000 ms (FIG. 1C) to compute. These computation times are generally not suitable for real world scenarios where decisions must be made much faster, especially for greater number of bids. FIG. 2 depicts the time required to reach a solution based on a score improvement heuristic method. As depicted, the time to compute a solution is decreased with respect to the brute force method, but the time to research the solution exponentially increases as the number of bids are increased (e.g., ≥40 bids). The time to determine the optimal or potential course of actions for many situations can be severely limited, such as during active engagement or deployment. Therefore, a need exists for alternative methods of calculating or approximating COAs for CAs which are more time efficient and scale-well with the number of bids (e.g., linearly or approximately linearly). The alternative methods should also be able to be trainable on small data sets since generating training data can be time-consuming, especially when there are large number or bids or items. SUMMARY The AI enabled bid adjudication system of the present invention addresses these deficiencies by using graph neural networks (GNN) to infer/approximate COAs. The COA winner decision process (WDP) is modeled as a bi-partite graph. A GNN model is trained using previously generated data (e.g., achieved from a previous brute force calculation). The trained GNN model is then used to solve the COA WDP. From the solution, the top n COAs and associate WDP solution scores are calculated. The top n inferred solution scores are then ranked to determine the solution of the COA WDP. The AI enabled bid adjudication system may be utilized with any battle management system (BMS) with a mathematical or heuristic COA scoring decision process. FIGS. 3 and 4 depict the time to solution (in ms) vs. the number of bids when the AI bid adjudication system of the present invention is utilized to solve the same CA from FIGS. 1 and 2. Specifically, the number of combined bids for the solution is set to 5 bids in FIG. 3 and 25 bids in FIG. 4. As shown, a 100× performance increase is quickly realized as the number of bids is increased. Further, the time scales linearly with the number of bids as opposed to exponentially in the other described methods. This means that much smaller training sets can be used when training the GNN model. A GNN model approach enables analysis of complex scenarios with many potential COAs that would be intractable by standard methods. An additional benefit is that GNN models can be train