  Many real-world tasks require agents to coordinate their behavior to achieve
shared goals. Successful collaboration requires not only adopting the same
communicative conventions, but also grounding these conventions in the same
task-appropriate conceptual abstractions. We investigate how humans use natural
language to collaboratively solve physical assembly problems more effectively
over time. Human participants were paired up in an online environment to
reconstruct scenes containing two block towers. One participant could see the
target towers, and sent assembly instructions for the other participant to
reconstruct. Participants provided increasingly concise instructions across
repeated attempts on each pair of towers, using higher-level referring
expressions that captured each scene's hierarchical structure. To explain these
findings, we extend recent probabilistic models of ad-hoc convention formation
with an explicit perceptual learning mechanism. These results shed light on the
inductive biases that enable intelligent agents to coordinate upon shared
procedural abstractions.
