Abstract
We propose a method to generate optimal natural language for block placementdirectives generated by a machine's planner during human-agent interactions inthe blocks world. A non user-friendly machine directive, e.g., move(ObjId,toPos), is transformed into visually and contextually grounded referringexpressions that are much easier for the user to comprehend. We describe analgorithm that progressively and generatively transforms the machine'sdirective in ECI (Elementary Composable Ideas)-space, generating manyalternative versions of the directive. We then define a cost function toevaluate the ease of comprehension of these alternatives and select the bestoption. The parameters for this cost function were derived empirically from auser study that measured utterance-to-action timings.