Philips Research Press Release

Whenever you want to plan a route from A to B, whether it is driving somewhere in your car or getting a robot to carry out complex maneuvers, the chances are you can do it faster and more efficiently using an algorithm developed by two senior scientists at Philips Research. Their method is so successful at optimizing computerized route-planning operations that it has won Dr. Karen Trovato and Dr. Leo Dorst the ‘2005 Inventor of the Year’ award from the New York Intellectual Property Law Association (NYIPLA), one of the USA’s leading associations of intellectual property lawyers. The award, which was presented personally to Dr. Trovato and Dr. Dorst at today’s annual meeting of the NYIPLA in New York (USA), not only recognizes the innovation and hard work that the two Philips scientists put in to develop the technology and get it patented. It is also an endorsement of the value of software patents by one of the world’s leading patent law associations.

Casting the motion-planning problem as a complex set of equations would be mathematically correct, but not very practical, because solving these takes an inordinate amount of time. Instead, Trovato and Dorst adopted a radically different approach to path planning. They proposed a computer representation in which the ‘goal’ (the required destination in the case of route mapping) radiates a series of waves into a mathematical model of the environment.

The intensity of a wave at any given point in this mathematical model represents a particular path-planning optimization characteristic such as distance from the goal. The waves spread out, interacting with the environment (for example, as they meet solid objects) in a way that locally changes the gradient of their corresponding optimization characteristic. Anything dropped into the environment that wants to optimally reach the goal merely has to sense these gradients and follow the path of the wave back to its source.

“It is a bit like locating a mature lump of cheese in a labyrinth of caves,” said Dr Leo Dorst, now an assistant professor at the University of Amsterdam, The Netherlands. “All you have to do is follow your nose.”

One advantage of the method is that for many applications the amount of real-time computing power required is well within the capabilities of mobile/portable devices such as PDAs or next-generation cell-phones.

“I remember listening to a graduate lecture on the conceptual problem of maneuvering a grand piano and quickly realizing that the continuous mathematical approach required too much compute power for real-time applications,” said Dr Karen Trovato, Principal Member of Research Staff at Philips. “Then on hearing the ideas of Leo Dorst, I knew that between us we could come up with a more practical solution.”

A second advantage of the technique is that it is easily adapted to any goal-directed application, provided you can define optimality, model fundamental motions within the environment and calculate the cost of those motions.

For example, by evaluating inputs from temperature sensors and smoke detectors distributed throughout a building, an intelligent fire alarm system could automatically direct you to the safest exit rather than the nearest exit, indicating the way by controlling illuminated arrows. Another example cited by Karen Trovato is a car that automatically maneuvers itself in and out of parking places. The technology is also likely to find important application in the Philips vision of Ambient Intelligence – environments that are aware of our presence and responsive to our needs.

Granted under a patent titled ‘Method and Apparatus for Path Planning’ this innovative technology adds to the extensive patent portfolio that has come out of Philips Research – one of the largest patent portfolios in the world generated by a private research organization.

 

Car that parks itself

 

A high-resolution picture of Dr Karen Trovato is available from:
www.research.philips.com/newscenter/pictures/050525-prize_nyipla.html

For further information please contact:

Philips Research
Betsy McIlvaine
Tel.: 1.914.945.6195
E-mail: betsy.mcilvaine@philips.com
 

About Royal Philips Electronics

Royal Philips Electronics of the Netherlands (NYSE: PHG, AEX: PHI) is one of the world's biggest electronics companies and Europe's largest, with sales of EUR 30.3 billion in 2004. With activities in the three interlocking domains of healthcare, lifestyle and technology and 160,900 employees in more than 60 countries, it has market leadership positions in medical diagnostic imaging and patient monitoring, color television sets, electric shavers, lighting and silicon system solutions. News from Philips is located at www.philips.com/newscenter.