|Search Duke CS||
At the University of Maryland (UMD) last year a special symposium was held to celebrate Dana Nau's 60th birthday and to honor their renowned Professor of Computer Science's contributions to the field of Artificial Intelligence (AI).
Our department's own Alan Biermann travelled to College Park, MD, for the occasion. Thirty-plus years ago, Biermann was a newly appointed Assistant Professor, and Nau was among his first students. Biermann, now Professor Emeritus, eventually became Nau's advisor. "Right from the beginning, the faculty thought that Nau was a very, very unusual student," Biermann said, adding that Nau was always the student asking the most penetrating questions, whether he was in a department seminar or an invited talk by a guest speaker.
Biermann helped point Nau in the direction of game theory, suggesting that for his dissertation Nau investigate the widely held belief that searching deeper in game trees would always lead to better results. In game theory the game tree is a directed graph representing a sequential game. Nodes on the graph represent possible positions in the game, and edges show possible moves from one position to another. At that time the standard methodology for making a decision about the next move in a game was to search the game tree up to a depth limit, then use the values backed up to the starting position to select a move.
Although it seemed obvious that a deeper search would yield a better result, no one had yet proved it mathematically. Nau went to work on the problem, only to find that some trees actually yielded worse results when the search went deeper. Carrying this discovery further, he came up with a groundbreaking work identifying "Pathological Game Trees" -- a whole new class of game trees where deeper searches led to worse decisions. Nau's discovery of game tree pathology is held in great esteem by the AI community. Judea Pearl, the 2011 Association for Computing Machinery Turing Award winner, included some of Nau's work in his famous 1984 book Heuristics: Intelligent Search Strategies for Computer Problem Solving.
Nau graduated from Duke with his doctoral degree in 1979 and joined UMD as an Assistant Professor almost immediately afterwards. At UMD he holds appointments in Computer Science and the Institute for Systems Research, and he has affiliate appointments in the Institute for Advanced Computer Studies and the Department of Mechanical Engineering. Broadly stated, he works in automated planning, diagnostic inference, adversarial and game theoretic reasoning, and automated manufacturing. Not one to shy away from challenges, he has often ventured outside his immediate fields to seek newer topics for research and to collaborate with researchers across disciplines. Most recently he has branched out to investigate the connection between game theory and cultural psychology; he is the Co-Director of the Laboratory for Computational Cultural Dynamics at UMD.
Early in his career he worked with scientists at the National Institute of Standards and Technology to apply AI techniques to solving planning problems in automated manufacturing. He later went on to work with then-UMD colleague Jim Hendler, building a long and productive scientific collaboration in the branch of AI now often simply called 'Planning.'
Around the same time Thomas Throop of Great Game Products Inc. asked for Nau's advice on using AI techniques to improve computer bridge-playing programs. This led Nau and his student Stephen Smith to the creation of game-playing algorithms that were used by Throop's "Bridge Baron" program to win the World Computer-Bridge Championships in 1997.
Nau also created SHOP (the Simple Hierarchical Ordered Planner), an automated planning system, which he made available as open source software. It has been downloaded and used on thousands of projects around the world. A later version of the work, SHOP2, won an award at the 2002 International Planning Competition.
Nau joined with Malik Ghallab of France's Laboratory for Analysis and Architecture of Systems, part of the National Center for Scientific Research (LAAS-CNRS) in Toulouse, and Paolo Traverso of the Bruno Kessler Foundation's Center for Information Technology (FBK-ICT) in Trento, Italy, to write a textbook. Published in 2004, Automated Planning: Theory and Practice has become the go-to textbook in AI Planning courses.
When it came to the symposium in his own honor, however, Nau chose to present a comic-book version of his long and distinguished career, informing attendees that he would not lecture them on technical details, because he wanted to "keep it from being deadly boring." He succeeded, and it is clear the distinguished Duke CS alumnus is still the "bright and shining student" Biermann remembers so well.