Research On Human Information Driven Technologies In Planning And Search

Traditional planning and searching techniques are in broad use in many areas,such as space telescope scheduling and routing.But with the development of the current IT technologies(e.g.,Internet technology and AI technology),new requirements are set for planning and searching,especially the requirement of addressing complex planning problems and implementing efficient searching with the use of human information.These requirements have been critical issues in many emerging application scenarios(in this dissertation,instant or historical information data generated by diverse human activities and behaviors is collectively referred to as “human information”,which includes user account information,participants' voting information,executors' decision-making information,etc.).Many all-purpose models,algorithms and the relevant theories are used in traditional planning and searching areas,without being combined well with human information.This dissertation focuses on how to introduce the right types of human information into specific planning and searching approaches,driving them by human information to make the relevant models and the algorithms become more accurate and more efficient,and better cope with human demands for many practical applications.The specific research contents in this dissertation are: historical voting information advanced Partially Observable Markov Decision Process(POMDP),feedback information based Transfer Learning,account information assisted network searching technology,and experience information guided Procedural Content Generation(PCG)technology.The details are as follows.1)It is often required to collect relevant information in some crowdsourcing application scenarios.In these scenarios,planning for the best time to stop information gathering is a major issue.Many existing studies designed planning approaches based on POMDPs.However,due to the uncertain environment of information gathering,measures like Machine Learning(ML)are often used to train a part of parameters in a POMDP for efficient planning.This dissertation further improve the POMDP models for planning for voting information gathering from two aspects: first,single-step planning for collecting units of information is often used for crowdsourcing tasks.Because each single unit of information contains weak evidence,this kind of planning method is inefficient when being used to collect long evidential sequences of information.In this dissertation,a new multistep planning method is proposed for enhancing efficiency.Second,setting reasonable asking strategies in planning that is based on POMDPs can increase evidence in collected information.This dissertation considers adjusting an asking strategy in a POMDP planning,and before each round of multistep collecting,the asking strategy is dynamically adjusted based on the actual characteristics of the corresponding crowdsourcing task.Therefore participants can provide more accurate and more evidential information during answering the questions.These dynamically adjusted asking strategies can accelerate the information gathering process and help do more intelligent planning.Experiments have verified that the multistep collection planning approach is superior to the single-step one particularly in terms of runtime,and compared to the existing multistep ones(e.g.,Limited Lookahead algorithms,LLA),the proposed approach performs better in saving the cost of information gathering and enhancing the efficiency of it.2)Simulators train policies and then send them to the real world,but there is a gap between the two worlds,making the transferred policies do not have their intended effects,and in extreme cases,incurring costly damage that is unacceptable by human beings.Therefore,transfer learning learned on feedback information is of some research significance.Existing studies often used statistical analysis to determine blind spots,which are unknown error states in the real world caused by the limitations of the simulation.Although these studies have developed methods based on the feedback information,but them have simply replaced the policies causing blind spots with the ones learned from the information.In this dissertation,simulators adopt the SADPP algorithm to obtain policies from the simulated environment and the real-world environment is built into a Markov Decision Process(MDP).This dissertation proposes an approach to using decision tree methods(specifically based on the Dawid-Skene algorithm and the C4.5 algorithm)to divide blind spots,according to the sampled human feedback.Finally,this dissertation designs a complementary model defined on the blind spots,and through this model and a proposed FRU-SADPP algorithm,the transferred policies are fixed.Experiments tested on two games,Catcher and Monster Kong,available in Py Game Learning Environment have verified the accuracy and the scalability of the proposed approach used to fix transferred policies.3)Many applications need to deal with dense subgraph mining problems on graphs.This kind of problems has always been a critical research site in data mining.In the applications of social network or commercial network,there are manually reported fraud user IDs or product IDs.For further detection of the fraud rings involved with these IDs,the technology of local densest subgraph mining is needed.Aiming at the scenario,this dissertation investigates the ID information assisted subgraph mining technology,mining the involved fraud rings on networks.This technology models the task of searching the fraud rings as a local subgraph mining problem,which is to find a maximum density subgraph near or containing a given node in an undirected(unipartite or bipartite)graph,and the given node is determined by the manually reported ID information.Compared to existing studies,an important improvement in this dissertation is measuring the density of a subgraph by its average degree,and two local dense subgraph finding algorithms Slither and Slither PR are proposed.Experiments on both unipartite and bipartite graphs have verified that,compared to other local dense subgraph finding algorithms(Find Dense,Hi DDen and HPR),the proposed algorithms improve the densities of the found subgraphs and the adaptability and scalability of this kind of algorithms to some extent.A fraud detection test was conducted on a large real-world social network Twitter.The results of this test have showed the effectiveness of the proposed method.4)PCG technology is commonly used in game level design.Current PCG technology is mainly developed to produce game levels solely on machines,and the produced levels are often lacking in interest and difficulty.To solve this issue,frequently used approaches are based on the statistical analysis of existing levels,but being of little effect.This dissertation investigates an experience guided PCG technology.Compared to existing studies,this technology is developed from the idea of modeling the experience information of level designers as levels' outlines(inspired by the idea of reverse design),and guided by the levels' outlines,it searches the optimal solutions as specific levels with the use of a multi-objective genetic algorithm(NSGA-II).The algorithm defines the levels' interest and difficulty as the optimization objectives,thus overcoming the shortage of capabilities of existing approaches to maintain the interest and the difficulty of the populations of levels.Experiments have verified the effectiveness of the proposed PCG technology by analyzing the diversity(in interest)and the complexity(in difficulty)of the solutions,evaluated by specific game solvers.