EP0362874A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Cellular network assignment processor using randomly triggered adaptive cell thresholds
Assignee: Raytheon Co
•
Filing: 1989-10-06
•
Granted: —
•
Expires: 2009-10-06
Abstract
Abstract An information processor (10) for solving assignment problems using a matrix of individual processing cells. The location of each cell within the processor (10) corresponds to the position of the costs in the associated constraint space of the assignment problem, and each cell contains a cost register (12) that is stored with an associated cost value. A noise generator (14) associated with each cell is used to trigger a variable threshold (16) in each cell so that cost values may be transmitted by each cell only when the signal from the noise generator (14) exceeds the threshold. When triggered, the cell disables all other cells along each dimensional axes stemming from that cell from contributing to the current tentative solution. This disabling is removed at the beginning of the next cycle. Successive solutions to the assignment problem are evaluated by adding the cost values in an accumulator (24) for cells that represent each particular solution. The sums are then compared to a criteria by a comparator (28). Thresholds are then lowered by a threshold adjustment circuit (30) for good solutions and raised for bad solutions. This leads the activity of the processor (10) toward a final stable state which corresponds to a near optimal solution of the assignment problem.
Inventors
- 👤 Patrick F. Dr. Castelaz
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-26 16:40
CPC Classifications
G; G06; G06N; G06N3/00; G06N3/02; G06N3/06; G06N3/063; G06Q; G06Q10/00; G06Q10/04; G06N3/04; G06Q10/06; G06Q10/063; G06Q10/0631; G06Q10/06315; G06Q10/06316; G06Q10/0637; G06Q10/06375
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
186 words
information processor (10) for solving assignment problems, said information processor (10) having a multidimensional matrix of processing cells, each capable of receiving, storing and transmitting cost values, characterized by: - said cells being located in a position that represents a particular set of input parameters; - means (14) for generating a randomly varying signal associated with each cell; - variable threshold means (16) for permitting said cost value to be transmitted by said cells only when said threshold level is exceeded by said randomly varying signal; - accumulator means (30) for summing said cost values in a plurality of said cells, after said cost value has been transmitted by said cells; - comparator means (34) responsive to said accumulator means (30), for comparing the sum of said cost values with a predetermined value to classify said sum as being a good or a bad solution; and means (36) for adjusting said threshold, responsive to said comparator means (34), wherein said thresholds are lowered for those cells which contribute to solutions classified as good and thresholds are raised for cells which contribute to solutions classified as bad.
Claim 2
Dependent Claim
186 words
information processor (10) for solving assignment problems, said information processor (10) having a multidimensional matrix of processing cells, each capable of receiving, storing and transmitting cost values, characterized by: - said cells being located in a position that represents a particular set of input parameters; - means (14) for generating a randomly varying signal associated with each cell; - variable threshold means (16) for permitting said cost value to be transmitted by said cells only when said threshold level is exceeded by said randomly varying signal; - accumulator means (30) for summing said cost values in a plurality of said cells, after said cost value has been transmitted by said cells; - comparator means (34) responsive to said accumulator means (30), for comparing the sum of said cost values with a predetermined value to classify said sum as being a good or a bad solution; and means (36) for adjusting said threshold, responsive to said comparator means (34), wherein said thresholds are lowered for those cells which contribute to solutions classified as good and thresholds are raised for cells which contribute to solutions classified as bad.
Claim 3
Dependent Claim
35 words
The information processor of claim 1, characterized by means for determining when the number of cost values transmitted exceeds a predetermined number, wherein said accumulator means (30) sums said predetermined number of said cost values.
Claim 4
Dependent Claim
21 words
The information processor of claim 1 or 2, characterized in that said variable threshold means (16) is located within each cell.
Claim 5
Dependent Claim
35 words
The information processor of any of claims 1 through 3, characterized by means for disabling all other cells along the same dimensional axes as a given cell when said threshold is exceeded for said cell.
Claim 6
Dependent Claim
27 words
The information processor of any of claims 1 through 4, characterized in that said means (14) for generating a randomly varying signal is located within each cell.
Claim 7
Dependent Claim
36 words
The information processor of any of claims 1 through 5, characterized by means for storing said solutions and means for comparing a current solution with a previous stored solution for determining and storing the best solution-to-date.
Claim 8
Dependent Claim
30 words
The information processor of any of claims 1 through 6, characterized by a means (38) for interrupting said information processor (10) to transmit the best solution-to-date at any given time.
Claim 9
Dependent Claim
19 words
The information processor of any of claims 1 through 7, characterized in that said cost values comprise digital data.
Claim 10
Dependent Claim
26 words
The information processor of any of claims 1 through 8, characterized in that said predetermined number of cost values represent particular solutions to an assignment problem.
Claim 11
Dependent Claim
20 words
The information processor of any of claims 1 through 9, characterized in that said predetermined value is said best solution-to-date.
Claim 12
Dependent Claim
58 words
The information processor of any of claims 1 through 10, characterized in that said assignment problem comprises deghosting from angle-only sensor data; said particular input parameters being particular angles for particular sensors (20); said predetermined number being the number of targets (22); and said cost values being proportional to the error associated with intersects from said sensors (20).
Claim 13
Independent Claim
140 words
A method for solving an assignment problem, preferably by using a processor according to any of claims 1 through 11, characterized by: - assigning cells in a multi-dimensional matrix to locations wherein each cell's location represents a particular input parameter; - storing cost values in each cell; - generating a randomly varying signal associated with each said cell; - transmitting said stored cost values from each cell only when said randomly varying signal exceeds a predetermined threshold; summing said transmitted cost values from a plurality of said cells; - comparing said sum with a predetermined value to classify said sum as being a good or a bad solution; and - lowering said thresholds for those cells contributing to good solutions and raising said thresholds for those cells contributing to bad solutions each time a set of cost values is summed.
Claim 14
Dependent Claim
36 words
The method of claim 12, characterized by the step of determining when the number of costs values transmitted exceeds a predetermined number, wherein said step of summing only occurs after said predetermined number has been exceeded.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.