Cellular network assignment processor using minimum/maximum convergence technique

• US 5,093,781 A
• Filed: 10/07/1988
• Issued: 03/03/1992
• Est. Priority Date: 10/07/1988
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Castelaz, Patrick F.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): FAGAN, MATTHEW
• Application Number:
  US07/255,692
• Time in Patent Office: 1,243 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/513, 364/807
• US Class Current: 712/16
• CPC Class Codes: G06F 15/8015 One dimensional arrays, e.g. rings, linear arrays, buses

Abstract

A cellular network assignment processor (10) for solving optimization problems utilizing a neural network architecture having a matrix of simple processing cells (12) that are highly interconnected in a regular structure. The cells (12) accept as input, costs in an assignment problem. The position of each cell (12) corresponds to the position of the cost in the associated constraint space of the assignment problem. Each cell (12) is capable of receiving, storing and transmitting cost values and is also capable of determining if it is the maximum or the minimum of cells (12) to which it'"'"'s connected. Operating on one row of cells (12) at a time the processor (10) determines if a conflict exists between selected connected cells (12) until a cell (12) with no conflict is found in each row. The end result is a chosen cell (12), in each row, the chosen cells (12) together representing a valid solution to the assignment problem.

Claims

1. A method for processing information comprising:

assigning an address to each of a plurality of processing cells, said address including coordinates representing a particular set of input parameters for a multidimensional assignment problem, said input parameters originating from a plurality of sources wherein parameters from each of said sources correspond to one of said dimensions of said assignment problem, and wherein each of said processing cells receives, stores, and transmits information values;

storing one of said information values in each processing cell;

connecting each individual processing cell to every other processing cell whose assigned address has a conflict with the assigned address of said individual processing cell, said conflict defined as occurring when the assigned address of said individual processing cell has at least one common input parameter with the assigned address of another processing cell;

comparing the information values of processing cells in each of a plurality of groups of processing cells which are connected;

setting a flag in those processing cells which meet a preselected criteria of the compared information values for each group;

determining if a conflict exists between each flagged processing cell and other flagged processing cells;

unsetting the flag in those flagged processing cells which are in conflict with other flagged processing cells as determined by said determining step; and

performing the steps of comparing, setting flags, determining, and unsetting flags on one group of processing cells at a time until a flagged processing cell having no conflicts with other flagged processing cells is found for each group, whereby said flagged processing cells having no conflicts with other flagged processing cells together represent an optimal solution to said assignment problem.

2. The method of claim 1 wherein said step of setting a flag in those processing cells which meet a preselected criteria comprises setting a flag in those processing cells which have the maximum of the compared information values for each group.

3. The method of claim 1 wherein said step of setting a flag in those processing cells which meet a preselected criteria comprises setting a flag in those processing cells which have the minimum of the compared information values for each group.

4. The method of claim 1 wherein said step of comparing is performed by each processing cell.

5. The method of claim 4 wherein said sources are sensors and said assignment problem involves the deghosting of angle-only target data from multiple targets sensed by said sensors;

each of said input parameters represent angles for one of said sensors;

the total number of input parameters from one of said sensors equals the number of targets in said assignment problem; and

said information values are cost values proportional to an area formed by the intersection of paths from said sensors to said targets.

6. The method of claim 1 wherein the step of setting flags further comprises the step of disabling selected ones of said processing cells for a period of time so that said flags in said selected ones of said processing cells cannot be set while other solutions to said assignment problem are processed.

7. The method of claim 6 wherein said period of time is set randomly.

8. In an information processor having a plurality of processing cells, each of said cells for receiving, storing, and transmitting an information value, the improvement comprising:

means for assigning an address to each processing cell, said address including coordinates representing a particular set of input parameters for a multidimensional assignment problem, said input parameters originating from a plurality of sources wherein parameters from each of said sources correspond to one of said dimensions of said assignment problem;

means for connecting each individual processing cell to every other processing cell whose assigned address has a conflict with the assigned address of said individual processing cell, said conflict defined as occurring when the assigned address of said individual processing cell has at least one common input parameter with the assigned address of another processing cell;

means for comparing the information values of processing cells in each of a plurality of groups of processing cells which are connected;

means, responsive to said comparing means, for setting a flag in those processing cells which meet a preselected criteria of the compared information values for each group;

means for determining if a conflict exists between each flagged processing cell and other flagged processing cells;

means, responsive to said determining means, for unsetting the flag in those flagged processing cells which are in conflict with other flagged processing cells; and

means for controlling said comparing means, said flag setting means, said determining means, and said flag unsetting means, so that said comparing means, said flag setting means, said determining means, and said flag unsetting means all operate on one group of processing cells at a time, until a flagged processing cell having no conflicts with other flagged processing cells is found for each group, whereby said flagged processing cells having no conflicts with other flagged processing cells together represent an optimal solution to said assignment problem.

9. The processor of claim 8 wherein said means responsive to said comparing means for setting a flag in those processing cells includes means for setting a flag in those processing cells which have the maximum of the compared information values for each group.

10. The processor of claim 8 wherein said means responsive to said comparing means for setting a flag in those processing cells includes means for setting a flag in those processing cells which have the minimum of the compared information values for each group.

11. The processor of claim 8 wherein said comparing means comprises means within each processing cell for comparing the information values within each group of connected processing cells.

12. The processor of claim 8 wherein said sources are sensors and said assignment problem involves the deghosting of angle-only target data from multiple targets sensed by said sensors;

each of said input parameters represents angles for one of said sensors;

the total number of said input parameters from one of said sensors equals the number of targets in said assignment problem; and

said information values are cost values proportional to an area formed by the intersection of paths from said sensors to said targets.

13. The processor of claim 8 further comprising means for disabling said flag setting means for a predetermined period of time so that said flags in selected ones of said processing cells cannot be set while other solutions to said assignment problem are processed.

14. The processor of claim 13 wherein said period of time is set randomly.