Approximate Maximum Likelihood Estimation


Chief Investigator:

Panos Tzanos



Problem Statement:


We want to find computationally efficient methods to estimating the location of a biochemical source.  Finding the maximum likelihood (ML) estimates of the vapor source location corresponds to solving a nonlinear maximization problem.  This procedure can be computationally expensive.  We propose two methods to approximate the ML estimates that are easier to implement, computationally cheaper and can bring a greater understanding to the motion control problem.


Mathematical Preliminaries:


We model our sensor measurements as follows:



Where is our measurement model matrix that depends on the unknown parameters contained in the vector ,  is a vector of unknown parameters and is a Gaussian white noise vector. The vector contains the vapor source location parameters.  Using ML estimation, an estimate of can be computed as




where  is the complimentary projection matrix of the matrix .


One Step Newton-Raphson Algorithm:


This approximation technique is commonly used in system identification.  Let  be the estimate of at time instant , and let , the estimate of theta at the previous time instant.  Then the one step Newton-Raphson update is



where the primes denote derivative with respect to .


First-Order Taylor Series Approximation:


Finding the ML estimate essentially involves finding the vector that makes the column space of as parallel to as possible.  The first-order Taylor Series approximation involves solving a set of bilinear equations, which have a unique solution, for the approximate ML estimates of .  Details can be found here.





Both of these methods are computationally less expensive than ML estimation, and recursive.  The following figures show that these methods are comparable to ML estimation in terms of the accuracy of estimation, and the time it takes for the estimates to converge:





The figure to the left depicts the trajectories of the robot for the cases of ML estimation, the Newton-Raphson approximation and the Taylor-Series approximation.  “DOG” is the acronym for the “Direction of Gradient” algorithm, which is an information based motion algorithm developed by Porat and Nehorai, 1996.  In their development they strictly used ML estimation.  In each case we are using the DOG algorithm but a different estimation approach. As you can see, for each estimation technique, the trajectory of the sensor is nearly identical.


The middle figure depicts the distance between the estimates and the source location.  In each case, the estimates converge to the true value of the source location at about the same time.


Finally, the figure to the right depicts the Cramer-Rao Bound for the source location estimates.  The source location in each case is estimated with a high degree of accuracy.







Here is a movie of the motion of the robot using the first-order Taylor Series Approximation.





This research is supported by NSF grant CCR-0330342