Non-monotonic Theory And Implementation For Hierarchical Task Planning Of Intelligent Service Robots

Compared to the classical logic (propositional or first-order), in non-monotonic reasoning, adding new knowledge may result in the change of the consequence of the system. In the representation and reasoning systems of service robots, due to the limita-tions of the hardware and perception systems, the model of the environements is often not complete. Thus we must make assumptions that the enviromnents are not abnor-mal, and the reasoning is "in common conditions". When the environment changes, such assumptions no longer hold, the consequences obtained in the origional system may not hold either. The problems can be conveniently handled by non-monotonic rea-soning systems, and such systems, to some extent, satisfy the requirement of elaboration tolerance.Action languages are formal models of parts of the natural language that are used for representing the change and reasoning about actions. The semantics of the action language is defined formally on the transition systems represented by the action de-scription. With the developments of the theory for many years, the action language C+, can be used to represent the multi-value action signature, the concurrency execution of actions, the non-determined execution of actions, and the inertia property of the fluents, etc, which employs a powerful expressivty of the language. Meanwhile, with the de-velopment of C+, to employ it to real-life projects is promising. On the other hand, in the domain of robot task planning, the representation and reasoning should meet the requirements of "elaboration tolerance", thus a logic system with a non-monotonic se-mantics is needed. Action language C+, which is based on the non-monotonic causal theory, is a suitable candidate for robot task planning.In obottask planning, using primitive actions which are decided by the hardware and the perception systems of the robots directly is complicated and not intuitive. An action description by introducing the composition of a series of the primitive actions is more intuitive and efficient which shorten the length of the plan.This thesis studies three research issues:First, we extend the action language C+by introducing composite actions formally. Composite actions, in intuition, are exe-cutions of other actions in some conditions. Based on the definition of the composite actions, we discuss the semantics of the extended language in detail by relating the ac-tion description with its transition systems. Some properties of the new languages are explored, and finally, the soundness and completeness of the new language are proved. These properties assure that the validation of composite actions.Second, the solving system of C+, cplus2asp, is extended to support composite ac-tions. Thus, we can apply the system to the task planning module of a service robot. By an instance of the robot KeJia’s domain, we have tested the formalization and efficiency of the new language, and the results show that for large-scale domains, the efficiency is improved.Third, according to the general architecture of a service robot, we discuss the im-plementation of the system by introducing a task planning module represented by action language C+in detail. A technique to knowledge acquirement and the modular descrip-tion of the actions is also proposed.The main contributions are as follows:First, based on the action language C+, we introduce a formal definition of com-posite actions, which extends the expressivity of C+. The concept like composite action can not be described in the origional C+. The composite actions, which are used to ex-press "high-level actions" is intuitive. On the other hand, previous works include the representation of some structures like composite actions, but there are many limitations, such as there is no conditional execution or no nested execution of the actions. Such composite actions are less expressitive and are not suitable for certain domains.Second, we prove that the extension of the action language C+by composite ac-tions is sound and complete with respect to the original C+, which gives a solid foun-dation to applications based on C+. The experiments show that, the knowledge about composite actions can be added to the action descriptions incrementally, i.e. without any modification about the original desriotion. And, the efficiency of solving the prob-lems is improved greatly with the knowledge about the composite actions. In previous works about structures like composite actions, there are no theoretical results about the soundness and completeness.Third, to the problem of re-usable and modular knowledge about the planning sys-tem, we propose an elegant and consistent solution to the knowledge acquisition prob-lem based on the extended action language C+. In recent years, research effects about knowledge acquisition need a hard-coded structure and algorithm to realize the acqui-sition and storage of the knowledge.The thesis firstly studies the theoretical extension of the action language C+, then discusses an instance using the extended action languages, and implements a prototype of the task planning system of the service robots. On the other hand, we only consider a small fragment of the language C+, and we also make an assumption about the syntax of C+in extening the composite actions. How to implement a more expressive and usable system about composite actions is a promissing issue in the future.