System and method for tracking vehicles using random search algorithms

• US 6,115,700 A
• Filed: 01/31/1997
• Issued: 09/05/2000
• Est. Priority Date: 01/31/1997
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Gong, Kai F., Hammel, Sherry E., Ferkinhoff, David J.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): PENDER JR, MICHAEL J
• Application Number:
  US08/792,266
• Time in Patent Office: 1,313 Days
• Field of Search: 706/13, 382/103, 367/131, 361/131
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The present invention relates to a method and a system for providing an estimate of the state of a contact. The method includes the steps of sensing the state of the contact; generating signals representative of the state of the contact; and processing the signals using a random search procedure to arrive at an estimate of the state of the contact. The random search procedure may employ the simulated annealing-based algorithm methodology or the genetic-based algorithm methodologies. The system includes sensors for sensing the state of the contact and a pre-programmed computer for generating the desired contact state estimates.

Claims

1. A method for providing an estimate of the state of a contact comprising:

sensing the state of said contact;

generating signals representative of the state of said contact;

processing said signals to arrive at estimates of the state of said contact;

said processing step comprising applying a simulated annealing algorithm methodology to said signals to generate a contact state estimate solution;

said applying step comprising making an initial random guess of said state of said contact;

computing the cost of the contact state estimate;

randomly generating a small change in the contact state estimate;

computing the cost of the new target state estimate;

comparing the new target state estimate against a stopping criteria to determine if said stopping criteria has been met; and

changing the simulated annealing temperature if a desired number of iterations has been performed since last temperature update, or incrementing the simulated annealing temperature counter if said desired number of iterations has not been performed.

2. The method according to claim 1 further comprising:

determining the probability of accepting the target state estimate using the following equation;

##EQU17## where T_j is the simulated annealing temperature at the j^th simulated annealing temperature iteration and Δ

E is the change in cost; and

using a simulated annealing temperature schedule according to the following equation;

space="preserve" listing-type="equation">T.sub.j =α

jT.sub.0,

where T₀ is the initial simulated annealing temperature and α

is a constant less than unity.

3. The method according to claim 1 further comprising:

determining if the change in energy is negative; and

updating the contact state estimate if said change in energy is negative.

4. The method according to claim 1 further comprising:

determining if the change in energy is negative;

determining t he probability of accepting the new contact state estimate if the change in the contact state is not negative;

comparing the probability to a random threshold; and

updating the contact state estimate if the probability of accepting the new contact state estimate exceeds said random threshold or returning to said random generating step if the probability of accepting the new contact state estimate does not exceed said random threshold.

6. The method according to claim 1 further comprising:

computing weighted and normalized performance for the samples if the cost of the samples in said new generation is not below the threshold value; and

replacing the original population.

7. The method according to claim 6 further comprising:

performing mutation on said samples in said new generation; and

determining the cost for all samples in said new population.

5. A method for providing an estimate of the state of a contact comprising:

sensing the state of said contact;

generating signals representative of the state of said contact;

processing said signals to arrive at estimates of the state of said contact;

said processing step comprising applying a genetic algorithm to said signals to generate a contact state estimate;

said application of a genetic algorithm step comprising generating a population having a number of randomly distributed samples of contact state spaces, determining the cost for all of said samples in said population, and comparing the cost of all of said samples to a threshold value to determine if the cost of any one of said samples is less than said threshold value;

determining weighted and normalized performance values for all samples;

selecting parents for crossover;

producing pairs of parents from said selected parents;

performing crossover for said pairs of parents and creating a new generation;

determining the cost of all samples in said new generation;

comparing the cost of all samples in said new generation;

comparing the cost of the samples in said new generation to a threshold value to determine if the cost of any one of the samples in said new generation is below the threshold value and stopping if it is; and

constructing a binary representation by concatenating a binary representation of the state variable into a single binary sequence as

space="preserve" listing-type="equation">XT.sub.bi =[RxT.sub.bi RyT.sub.bi VxT.sub.bi VyT.sub.bi ],

where, for the i^th sample, ##EQU18##

8. A system for providing an estimate of the state of a contact comprising:

means for sensing the state of said contact and for generating signals representative of the state of said contact;

means for processing said signals to generate an estimate of the contact state parameters, said processing means comprising pre-programmed means for applying a simulated annealing methodology to said signals to generate the contact state estimate; and

said simulated annealing methodology applying means comprising means for making an initial random guess of the contact state, means for computing the cost of the contact state estimate, means for randomly generating a small change in the contact state estimate, means for computing the cost of the new target state estimate, means for comparing the new target state estimate against a stopping criteria to determine if said stopping criteria has been met, means for changing the simulated annealing temperature if a desired number of iterations has been performed since the last simulated annealing temperature update or incrementing the simulated annealing temperature counter if said desire number of iterations has not been performed, means for determining the probability of accepting the target state estimate using the following equation;

##EQU19## where T_j is the simulated annealing temperature at the j^th simulated annealing temperature iteration and Δ

E is the change in cost, and means for generating a simulated annealing temperature schedule according to the following equation;

space="preserve" listing-type="equation">T.sub.j =α

jT.sub.0,

where T₀ is the initial simulated annealing temperature and α

is a constant less than unity.

10. The system of claim 8 wherein said processing means comprises means for providing an initial estimate of said contact state parameters.

11. The system of claim 8 further comprising means for checking the consistency of estimated contact state parameters generated by said processing means.

9. A system for providing an estimate of the state of a contact comprising:

means for sensing the state of said contact and for generating signals representative of the state of said contact;

means for processing said signals to generate an estimate of the contact state parameters, said processing means comprising pre-programmed means for applying a random search methodology to said signals;

said pre-programmed means comprising means for applying a genetic algorithm methodology to said signals to generate the contact state estimate; and

said generic algorithm methodology applying means comprising;

means for generating a population having a number of randomly distributed samples of contact state spaces;

means for determining the cost for all of said samples in said population;

means for comparing the cost of all of said samples to a threshold value to determine if the cost of any one of said samples is less than said threshold value;

means for determining weighted and normalized performance values for all samples;

means for selecting parents for crossover;

means for producing pairs of parents from said selected parents;

means for performing crossover for said pairs of parents and creating a new generation;

means for determining the cost of all samples in said new generation;

means for comparing the cost of the samples in said new generation to a threshold value to determine if the cost of any one of the samples in said new generation is below the threshold value and stopping if it is; and

constructing a binary representation by concatenating a binary representation of the state variables into a single binary sequence as

space="preserve" listing-type="equation">XT.sub.bi =[RxT.sub.bi RyT.sub.bi VxT.sub.bi VyT.sub.bi ],

where, for the i^th sample, ##EQU20##10.