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