Data publikacji: 15 mar 2024
Zakres stron: 1 - 9
DOI: https://doi.org/10.2478/ijanmc-2023-0061
Słowa kluczowe
© 2023 Chongtian Feng et al., published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Intelligent planning is a research field with strong application in the field of artificial intelligence, which is widely used in practical problems such as industrial task scheduling and mechanical manufacturing planning. For practical problems, developing a domain-specific planner is the main goal of improving planning efficiency, and a general domain-independent planner is the ultimate goal of researchers.
In the field of intelligent planning, some mature planning methods have been proposed, and a planner with good performance has been designed according to this method, which has successfully solved some planning problems. In the International Intelligent Planning Contest (IPC), more efficient planners are constantly emerging. The following is a list and analysis of the current mainstream intelligent planning methods.
At present, the academic community divides intelligent planning into two categories: classical intelligent planning and non-classical intelligent planning. Classical planning only refers to: Agent knowledge of the planning world is complete planning process action effect is determined at each time step can only perform one action [5]. Non-classical intelligent planning refers to: Compared with classical planning, non-classical planning refers to planning that is carried out in an environment that is partially observable or random, considers time and resources, and relaxes other constraints. Many planning methods are proposed for two intelligent planning problems.
The classical methods in the field of intelligent planning mainly include state space planning method and planning space planning method.
The state space planning method regards the planning solution process of the problem as a state transition. The prime minister of the method regards the initial state of the problem as the current state, and selects a certain operator for application to obtain a new state. If the target state appears, the planning ends. If not, the current state is updated according to a certain search strategy to repeat the above actions. The search strategies applied when planning fails mainly include depth-first search, breadth-first search and A * search algorithm. The first two search algorithms are called uninformative search algorithms, that is, search according to a specified order during the search process. For example, depth-first search searches according to the maximum depth of the search tree. If the search is completed, the planning ends. If the deepest node state is not the target state, the previous node is backtracked for re-search. The A * search algorithm adds a search algorithm for guiding information. The guiding information is a defined evaluation function:
Where
In the planning space planning, the planner searches the planning space, and the planning is defined as a set of planning operations with a certain order and bound by variables, which does not necessarily correspond to an action sequence [6].
Graph planning is to introduce the graph structure into the planning process. Based on the planning graph, the planning graph is composed of two nodes and three edges. The two nodes refer to the proposition node and the action node, and the three edges refer to the precondition edge, add effect edge and delete effect edge [7].
The problem conditions solved by non-classical programming are often more relaxed than those of classical intelligent programming, such as the planning problem with uncertain initial state and action results. Such planning is called uncertain planning. For example, heuristic planning makes some assumptions and simplification constraints on the original planning to obtain a simpler problem. In non-classical planning, some new planning methods adapted to specific problems are often proposed based on classical planning methods.
A. Blum and J. Langford proposed the probabilistic planning algorithm PGraphplan [8] based on the planning graph. The algorithm includes two stages, plan graph expansion and effective plan extraction. The probabilistic planning algorithm solves the uncertainty planning, that is, the result of the action is uncertain. The probability is used to represent the uncertainty, and the result of the action has its probability. In 2003, The Duy Bui and Wojciech Jamroga of the University of Twente in the Netherlands extended the planning graph to deal with multi-agent planning [9]. They defined three kinds of agent relationships: cooperative relationship, antagonistic relationship and independent relationship, and proposed corresponding algorithms for the planning between the three agents.
The heuristic planning uses the search strategy to realize the planning, and uses different heuristic strategies to guide the search direction in the planning process. The current heuristic strategy has HSP planner, which calculates the planning cost by accumulating the heuristic value in the planning process, while the FF planner uses the enhanced hill climbing algorithm to optimize the planning cost, and finally realizes the optimal planning.
Classical intelligent planning believes that all information is known and there will be no unexpected situations. Therefore, planning is regarded as a transition between states, so the planning process is a process of searching for the target state among many states. Classical intelligent planning requires that every link in the planning process is determined. Therefore, classical intelligent planning is often harsh in planning conditions. For example, it is necessary to ensure the uniqueness of action results. However, there may be many consequences of actions in the real world. In fact, the results may be different according to the probability. Therefore, non-classical intelligent planning is developed on the basis of classical intelligent planning. So far, classical intelligent planning and non-classical intelligent planning can solve most practical problems. Although its planning effect is good, the whole planning process from the definition of intelligence does not reflect the characteristics of intelligence. Therefore, on the basis of the existing intelligent planning algorithm, it is necessary to combine intelligent research to further propose a planning that can use intelligent theory.
The existing intelligent planning has a great relationship with the problem itself. The information contained in the planning problem is extracted and input into the existing algorithm flow, and finally the planning result is given. A relatively complete agent often needs to know the knowledge of multiple fields. When the agent solves the problems in different fields, it needs to process different domain knowledge. At present, there is no unified organization form for different domain knowledge, which leads to the need for the agent to manually participate in the preprocessing when dealing with multi-domain planning problems. Through in-depth analysis of the nature of intelligence and the representation of knowledge, AORBCO model gives a relatively unified knowledge representation and knowledge organization form. Therefore, the development of intelligent planning system based on AORBCO model is a reasonable way to develop general intelligent planning system.
The ultimate goal of artificial intelligence is to make the machine have human intelligence. At present, the research of artificial intelligence does not have a deep discussion and understanding of human intelligence. The current artificial intelligence only makes the computer have ‘look’ intelligence, that is, the existing artificial intelligence is human: the intelligent performance of program algorithm developers. Developers summarize the steps and methods to solve the problem, and input them into the computer (program) in the form that the computer can recognize, and drive the computer to carry out intelligent activities. Therefore, the existing artificial intelligence is a weak artificial intelligence that performs well. Intelligent planning is an early-developed branch of artificial intelligence, which wants to embody intelligence in the planning process. At present, the more recognized definition of intelligent planning is as follows : to understand and analyze the surrounding environment, according to the predetermined goal, to reason about a number of alternative actions and the resource constraints and related constraints provided, and to comprehensively formulate the action sequence to achieve the goal. This sequence of actions is called a plan. The intelligence that can only be planned is mainly reflected in the complexity of the planning algorithm to deal with the problem, the processing efficiency, and whether it is optimal. This is only to evaluate the intelligence of the planning from the results of the problem, but the algorithm itself is a summary of the public planning.
Therefore, it is essential to discuss what intelligence is in order to design an intelligent planning framework.
The AORBCO model believes that knowledge is the understanding and description of ‘knowledge’. And people’s knowledge is divided into eight knowledge: eye knowledge, ear knowledge, nose knowledge, tongue knowledge, body knowledge, consciousness, the last knowledge, Alafia knowledge. Through the eight senses, the information in the real world is received, understood and called, so as to carry out intelligent activities. In the literature [10], through in-depth analysis and research on what intelligence is, through the study of general psychology, reflective psychology, cognitive psychology and consciousness-only psychology, the four characteristics of intelligence are pointed out, and the four major knowledge components in the AORBCO model are studied. It is considered that knowledge is the understanding and description of “knowledge.” Only with knowledge can intelligence be shown. We believe that intelligence and knowledge are actually equivalent.
Therefore, the intelligent planning of agent should be based on agent intelligence, that is, intelligent planning is based on knowledge. Combined with the intelligent theory of AORBCO model, the definition of intelligent planning based on self-consciousness is given: agent takes its own knowledge as the planning basis, and calls knowledge under the action of behavior control mechanism to give the knowledge sequence that agent can call in turn to solve the problem.
By studying the existing intelligent planning algorithm, the overall framework of intelligent planning based on self-consciousness is given under the knowledge system of AORBCO model.
Figure 1.
System framework diagram
The above figure shows the overall framework of the planning system based on the AORBCO model. The overall framework consists of six parts: domain knowledge base, user GUI, planning domain matcher, planning problem generator, general planning period and planning result interpreter.
The domain knowledge base is an agent’s initialized knowledge stored in a non-relational database composed of nodes and relationships. The AORBCO model believes that domain knowledge is the result of Ego’s abstraction of the real world, so there is more than one domain knowledge base for Ego;
User GUI: The user and system interaction interface, where the user can enter the problem to be solved into the system in a form that the user can understand.
Planning problem generator: It is the generation component of planning problem and the intermediate component of domain location. It has two main functions: convert the problem input by the user into an XML description format that the system can recognize, integrate it into the initial XML description of Ego, and then convert the XML format problem description file into a runnable pddl problem description file; extract key domain information from the problem.
Planning domain matcher: It is used to locate the components of the problem domain. After the planning problem generator obtains the key information of the domain, it locates the domain of the problem in many domain knowledge bases through the domain matcher, obtains the domain knowledge related to the problem and generates the domain PDDL file.
General planner: General planner is the core of the intelligent planning system based on self-awareness. The planning algorithm of the general planning period is not aimed at a specific domain knowledge. The core idea is: Based on the Ego knowledge organization form and storage form, the existing heuristic planning ideas are used to plan the problem. Because the knowledge organization form of Ego is fixed, that is, all domain knowledge is the same organizational structure, and the knowledge structure is universal, the planning algorithm on this basis also has domain versatility. When the user enters the problem, because the problem itself has domain characteristics, the problem description file and domain knowledge file are needed to solve the specific problem.
Planning result interpreter: It is a part of processing planning results. The planning result interpreter has two functions: the first is to return the obtained action sequence to the user through the packaging display on the GUI; the second is to extract the obtained action sequence into strategic knowledge and store it in the knowledge base.
The design and implementation of the general planner is the core of the intelligent planning system based on self-consciousness. Based on the knowledge representation method of AORBCO model, the general planner is designed and implemented by referring to the idea of A-start algorithm. From the perspective of the agent in the AORBCO model, based on the idea of one person and one world, the general planning idea of the agent is as follows: After understanding the problem input and determining the domain to which the problem belongs, the agent first searches for related capabilities from the knowledge base. The correlation of capabilities is related to the representation and storage of capabilities in the knowledge base, and the emotion of the agent to the related capabilities during the search process will also affect the search results, which is the process of the agent’s active matching capability. Another process is the agent’s simulation of the action. The agent will simulate the ability to search. The ability to call will change the agent’s current desire, that is, the state change of the ability object. The agent obtains the new state of the object through state reasoning. The gap between the new state and the target state is used as part of the agent’s assessment of whether to select the ability. The design structure of general planner based on knowledge organization is as follows:
Figure 2.
Basic Planner Data Flow Diagram
This figure shows the transfer of data flow in the basic planning period. It can be seen that the original data is a pddl file and related domain knowledge. The initial state and target state are obtained according to the pddl file. First, it is sent to the capability searcher, and then selected the qualified capability through constraint matching. This capability is simulated, and the description of related topics after the simulation is state reasoned, Calculate the similarity between the target state and obtain the confidence level of the ability
The universality of the general planning period is mainly reflected in 1. The general field of the AORBCO model is only the representation. By analyzing the characteristics of AORBCO model and comparing the existing knowledge representation methods, the knowledge representation method based on AORBCO model is given in [11]. The descriptive representation framework of domain knowledge is given by XML markup language, and the general planner structure is designed based on this framework. The structure of the problem description file of different problems is consistent, and the domain knowledge representation structure of different fields is unified to design a general planner. The planning results can be integrated with the existing knowledge in the knowledge base and can solve other related problems. The following describes each part of the above figure.
The main function of the ability searcher is to search and match the current state of the object in the description of the problem based on the pre-condition, post-condition and ability object in the domain knowledge base on the domain knowledge of the AROBCO model and the planning problem. The pre-post conditions of the ability in the AROBCO model are described by logical expressions. The constraint matching algorithm is used to match the pre-post conditions of the current state and ability of the object in the description of the problem, and the corresponding matching degree is calculated.
The action simulator is the result of the agent’s ability according to the post-condition of the ability, that is, the action result described by the logical expression is related to the problem object, and the logical expression is applied to the object to observe the change of the object.
The state inference engine is the part of the agent to identify the current state of the object. When the agent simulates the ability, the state and attributes of the object may change. These changes may be close to the target state or far away from the target state. Therefore, the agent after the action simulation needs to understand and reason the current state attributes of the object to obtain a new state, and calculate the gap between the new state and the target state. After obtaining the gap between states and the ability matching degree, the confidence of the agent to the ability is obtained. The higher the confidence, the higher the possibility that the agent chooses the ability as part of the planning sequence, and vice versa.
The ability set obtained in the ability searcher is selected according to the confidence level. The degree of confidence will feed back to the emotional knowledge of the agent. The lower the ability to perform, the less the ability to solve the problem, so the agent’s emotional weight is reduced accordingly.
Based on the above structure, there are three main algorithms involved in the general planner: object attribute and capability constraint matching algorithm, state similarity calculation algorithm and heuristic value (confidence) calculation algorithm. The following three algorithms are described:
Figure 3 shows the flowchart of the object capability constraint matching algorithm: The object attribute and capability constraint matching algorithm is mainly used to reduce the set of planning capabilities. The agent first determines whether the subject of the problem is the same as the capability topic through the entity alignment algorithm. Under the premise of the same subject, the knowledge reasoning technology is used to reason about the precondition of the capability. Calculate whether the precondition of the capability is semantically consistent with the current state of the object. After the above process, the object-capability matching degree is calculated by combining the emotional weight of the agent to the current capability.
Figure 3.
Constraint matching algorithm flowchart
Figure 4.
Flow Chart of State Similarity Calculation
This figure shows the flow chart of state similarity calculation: when the ability matching calculation is completed, the agent performs action simulation on the object according to the pre-condition and post-condition of the ability. Specifically, it refers to the reasoning of the state attributes of the object according to the post-condition description of the ability. After reasoning, a new expected state will be obtained. At this time, the state similarity calculation algorithm is used to calculate the gap between the expected state and the target state. The state similarity calculation mainly uses the cosine similarity to calculate the gap between the current object state and the target state.
Ability confidence algorithm: Based on the idea of A * algorithm, the confidence of ability is mainly composed of constraint matching value and state similarity. The higher the confidence is, the closer the ability is to the target state and the farther it is. The A * algorithm is mainly composed of the initial cost and the estimated cost. In the AORBCO model, the agent has self-consciousness, and the emotional weight factor of the agent’s ability is added when selecting the ability. Therefore, the emotional factor of the agent and the ability constraint matching value jointly generate the initial preference (the initial cost in A * ), and the state similarity as the estimated heuristic value constitutes another part of the heuristic function.
Because the inference engine is the main component of the agent to update its own state, attributes and relationships, the inference engine in intelligent planning is described again. After the ability simulation of the agent, some characteristics of the object change. The change of the object characteristics means that the state of the object also changes. Therefore, it is necessary to redetermine the state of the object by analyzing and comparing the object characteristics, which is the main task of the state reasoning module.
This paper adopts rule-based reasoning strategy and uses Java rule engine technology to realize object state reasoning. Rule inference engine, also known as production system, is developed from rule-based expert system. Rule-based expert system is a branch of expert system in the field of artificial intelligence. It simulates human reasoning, uses tentative methods for reasoning, and uses human understandable terms to explain and prove its reasoning conclusions.
In the AORBCO model, the agent is an agent with reasoning ability, and the reasoning ability of the agent is mainly reflected in its knowledge organization and behavior control mechanism. The reasoning process of agent is based on knowledge and strategy, and the behavior control mechanism controls the whole process of reasoning.
The reasoning process of agent is based on rich knowledge base and scientific knowledge organization. In AORBCO model, ego knowledge is divided into descriptive knowledge, process knowledge, strategic knowledge and emotional knowledge. Descriptive knowledge is a description that represents the abstract knowledge of the real world and is used to represent the question of ‘what’ ; process knowledge is the ability of agent to operate knowledge and have specific functions. Strategic knowledge is the action plan obtained by ego after matching descriptive knowledge, and its core logic is if… else… matching mechanism; emotional knowledge is the knowledge of value judgment on the state of the world.
Figure 5 shows the workflow diagram of the state inference engine in the AORBCO model: the inference controller of the agent is mainly composed of four modules, which are condition matchers; a similarity calculator; trigger and actuator. Condition matcher : compare facts and rules by comparing facts and rules, matching rules that meet the conditions, agents compare facts and rules from factors such as domain, object, object type, and object number ; similarity Calculator : There may be more than one rule matched according to the fact data. All the matched rules need to calculate the similarity between the behavior results in the rules and the target state. Trigger: The trigger maintains an ordered list, and the similarity of all matched rules is saved in the list. The trigger selects the rule with the highest similarity and hands the rule to the actuator; actuator: The actual and rules are given to the actuator, which executes the rules and changes the current desire and object.
Figure 5.
State inference structure diagram
Drools is an open source rule engine written in Java language, which uses Rete algorithm to evaluate the written rules. The rule writing format in Drools is:
rule “ruleName” when $message:Message(status == 0) then System.out.println(“fit”); $message.setStatus(1); update($message); end
By analyzing the intelligence and planning principles of the existing intelligent planning methods, the definition of intelligent planning based on self-consciousness is studied on the basis of AORBCO model intelligence theory. At the same time, the overall architecture of intelligent planning based on self-consciousness is given based on AORBCO model. The general planner is designed and implemented, and the planning algorithm in the general planner is designed by referring to the idea of A * algorithm. Although the existing intelligent planning algorithm can plan most of the problems, the algorithm itself does not reflect the intelligence and autonomy of the agent. The intelligent planning based on self-consciousness is a knowledge-based planning algorithm. The AORBCO model proposes the behavior control mechanism of the agent. The behavior control mechanism reflects the autonomy of the agent, and the knowledge participates in the behavior control mechanism to reflect the intelligence of the planning.