Several Ways To Improve Efficiency Of Answer Set Programming And Its Application In Service Robots

With the development of the theory and the presence of efficient solvers, more and more researches considered Answer Set Programming (ASP) as a general knowl-edge representation and reasoning (KR) tool with non-monotonic reasoning ability, and applied it in many areas. Currently, the low efficiency is still the bottleneck for more applications of ASP, and more applications are also needed. These two are related, higher efficiency brings more applications, more applications provide more practical requirements. The dissertation provides some approaches for improving the efficiency of ASP solvers by conclusions of the program (formulas that are true in every answer set), and uses ASP to implement some cognitive abilities for service robots, such as au-tomated planning, natural language understanding, and automated diagnosis. We have implemented the system for "Ke Jia" home service robot of USTC. We have tested the abilities of "Ke Jia" by a series of typical tasks, and designed a simulation test to systematically measure the ability of intelligent problem solving for service robots.The dissertation contains three main contents:some approaches for improving the efficiency of ASP solvers by conclusions of the program; using ASP to implement some cognitive abilities for service robots, such as automated planning, natural language understanding, and automated diagnosis; a series of tests for the performance of the system and the results.In this dissertation, the main idea for improving the efficiency of ASP solvers is to compute more consequences and using them more efficiently. Based on this idea, we provide three approaches:Firstly, we compute consequences from the loop formu-las of loops with at most one external support rules in the program and the completion of the program by unit propagation. We see that these loop formulas are equivalent to sets of unit or binary clauses. For normal logic programs, these loop formulas can be computed in polynomial time, and for disjunctive logic programs, we propose a poly-nomial algorithm for computing some of these loop formulas. We discuss the relations to well-founded models and other related work for normal and disjunctive programs, and show experimentally that these extra consequences can help ASP solvers to find answer sets of certain programs. Secondly, we propose a general framework for char-acterizing well-founded semantics for disjunctive logic programs, and discuss how to compute consequences of a program from the framework. The basic idea of the frame- work is to characterize each well-founded semantics for disjunctive programs as the least fixed-point of a consequence operator based on GL-transformation and the form of consequences. We proved that some recent semantics for disjunctive well-founded semantics can be characterized in the framework, and the framework can provide some guidance for computing consequences of a program within certain computational com-plexities. Lastly, we provide some ways for simplifying programs by consequences, and provide conditions for the equivalence between the program and the simplified program. Well-founded models are usually used for simplifying programs, but gen-erally, other consequences cannot be used as well-founded models, here we specified the conditions for equivalent simplification.On the other hand, many researchers become focused on service robots. Service robots need to accomplish complex tasks in a complex environment, so some cognitive abilities such as automated planning, natural language understanding, and automated diagnosis are necessary, which are not well implemented currently. In this dissertation, we propose to use ASP to implement these cognitive abilities for service robots. We use ASP to implement the ability for automated planning for robots, a planning problem is reduced to the problem of finding an answer set of the corresponding ASP program. Then, ASP is used for natural language understanding. The robot acquires tasks, in-formation and casual knowledge from natural language sentences proved by the user. These sentences are first converted to sets of predicates by lazy semantic interpreta-tion, then based on these sets of predicates, tasks are translated goals in corresponding ASP programs, information and casual knowledge are translated to ASP rules which are later added to the knowledge base. At last, we use ASP to implement the ability for automated diagnosis and a diagnosis is related to an answer set with minimal abnormal components of the system.We have implemented the system for "Ke Jia" home service robot. We also de-signed a series of typical tasks for "Ke Jia" to test its abilities, and a simulation test to systematically measure the ability of intelligent problem solving for service robots. We compared "Ke Jia" with other approaches on the simulation test. The accomplish-ment of the tasks and the results for the simulation test showed that, ASP is feasible and convenient for the implement of these cognitive abilities for service robots.Three main contributions are summarized as follows:·Three approaches for improving the efficiency of ASP solvers by conclusions of the program are provided. First, the. dissertation provides how to compute loop formulas of loops with at most one external support rule in the program, proves the relation between the computed consequences and other related work, and shows experimentally that these extra consequences can help ASP solvers to find answer sets of certain programs. Second, the dissertation proposes a general framework for characterizing well-founded semantics for disjunctive logic programs, proves that some recent semantics for disjunctive well-founded semantics can be char-acterized in the framework, and discusses how to compute consequences of a program from the framework. At last, the dissertation provides some ways for simplifying programs by consequences, and provides conditions for the equiva-lence between the program and the simplified program.·In this dissertation, ASP is used to solve planning problems for service robots, and a way to convert the results of lazy semantic interpretation to corresponding ASP rules is provided.·The task planning component of "Ke Jia" is accomplished, which allows it to finish complex tasks and to do causal reasoning. The dissertation designs a simu-lation test to systematically measure the ability of intelligent problem solving for service robots, as far as author's knowledge, there is not any such work currently. The results of the tasks and the simulation test show that, ASP is feasible and convenient for the implement of these cognitive abilities for service robots.For the research on ASP, the dissertation provides some approaches for improving the efficiency of ASP solvers, and applies ASP to implement some cognitive abilities for service robots. On the other hand, the application also provides a platform for testing KR work. Many KR work can be implemented by ASP, based on the system in the dissertation, these work can also be implemented on service robots, thus can be tested by practical requires for robots.