  We present a novel approach for generating plausible verbal interactions
between virtual human-like agents and user avatars in shared virtual
environments. Sense-Plan-Ask, or SPA, extends prior work in propositional
planning and natural language processing to enable agents to plan with
uncertain information, and leverage question and answer dialogue with other
agents and avatars to obtain the needed information and complete their goals.
The agents are additionally able to respond to questions from the avatars and
other agents using natural-language enabling real-time multi-agent multi-avatar
communication environments.
  Our algorithm can simulate tens of virtual agents at interactive rates
interacting, moving, communicating, planning, and replanning. We find that our
algorithm creates a small runtime cost and enables agents to complete their
goals more effectively than agents without the ability to leverage
natural-language communication. We demonstrate quantitative results on a set of
simulated benchmarks and detail the results of a preliminary user-study
conducted to evaluate the plausibility of the virtual interactions generated by
SPA. Overall, we find that participants prefer SPA to prior techniques in 84\%
of responses including significant benefits in terms of the plausibility of
natural-language interactions and the positive impact of those interactions.
