狐狸视频

U of T experts in AI explore a classical problem of computer science

Photo of Alberto Camacho
Alberto Camacho, a PhD student of computer science at U of T, is investigating solutions to a classical problem in computer science known as program synthesis (photo by Ryan Perez).

The Internet of Things, or IoT, refers to the network of physical devices, from smartphones and personal fitness trackers to home alarm systems and smart refrigerators, even vehicles. Collectively, these devices can make our environment smarter.

鈥淭he promise of IoT is that it will make our lives easier,鈥 says Sheila McIlraith (pictured right), a professor of computer science at the 狐狸视频. 鈥淏ut these devices need to be programmed, instructed and customized, and most people don鈥檛 know how to program 鈥 nor should they have to.鈥

To solve this problem, McIlraith says Alberto Camacho, a PhD student in U of T's department of computer science who she supervises, is looking for synergies between fast, effective algorithms in artificial intelligence (AI) for automated planning 鈥 developed by their research group for tasking robots 鈥 and program synthesis, the task of generating a computer program automatically from a specification of user intent.

Camacho presented their work at two international conferences this summer. Their paper, &苍产蝉辫;鈥&苍产蝉辫;with contributions from U of T computer science alumni Jorge A. Baier, now an assistant professor at the Pontificia Universidad Cat贸lica de Chile, and Christian Muise, now a researcher with IBM Research AI 鈥 was presented and demonstrated at the International Conference on Automated Planning and Scheduling in Delft, the Netherlands. Camacho鈥檚 system, SynKit, was awarded the conference鈥檚 prize for best demonstration.

A second paper, , that explores fundamental principles, was presented at the International Joint Conference on Artificial Intelligence.

Synthesis, explains Camacho, is a classical problem in computer science. It was first introduced by Princeton University Professor Alonzo Church in the 1950s in the context of synthesizing digital circuits from logical specifications. Software synthesis, which Camacho and his colleagues study, has the end goal of automatically constructing software that satisfies user intent.

鈥淪ynthesis has been very well studied and understood theoretically, but no practical solutions existed,鈥 says Camacho. 鈥淣ew algorithmic approaches were introduced in 2006, and practical tools started to appear.鈥

To develop their practical tool for synthesis, Camacho uses linear temporal logic, or LTL, a form of logic that expresses what the user wants the program to do, such as 鈥渟end me an alert if someone enters the house when I鈥檓 away this weekend,鈥 or 鈥渟witch off the lights when there鈥檚 no one in the room."

Instructions in LTL sound a lot like English-language instructions, explains McIlraith, but LTL is a formal language with well-defined semantics so there is no ambiguity in the LTL statements.

鈥淚 can say something to you, and if you misunderstand, we can have a conversation back and forth [to clarify],鈥 says McIlraith. 鈥淏ut when we care about synthesizing safety-critical systems like a controller for a nuclear power plant, or for an autonomous car, it really matters that the system understands what we鈥檙e asking it to do.鈥

Camacho says they鈥檙e applying their state-of-the-art automated planning algorithms to LTL synthesis. The program which is generated is correct by construction, and every run of that program satisfies the LTL statements provided to it.

 鈥淲e think the new techniques we are introducing will have some impact,鈥 says Camacho.

This research was funded in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).

 

Topics

The Bulletin Brief logo

Subscribe to The Bulletin Brief

Computer Science