Bar-Shalom Designs Computer
Software That Can Track Targets
By Brent C. Evans
he next time you catch a flight, your trip may owe something to Yaakov Bar-Shalom.
A new generation of air traffic control systems is being put in place, and he has designed its brains.
Bar-Shalom, a professor of electrical and computer engineering, develops sets of computer instructions, or algorithms, that keep track of objects, such as airplanes. His work is already being used in Boston by Logan airport's ground traffic monitoring system, by the Navy, and in Israeli and U.S. missile defense systems. It may also help biologists - for example, by tracking cells in the bloodstream.
The task is to get computers to see connections between the snapshots of data they receive from sensors such as radar. "Sensors send you information in frames," says Bar-Shalom. "You can think of them as snapshots with a bunch of dots."
Bar-Shalom begins by giving the computer a model of an object's motion, which will vary according to the tracking system's intended purpose. If the object has been moving in a straight line, the model predicts that it will continue to do so. So the computer predicts a path for each object, and checks whether an object appears on that track in the next frame.
Planes and cells, however, may suddenly change direction, and all radars make some measurement errors. "The motion of objects is not predictable," Bar-Shalom says. "You have to account for the uncertainty of the motion and the uncertainty of the measurements."
If a plane takes a turn, and the computer rigidly assumes it will continue in a straight line, the computer will look in the wrong spot for the plane. So the computer must be flexible.
Bar-Shalom has developed a way to tell a computer exactly how flexible it should be. He instructs the computer to make a "window" around the object's next predicted position. If the signal from the radar is slightly off-target, or if the object begins to turn, the object will remain inside the window and be recognized by the computer. If the object begins a turn, the computer will switch to another motion model.
Bar-Shalom bases the width of the window on the reliability of the sensor and the regularity of the object's motion.
One application with a large number of targets is cell biology. Several years ago, Bar-Shalom began developing a system for tracking cells with Leslie Loew, a professor of physiology and director of the center for bio-medical imaging technology.
Tracking cell movement can allow researchers to watch cells' reactions to a certain stimulus; it is an established research tool, but currently, researchers are sometimes forced to track cells by hand. Loew wants an automated system. "We're trying to find a general algorithm for taking very complicated movies of cells in motion," Loew says. "The reason it's complicated is that cells change shape and go in all sorts of odd directions."
Difficulties arise when two cells overlap. To the computer, the two will appear as one blob. So how will the computer know which is which when they separate again? With Bar-Shalom's algorithm, the computer remembers the shape and direction of each cell, and, while they are overlapped, takes a guess at which part of the blob is which cell.
His algorithms also drive an Australian radar system that keeps track of all sea and air traffic within a 2,500-mile radius.
Bar-Shalom, whose first name, coincidentally, in modern Hebrew means "he shall track," has published prolifically in the field of target tracking, authoring 110 journal papers and four books. He is president of the International Society of Information Fusion and is a frequent keynote speaker at major conferences in his field.
Last May, Bar-Shalom's colleagues organized a workshop in his honor. They also published a 600-page festschrift, or celebratory writing, to honor his contributions to the field.
"Yaakov is the father of target tracking," says Peter Willett, a professor of electrical and computer engineering. "He's one of the people this university can be very proud of."