Digital parallel processor array for optimum path planning

• US 5,548,773 A
• Filed: 03/30/1993
• Issued: 08/20/1996
• Est. Priority Date: 03/30/1993
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Fossum, Eric R., Nixon, Robert H., Kemeny, Sabrina E.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): DARBE, VALERIE A
• Application Number:
  US08/042,486
• Time in Patent Office: 1,239 Days
• Field of Search: 395/800, 364/DIG. 1, 364/DIG. 2, 364/443, 364/444, 364/467
• US Class Current: 712/11
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06Q 30/0283 Price estimation or determination

Abstract

The invention computes the optimum path across a terrain or topology represented by an array of parallel processor cells interconnected between neighboring cells by links extending along different directions to the neighboring cells. Such an array is preferably implemented as a high-speed integrated circuit. The computation of the optimum path is accomplished by, in each cell, receiving stimulus signals from neighboring cells along corresponding directions, determining and storing the identity of a direction along which the first stimulus signal is received, broadcasting a subsequent stimulus signal to the neighboring cells after a predetermined delay time, whereby stimulus signals propagate throughout the array from a starting one of the cells. After propagation of the stimulus signals throughout the array, a master processor traces back from a selected destination cell to the starting cell along an optimum path of the cells in accordance with the identity of the directions stored in each of the cells.

Claims

1. A path planning parallel processor, comprising:

(A) a two dimensional array of processor cells, each of said processor cells comprising;

(1) plural direction input means for receiving stimulus signals from neighboring processor cells along corresponding directions in said array,

(2) direction memory means for determining and storing the identity of a direction along which a stimulus signal is first received,

(3) means for broadcasting a subsequent stimulus signal to said neighboring processor cells after a locally stored predetermined delay time, wherein said predetermined delay time corresponds to a topology, whereby stimulus signals propagate throughout said array from a starting one of said processor cells;

(B) link means for carrying stimulus signals between neighboring processor cells; and

(C) means for tracing back from a user selected destination one of said processor cells to said starting cell along an optimum path of said processor cells in accordance with said identity of a direction stored in each of said processor cells.

2. The parallel processor of claim 1 further comprising:

hardware means external to said processor cells operable prior to propagation of said stimulus signals throughout said array for programming different predetermined delay times in different ones of said processor cells in accordance with said topology across which said optimum path is to be determined.

3. The parallel processor of claim 2 wherein each of said processor cells further comprises:

hardware means for causing said starting cell to preemptively broadcast a stimulus signal to its neighboring processor cells.

4. The parallel processor of claim 3 wherein:

said means for broadcasting comprises programmable cost memory means for storing said predetermined delay time, and

said means for programming comprises means for writing said predetermined delay time to said programmable cost memory.

5. The parallel processor of claim 4 wherein:

each of said processor cells further comprises infinite cost memory means for storing cost values and for preventing a stimulus signal from being transmitted from said cell along at least a selected one of said directions, whereby to impose an infinite time delay for said selected one direction corresponding to an impassable barrier of said topology.

6. The parallel processor of claim 5 wherein said means for broadcasting and said programmable cost memory means comprise:

a first ripple down counter having an output connected to said link means, and

a count enable input connected to said direction memory means,

wherein said first ripple down counter comprises means for counting down from a preset count stored therein upon receipt by said direction memory means of a stimulus signal,

and wherein said means for programming comprises means for setting said count stored in said first ripple down counter to a count value corresponding to the predetermined delay time of the cell.

7. The parallel processor of claim 6 wherein said infinite cost memory means comprise:

programmable means for interrupting connection between said first ripple down counter output and link means of selected ones of said directions corresponding to said impassable barrier.

8. The parallel processor of claim 6 wherein said means for programming further comprises:

means for programming said infinite cost memory with the identity of the directions along which said programmable means is to interrupt connection between said first ripple down counter and said link means.

9. The parallel processor of claim 5 wherein said infinite cost memory means further comprises:

means for blocking receipt of any stimulus signals along selected directions.

10. The parallel processor of claim 5 wherein said means for programming and said means for tracing back comprise:

a master processor programmed to program said cost memory means and said infinite cost memory means prior to a propagation of stimulation signals throughout said array and to initiate broadcasting of a stimulus signal from said starting cell and to trace back said optimum path; and

row and column decoder means controlled by said master processor and connected to respective processor cells in respective row and columns of said array for accessing selected ones of said processor cells for said master processor.

11. The parallel processor of claim 10 wherein each of said processor cells further comprises:

cell decoder means connected to said row and column decoder means for sequentially enabling programming of said cost memory means and said infinite cost memory means and reading of said direction memory means upon receipt by said cell decoder of enabling signals from said row and column decoder means.

12. The parallel processor of claim 5 wherein said neighboring processor cells comprise:

nearest neighbor processor cells disposed in orthogonal directions with respect to said cell, and

next-nearest neighbor processor cells disposed in diagonal directions with respect to said cell,

wherein said cost memory means comprises an orthogonal cost memory and a diagonal cost memory,

and wherein said means for programming comprises means for programming one time delay in said orthogonal cost memory and an other time delay into said diagonal cost memory.

13. The parallel processor of claim 12 wherein each off said diagonal and orthogonal cost memories comprises:

a ripple down counter, and

means for applying separate clock signals to each ripple down counter.

14. The parallel processor of claim 4 wherein each of said processor cells further comprise:

infinite cost memory means for storing cost values and for blocking receipt of any stimulus signals along selected directions.

15. The parallel processor of claim 2 wherein said hardware means for programming different predetermined delay times in different ones of said processor cells is located within each of said processor cells.

16. The parallel processor of claim 1 wherein:

said array is a network of orthogonal rows and columns of said processor cells, and

the neighboring processor cells of an individual one of said processor cells comprise processor cells which are adjacent said one processor cell along one of;

(a) orthogonal directions only,

(b) orthogonal and diagonal directions.

17. The parallel processor of claim 16 wherein:

said means for broadcasting broadcasts a stimulus signal along said orthogonal directions after said predetermined time delay and broadcasts a stimulus signal along said diagonal directions of processor cells which are adjacent said one processor cells along orthogonal and diagonal directions after an other predetermined time delay different from said predetermined time delay.

18. The parallel processor of claim 17 wherein:

said other predetermined time delay exceeds said predetermined time delay by a factor equal to a square root of two.

19. The parallel processor of claim 16 wherein said network is a three-dimensional network, wherein the third dimension corresponds to altitudes of air traveled paths.

20. The parallel processor claim 1 wherein said direction memory means comprises:

plural resettable latches connected to receive stimulus signals along respective ones of said directions;

means responsive to the setting of any one of said resettable latches by a first-received stimulus signal for blocking the receipt of any further stimulus signals along at least all others of said directions.

21. The parallel processor of claim 1 wherein:

said broadcasting means comprises means for imposing different time delays for broadcasting stimulus signals in different ones of said directions.

22. The parallel processor of claim 1 further comprising:

software means external to said processor cells operable prior to propagation of said stimulus signals throughout said array for programming different predetermined delay times in different ones of said processor cells in accordance with said topology across which said optimum path is to be determined.

23. The parallel processor of claim 22 wherein said software means for programming different predetermined delay times in different ones of said processor cells is located within each of said processor cells.

24. A method of path planning in an array of parallel processor cells interconnected between neighboring processor cells by link means, comprising:

(A) in each cell;

(1) receiving stimulus signals from neighboring processor cells along corresponding directions in said array,

(2) determining and storing the identity of a direction along which a stimulus signal is first received,

(3) broadcasting a subsequent stimulus signal to said neighboring processor cells after a predetermined delay time, whereby stimulus signals propagate throughout said array from a starting one of said processor cells;

(B) after propagation of said stimulus signals throughout said array, tracing back from a selected destination one of said processor cells to said starting cell along an optimum path of said processor cells in accordance with said identity of a direction stored in each of said processor cells.

25. The method of claim 24 further comprising:

prior to propagation of said stimulus signals throughout said array, programming different predetermined delay times in different ones of said processor cells in accordance with a topology across which said optimum path is to be determined.

26. The method of claim 25 further comprising:

causing said selected starting cell to preemptively broadcast a stimulus signal to its neighboring processor cells.

27. The method of claim 26 wherein:

said broadcasting is preceded by reading said predetermined delay time from a programmable cost memory, and

said programming comprises writing said predetermined delay time to said programmable cost memory.

28. The method of claim 27 further comprising:

preventing a stimulus signal from being transmitted from said cell along at least a selected one of said directions, whereby to impose an infinite time delay for said selected one direction corresponding to an impassable barrier of said topology.

29. The method of claim 28 further comprising:

blocking receipt of any stimulus signals along selected directions.

30. The method of claim 28 wherein said programming and said tracing back comprise:

programming cost memory means and infinite cost memory means with said time delay and said identification of directions corresponding to impassable barriers, respectively, prior to a propagation of stimulation signals throughout said array from a master processor accessing individual processor cells from row and column decoder means;

initiating broadcasting of a stimulus signal from said starting cell under control of said master processor;

reading said stored direction of successive processor cells to said master processor while tracing back said optimum path whereby to construct a list of cell locations along said optimum path.

31. The method of claim 30 further comprising sequentially enabling:

(a) programming of said cost memory means,

(b) programming of said infinite cost memory means, and

(c) reading of said direction memory means upon receipt by said cell decoder of enabling signals from said row and column decoder means.

32. The method of claim 28 wherein:

said neighboring processor cells comprise nearest neighbor processor cells disposed in orthogonal directions with respect to said cell and next-nearest neighbor processor cells disposed in diagonal directions with respect to said cell,

said cost memory means comprises an orthogonal cost memory and a diagonal cost memory, and

said programming comprises programming one time delay in said orthogonal cost memory and an other time delay into said diagonal cost memory.

33. The method of claim 24 wherein:

said array is a network of orthogonal rows and columns of said processor cells, and

the neighboring processor cells of an individual one of said processor cells comprise processor cells which are adjacent said one cell along one of;

(a) orthogonal directions only,

(b) orthogonal and diagonal directions.

34. The method of claim 33 wherein said broadcasting comprises:

broadcasting a stimulus signal along said orthogonal directions after said predetermined time delay, and

broadcasting a stimulus signal along said diagonal directions after an other predetermined time delay different from said predetermined time delay.

35. The method of claim 34 wherein:

said other predetermined time delay exceeds said predetermined time delay by a factor equal to a square root of two.

36. The method of claim 33 wherein said network is one of:

(a) a two-dimensional network, and

(b) a three-dimensional network.

37. The method claim 24 further comprising:

blocking the receipt of any further stimulus signals along at least all others of said directions upon receipt of a stimulus signal in one direction.

38. The method of claim 24 further comprising:

imposing different time delays for broadcasting stimulus signals in different ones of said directions.

39. The method of claim 38 wherein:

said neighboring processor cells comprise nearest neighbor processor cells disposed in orthogonal directions with respect to said cell and next-nearest neighbor processor cells disposed in diagonal directions with respect to said cell,

said programming comprises programming one time delay for broadcasting in said orthogonal directions and an other time delay for broadcasting in said diagonal directions from each cell.

40. The method of claim 39 wherein:

said other time delay exceeds said time delay by a factor of a square root of two.

41. A method of optimum path planning in an array of nodes, neighboring ones of said nodes being linked together so as to enable communication of stimulus signals therebetween, said method comprising:

programming a pattern of delay times into said array of nodes corresponding to a topology of a terrain to be traversed;

electronically traveling all possible paths between a starting one of said nodes and a destination one of said nodes simultaneously, wherein each of said node can only be traveled to once; and

sensing which one of said paths provided the minimum travel time from said starting node to said destination node.

42. The method of claim 41 wherein said programming comprises:

programming different predetermined delay times in different ones of said nodes in accordance with a topology across which said optimum path is to be determined.

43. The method of claim 42 wherein said electronically traveling comprises performing the following steps in each node:

(1) receiving stimulus signals from neighboring nodes along corresponding directions in said array,

(2) determining and storing the identity of a direction along which a stimulus signal is first received,

(3) broadcasting a subsequent stimulus signal to said neighboring nodes after a predetermined delay time, whereby stimulus signals propagate throughout said array from a starting one of said nodes.

44. The method of claim 43 wherein said sensing comprises:

after propagation of said stimulus signals throughout said array, tracing back from a selected destination one of said processor cells to said starting cell along an optimum path of said processor cells in accordance with said identity of a direction stored in each of said processor cells.

45. The method of claim 42 wherein said programming further comprises:

blocking broadcasting of stimulus signals in one selected direction in a selected one of said processor cells whereby to represent an impassable barrier in said topology.

46. The method of claim 42 wherein:

said programming further comprises blocking receipt of any stimulus signals along a selected direction in a selected one of said processor cells whereby to represent an impassable barrier in said topology.

47. The method of claim 41 wherein said programming comprises:

imposing different time delays for broadcasting stimulus signals in different ones of said directions in each cell.

48. A parallel processor for optimum path planning including an array of nodes, neighboring ones of said nodes being linked together so as to enable communication of stimulus signals therebetween, said parallel processor comprising:

means for programming a pattern of delay times into said array of nodes corresponding to the topology of a terrain to be traversed;

means for electronically traveling all possible paths between a starting one of said nodes and a destination one of said nodes; and

means for sensing which one of said paths provided the minimum travel time from said starting node to said destination node.

49. The parallel processor of claim 48 wherein said programming means comprises:

means for programming different predetermined delay times in different ones of said nodes in accordance with a topology across which said optimum path is to be determined.

50. The parallel processor of claim 49 wherein said means for electronically traveling comprises in each node:

(1) means for receiving stimulus signals from neighboring nodes along corresponding directions in said array,

(2) means for determining and storing the identity of a direction along which a stimulus signal is first received,

(3) means for broadcasting a subsequent stimulus signal to said neighboring nodes after a predetermined delay time, whereby stimulus signals propagate throughout said array from a starting one of said nodes.

51. The parallel processor of claim 50 wherein said means for sensing comprises:

means operable after propagation of said stimulus signals throughout said array for tracing back from a selected destination one of said processor cells to said starting cell along an optimum path of said processor cells in accordance with said identity of a direction stored in each of said processor cells.

52. The parallel processor of claim 49 wherein said means for programming further comprises:

means for blocking broadcasting of stimulus signals in one selected direction in a selected one of said processor cells whereby to represent an impassable barrier in said topology.

53. The parallel processor of claim 49 wherein:

said neighboring processor cells comprise nearest neighbor processor cells disposed in orthogonal directions with respect to said cell and next-nearest neighbor processor cells disposed in diagonal directions with respect to said cell, and

said means for programming comprises means for programming one time delay for broadcasting in said orthogonal directions and an other time delay for broadcasting in said diagonal directions from each cell.

54. The parallel processor of claim 53 wherein:

said other time delay exceeds said time delay by a factor of a square root of two.

55. The parallel processor of claim 49 wherein:

said means for programming further comprises means for blocking receipt of any stimulus signals along a selected direction in a selected one of said processor cells whereby to represent an impassable barrier in said topology.

56. The parallel processor of claim 48 wherein said means for programming comprises:

means for imposing different time delays for broadcasting stimulus signals in different ones of said directions in each cell.