Patent US1570503A successfully refreshed from Google Patents.
Patent US5001631A successfully refreshed from Google Patents.
US5001631A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cellular network assignment processor using randomly triggered adaptive cell thresholds
Assignee: Raytheon Co
•
Filing: 1988-10-07
•
Granted: 1991-03-19
•
Expires: 2008-10-07
Abstract
Abstract An information processor (10) for solving assignment problems uses 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 the 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 (30) for cells that represent each particular solution. The sums are then compared to a criteria by a comparator (34). Thresholds are then lowered by a threshold adjustment circuit (26) 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. Castelaz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:57
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: 31
Claim 1
Independent Claim
180 words
In an information processor for solving assignment problems, said information procesor having a multidimensional matrix of processing cells, each capable of receiving, storing and transmitting cost values, the improvement comprising; said cells being located in a position that represents a particular set of input parameters; means for generating a randomly varying signal associated with each cell; variable threshold means for generating threshold levels and for permitting said cost value to be transmitted by said cells only when said threshold level is exceded by said randomly varying signal; accumulator means for summing said cost values in a plurality of said cells, after said cost value has been transmitted by said cells; comparator means, responsive to said accumulator means, 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 for adjusting said thresholds, responsive to said comparator means, 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 clasified as bad.
Claim 2
Dependent Claim
180 words
In an information processor for solving assignment problems, said information procesor having a multidimensional matrix of processing cells, each capable of receiving, storing and transmitting cost values, the improvement comprising; said cells being located in a position that represents a particular set of input parameters; means for generating a randomly varying signal associated with each cell; variable threshold means for generating threshold levels and for permitting said cost value to be transmitted by said cells only when said threshold level is exceded by said randomly varying signal; accumulator means for summing said cost values in a plurality of said cells, after said cost value has been transmitted by said cells; comparator means, responsive to said accumulator means, 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 for adjusting said thresholds, responsive to said comparator means, 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 clasified as bad.
Claim 3
Dependent Claim
34 words
The information processor of claim 1 further comprising means for determing when the number of cost values transmitted exceeds a predetermined number, wherein said accumulator means sums said predetermined number of said cost values.
Claim 4
Dependent Claim
20 words
The information processor of claim 1 wherein said means for generating a randomly varying signal is located within each cell.
Claim 5
Dependent Claim
49 words
The informatiaon processor of claim 2 wherein said assignment problem comprises deghosting from angle-only sensor data; said particular input parameters are particular angles for particular sensors; said predetermined number is the number of targets; and said cost values are proportional to the error associated with intersects from said sensors.
Claim 6
Dependent Claim
16 words
The information processor of claim 1 wherein said variable threshold means is located within each cell.
Claim 7
Dependent Claim
31 words
The information processor of claim 1 further comprising means for disabling all other cells along the same dimensional axes as a given cell when said theshold is exceeded for said cell.
Claim 8
Dependent Claim
20 words
The information processor of claim 2 wherein said predetermined number of cost values represent particular solutions to an assignment problem.
Claim 9
Dependent Claim
32 words
The information processor of claim 1 further comprising means for storing said solutions and means for comparing a current solution with a previous stored solution for determining said storing the best solution-to-date.
Claim 10
Dependent Claim
24 words
The information processor of claim 8 further comprising a means for interrupting said information processor to transmit the best solution-to-date at any given time.
Claim 11
Dependent Claim
14 words
The information processor of claim 6 wherein said predetermined value is said best solution-to-date.
Claim 12
Dependent Claim
13 words
The information processor of claim 1 wherein said cost values comprise digital data.
Claim 13
Dependent Claim
176 words
An information processor solving assignment problems, said information processor having a multidimensional matrix of processing cells, each capable of receiving, storing and transmitting cost values, comprising: said cells being located in a position that represents a particular set of input parameters; means for generating a randomly varying signal associated with each cell; variable threshold means for generating threshold levels and 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 for summing said cost values in a plurality of said cells, after said cost value has been transmitted by said cells; comparator means, responsive to said accumulator means, 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 for adjusting said thresholds, responsive to said comparator means, wherein said thresholds are lowered for those cells which contribute to solutions classified as good and thresholds are raised for cells which contribiute to solutions classified as bad.
Claim 14
Dependent Claim
176 words
An information processor solving assignment problems, said information processor having a multidimensional matrix of processing cells, each capable of receiving, storing and transmitting cost values, comprising: said cells being located in a position that represents a particular set of input parameters; means for generating a randomly varying signal associated with each cell; variable threshold means for generating threshold levels and 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 for summing said cost values in a plurality of said cells, after said cost value has been transmitted by said cells; comparator means, responsive to said accumulator means, 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 for adjusting said thresholds, responsive to said comparator means, wherein said thresholds are lowered for those cells which contribute to solutions classified as good and thresholds are raised for cells which contribiute to solutions classified as bad.
Claim 15
Dependent Claim
34 words
The information processor of claim 12 further comprising means for determining when the number of cost values transmitted exceeds a predetermined number, wherein said accumulator means sums said predetermined number of said cost values.
Claim 16
Dependent Claim
20 words
The information processor of claim 13 wherein said predetermined number of cost values represent particular solutions to an assignment problem.
Claim 17
Dependent Claim
49 words
The information processor of claim 13 wherein said assignment problem comprises deghosting from angle-only sensor data; said particular input parameters are particular angles for particular sensors; and predetermined number is the number of targets; and said cost values are proportional to the error associated with intersects from said sensors.
Claim 18
Dependent Claim
16 words
The information processor of claim 12 wherein said variable threshold means is located within each cell.
Claim 19
Dependent Claim
20 words
The information processor of claim 12 wherein said means for generating a randomly varying signal is located within each cell.
Claim 20
Dependent Claim
31 words
The information processor of claim 12 further comprising means for disabling all other cells along the same dimensional axes as a given cell when said theshold is exceeded for said cell.
Claim 21
Dependent Claim
32 words
The information processor of claim 12 further comprising 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 22
Dependent Claim
24 words
The information processor of claim 19 further comprising a means for interrutping said information processor to transmit the best solution-to-date at any given time.
Claim 23
Dependent Claim
14 words
The information processor of claim 19 wherein said predetermined value is said best solution-to-date.
Claim 24
Dependent Claim
13 words
The information processor of claim 12 wherein said cost values comprise digital data.
Claim 25
Independent Claim
122 words
A method for solving an assignment problem, said method comprising: assigning cells in a multidimensional 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 26
Independent Claim
122 words
A method for solving an assignment problem, said method comprising: assigning cells in a multidimensional 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 27
Dependent Claim
31 words
The method of claim 23 further comprising the step of disabling all other cells along the same dimensional axes as a given cell when said threshold is exceeded for said cell.
Claim 28
Dependent Claim
36 words
The method of claim 23 further comprising the step of determining when the number of costs values transmitted exceeds a predetermined number, wherein said step of summing only occurs after said predetremined number has been exceeded.
Claim 29
Dependent Claim
48 words
The method of claim 25 wherein said assignment problem comprises deghosting from angle-only sensor data; said particular input parameters are particular angles for particular sensors; said predetermined number is the number of targets; and said cost values are proportional to the error associated with intersects from said sensors.
Claim 30
Dependent Claim
43 words
The method of claim 23 further comprising the steps of: storing a previous good solution; comparing a current good solution with said stored good solution; and storing only the solution that is the better of the two, whereby the best solution-to-date is stored.
Claim 31
Dependent Claim
15 words
The method of claim 27 wherein said best solution-to-date is used for said predetermined value.
References Cited (Backward Citations)
US3443078A
Cited
US3562502A
Cited
US3950733A
Cited
US4025919A
Cited
US4254474A
Cited
US4326259A
Cited
US4450530A
Cited
US4591980A
Cited
US4802103A
Cited
US4858147A
Cited
US4914604A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-03-18 | 1994-09-17 | 1995-03-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-03-18 | 1998-09-17 | 1999-03-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-03-18 | 2002-09-17 | 2003-03-19 | $7700.00 | Window Closed / Lapsed |