Los Angeles, California - An innovation in artificial intelligence that was described in a 2001 paper by a UCLA computer science professor has found a somewhat unexpected application: helping car buyers customize their vehicles online.
The websites for Toyota and its Lexus division both offer shoppers the opportunity to tailor their vehicle from among a range of models, colors and accessories. The software that powers the sites, called a “product configurator,” is based on a logical form of artificial intelligence that was devised by Professor Adnan Darwiche.
The websites use artificial intelligence to perform sophisticated, real-time reasoning to ensure that if a consumer wants a specific vehicle — for example, a red Camry with a tan interior and a performance package — that exact combination of options could be manufactured by the company or is available in its inventory. The websites can also reason about features that are co-dependent, such as removing a minimum number of features when a combination is not feasible or determining which features must be bought together.
“I was very pleased to see this appreciation for the practical significance of my work to the point of adopting it for this massive commercial application,” Darwiche said. “What was particularly gratifying is that engineers found my publications sufficiently detailed to implement the work, without additional help from me or my group at UCLA.”
Darwiche’s innovation, known as a decomposable negation normal form circuit, addressed a central challenge in artificial intelligence: How to efficiently reason with knowledge, which is a core task of intelligent behavior. His research on DNNF circuits, which was published in the Journal of the Association for Computing Machinery, is just one part of his body of work in a field called knowledge compilation.
Knowledge compilation assembles knowledge into simple forms that allow reasoning to be conducted very efficiently. Darwiche proposed the compilation of knowledge into tractable circuit representations, including DNNF circuits, leading to very simple and minimal reasoning systems.
Another challenge of sites like Toyota’s is that the artificial intelligence decision-making must take place on the user’s computer. Having all of those computations take place on the company’s servers would overload the system if too many people were using it at the same time, but forcing it to happen on users’ machines would allow any number of cars to be configured simultaneously. This, in turn, means that the configurator must use minimal computer memory so it doesn’t strain users’ home devices.
To accomplish that, knowledge about Toyota’s manufacturing combinations and available inventory is compiled into a DNNF circuit, which is then loaded into the shopper’s web browser. Configuration takes place within the web browser using simple and efficient DNNF algorithms.
Darwiche said another type of tractable circuits he developed, called sentential decision diagrams, are being evaluated by Toyota as a possible way to allow more sophisticated queries in the product configurator. He described his research on sentential decision diagrams in a presentation at the 2011 International Joint Conference on Artificial Intelligence.
Although tractable circuits were originally developed for efficient reasoning, Darwiche says that researchers have employed them in other tasks, including machine learning.
More recently, Darwiche has started an effort to use tractable circuits to help solve a highly complex type of computer science problems known as Beyond NP problems.
“These tasks will expand the use of computers in various applications, including medical decision making, yet our current knowledge is limited on how to solve them very efficiently,” he said.
