Neal Lesh

AAAI Conference 2005 System Paper

DiamondHelp: A Collaborative Task Guidance Framework for Complex Devices

• Charles Rich
• Neal Lesh
• Shane Booth

DiamondHelp is a reusable Java framework for building collaborative task guidance systems for complex devices, such as digitally enabled home appliances. DiamondHelp combines a generic conversational interface, adapted from online chat programs, with an application-specific direct manipulation interface. DiamondHelp provides ‘a things to say” mechanism for use without spoken language understanding; it also supports extensions to take advantage of speech technology. DiamondHelp’s software architecture factors all application-specific content into two modular plug-ins, one of which includes Collagen and a task model.

AIJ Journal 2005 Journal Article

Explorations in engagement for humans and robots

• Candace L. Sidner
• Christopher Lee
• Cory D. Kidd
• Neal Lesh
• Charles Rich

This paper explores the concept of engagement, the process by which individuals in an interaction start, maintain and end their perceived connection to one another. The paper reports on one aspect of engagement among human interactors—the effect of tracking faces during an interaction. It also describes the architecture of a robot that can participate in conversational, collaborative interactions with engagement gestures. Finally, the paper reports on findings of experiments with human participants who interacted with a robot when it either performed or did not perform engagement gestures. Results of the human–robot studies indicate that people become engaged with robots: they direct their attention to the robot more often in interactions where engagement gestures are present, and they find interactions more appropriate when engagement gestures are present than when they are not.

MFCS Conference 2004 Invited Paper

Theory and Applied Computing: Observations and Anecdotes

• Matthew Brand
• Sarah F. Frisken Gibson
• Neal Lesh
• Joe Marks
• Daniel Nikovski
• Ronald N. Perry
• Jonathan S. Yedidia

Abstract While the kind of theoretical computer science being studied in academe is still highly relevant to systems-oriented research, it is less relevant to applications-oriented research. In applied computing, theoretical elements are used only when strictly relevant to the practical problem at hand. Theory is often combined judiciously with empiricism. And increasingly, theory is most useful when cross-pollinated with ideas and methods from other fields. We will illustrate these points by describing several recent projects at Mitsubishi Electric Research Labs that have heavy mathematical and algorithmic underpinnings. These projects include new algorithms for: traffic analysis; geometric layout; belief propagation in graphical models; dimensionality reduction; and shape representation. Practical applications of this work include elevator dispatch, stock cutting, error-correcting codes, data mining, and digital typography. In all cases theoretical concepts and results are used effectively to solve practical problems of commercial import.

AAMAS Conference 2002 Conference Paper

A Plug-in Architecture for Generating Collaborative Agent Responses

• Charles Rich
• Neal Lesh
• Jeff Rickel

AAAI Conference 2000 Conference Paper

Human-Guided Simple Search

• David Anderson
• Neal Lesh
• Brian Mirtich
• MERL -- Mitsubishi Electric Research Laboratory; Kathy Ryall

Scheduling, routing, and layout tasks are examples of hard operations-research problems that have broad application in industry. Typical algorithms for these problems combine some form of gradient descent to find local minima with some strategy for escaping nonoptimal local minima. Our idea is to divide these two subtasks cleanly between human and computer: in our paradigm of human-guided simple search the computer is responsible only for finding local minima using a simple hill-climbing search; using visualization and interaction techniques, the human user identifies promising regions of the search space for the computer to explore, and intervenes to help it escape nonoptimal local minima. We have applied our approach to the problem of capacitated vehicle routing with time windows, a commercially important problem with a rich research history. Despite its simplicity, our prototype system is competitive with the majority of previously reported systems on benchmark academic problems, and has the advantage of keeping a human tightly in the loop to handle the complexities of real-world applications.

AAAI Conference 1999 Conference Paper

Simulation-Based Inference for Plan Monitoring

• Neal Lesh
• MERL - A Mitsubishi Electric Research Laboratory
• James Allen
• University of Rochester

Thedynamicexecution of plans in uncertain domains requires the ability to infer likely current andfuture worldstates from past observations. Wecast this task as inference on DynamicBelief Networks(DBNs)but the resulting networksare difficult to solve with exact methods. Weinvestigate and extend simulation algorithms for approximateinference on Bayesiannetworks and propose a newalgorithm, called Rewind/Replay, for generating a set of simulations weightedby their likelihood givenpast observations. Wevalidate our algorithm on a DBN containing thousands of variables, whichmodelsthe spread of wildfire.

AAAI Conference 1998 Conference Paper

Improving Big Plans

• Neal Lesh

Past research on assessing and improving plans in domainsthat contain uncertainty has focused on analytic techniquesthat are exponentialin the length of the plan. Little workhas beendoneon choosingfrom amongthe manywaysin which a plan can be improved. Wepresent the IMPROVE algorithm which simulatesthe executionof large, probabilistic plans. IMPROVE runs a data miningalgorithm on the execution traces to pinpoint defects in the plan that most often lead to plan failure. Finally, IMPROVE applies qualitative reasoningand plan adaptation algorithms to modifythe plan to correct these defects. Wehave tested IMPROVE on plans containing over 250steps in an evacuation domain, producedby a domain-specific schedulingroutine. In these experiments, the modified plans haveover a 15% higher probability of achieving their goalthan the original plan.

IJCAI Conference 1997 Conference Paper

Adaptive goal recognition

• Neal Lesh

Because observing the same actions can warrant different conclusions depending on who executed the actions, a goal recognizer that works well on one person might not work well on another. Two problems that arise in providing user-specific recognition are how to consider the vast number of possible adaptations that might be made to the goal recognizer and how to evaluate a particular set of adaptations. For the first problem, we evaluate the use of hillclimbing to search the space of all combinations of an input set of adaptations. For the second problem, we present an algorithm that estimates the accuracy and coverage of a recognizer on a set of action sequences the individual has recently executed. We use these techniques to construct Adapt, a recognizer-independent unsupervised-learning algorithm for adapting a recognizer to a person's idiosyncratic behaviors. Our experiments in two domains show that applying Adapt to the BOCE recognizer can improve its performance by a factor of two to three.