Robots are increasingly being used in situations requiring them to exhibit flexible behavior. In such situations point-to-point motion sequences are inadequate. Instead, robots will probably use planning mechanisms, coupled with sensors of various kinds, to carry out their tasks. Such mechanisms allow robots to perform in situations where object position cannot be exactly specified in advance and in which unanticipated events can occur. One alternative is to teach the robot new plans. This paper describes a robot assembly system in which the robot is taught the steps in the new plan using natural language input.