Thursday, October 8, 2009

Blast from the Past

I just found this nice repository of old from from International Joint Conference on Artificial Intelligence. Lots of good stuff all the way from 1969.

One of my favorite findings was this paper from 1989 (If not mistake, the classic paper on velocity obstacles was published a decade later):

A Maneuvering-Board Approach to Path Planning with Moving Obstacles
Lou Tychonievich, David Zaret, John Mantegna, Robert Evans, Eric Muehle and Scott Martin

The year 1989 was like 20 years ago and yet we manage to produce games where NPCs have trouble avoiding walls and other kinds of minor things. So nice we have Google nowadays.

One quite important trick present in that '89 paper, that is missing from the Fiorini paper (IIRC) is the cone truncation. Applying the truncation helps a lot in many practical cases. Especially when trying to reach your final destination. Gladly it is well represented in Reciprocal n-body Collision Avoidance.


  1. Hum seems like a good antique (even the classic motion planning book Robot Motion Planning by Latombe is posterior).
    I'll read that carefully...

  2. I realize this is a 2-year-old post, but…

    This technique was hardly new in 1989. Almost a century earlier, the 1903 book “Instructions for the Use of Martin’s Mooring Board and Battenberg’s Course Indicator” by Miller and Everett describes a mechanical automation for the same approach. Even in that book it is the mechanical tool that is presented as novel; the underlying algorithm appears to have been commonplace. How much earlier the algorithm was used I have been unable to determine.