This dissertation explores embodied agents that can improvise with people in an object-based gestural proto-narrative domain. I study the improvisational action selection problem (the challenge of performing action selection ...