Programming Computers to Help Programmers

Computer scientists from Rice University, the University of Pennsylvania and seven other institutions are teaming up to address one of the greatest ironies of the information age: While computers and robots have automated the manufacture of thousands of products, the software that allows them to do this is still written mostly by hand.

Armed with a $10 million grant from the National Science Foundation (NSF), the researchers hope to create intelligent software agents — smart programs that can first observe and learn from human programmers and then help humans write code faster and with fewer errors. Based at Penn, the five-year effort is dubbed Expeditions in Computer Augmented Program Engineering, or ExCAPE. It is funded by the NSF’s Expeditions in Computing program, which supports ambitious research agendas that will define the future of computing.

“What it means to ‘code’ hasn’t changed much in the last 20 to 30 years,” said Penn computer scientist Rajeev Alur, the project’s principal investigator. “It’s still done by expert programmers and is quite time-consuming, expensive and error-prone.”

The ExCAPE research team includes Rice computer scientists Moshe Vardi and Lydia Kavraki and researchers from MIT, UCLA, Cornell University, the University of Illinois at Urbana-Champaign, the University of Maryland, the University of Michigan and the University of California, Berkeley. The goal of the team is to create “automated program-synthesis tools” for a variety of applications.

Rice’s team will address robotic applications and how to verify that the synthetic, computer-generated code is safe and effective.

Kavraki, a leading robotics expert and Rice’s Noah Harding Professor of Computer Science and of bioengineering, said that robotics provides an ideal test bed for automated program-synthesis tools.

“Programming is now done by experts only, and this needs to change if we are to use robots as helpers for humans,” Kavraki said. “At the same time, safety is critical. You can only have robots help humans in a task — any task, whether mundane, dangerous, precise or expensive — if you can guarantee that the behavior of the robot is going to be the expected one.”

Kavraki said she and Vardi, who have collaborated on advanced robotic methodologies in prior research, have proposed a “grand challenge” robotic scenario for ExCAPE: Create an automated program-synthesis tool that hospital staff could use to program mobile robots that go from room to room, turn off lights, distribute medications, remove medical waste and more.

“The robot will be instructed by medical staff using structured language,” Kavraki said. “The automated program-synthesis tool needs to be able to take the staff’s instructions and combine those with a set of standard rules such as, ‘Do not drive into a wall or a person,’ and come up with a set of low-level commands that will drive the robot’s motors and sensors. Finally, we need to be able to guarantee, in advance, that the synthetic code is both correct and safe.”

Programming for robotic behavior is one of four real-word problem areas the ExCAPE team will test their research upon. Other challenge areas involve figuring out how to set up routing policies for flow of information across networks of computers, how software written to work on single-processor computers can be correctly translated to improve performance while running on multiple cores that are now common even in mobile devices, and how to design efficient and correct algorithms for coordinating decisions among multiple computers.

In each of these applications, tools will be needed to verify that the synthetic code is both safe and effective. Vardi, Rice’s Karen Ostrum George Distinguished Service Professor in Computational Engineering and one of the world’s leading experts on computer verification, said the new tools need to find both coding errors and the flawed logic that led to the errors.

“Our programs need to behave something like a skilled teacher that listens carefully when a student gives the wrong answer in class,” Vardi said. “The real questions for the teacher are, Why did the student get the wrong answer? What don’t they understand, and how can I help them learn it? These are the same questions our verification tools need to ask and answer if automated program-synthesis tools are to succeed.”

The ExCAPE researchers plan to work with industry partners AT&T, Coverity, Honeywell, IBM, Intel, Microsoft and Willow Garage to see if their new automated program-synthesis tools are effective at meeting the day-to-day coding challenges that programmers face.