Traditional models for project management have not adequately incorporated a number of factors that are important for resource allocation. This paper proposed a unified timed Petri net model in which scheduling and pl...Traditional models for project management have not adequately incorporated a number of factors that are important for resource allocation. This paper proposed a unified timed Petri net model in which scheduling and planning were collectively carried out to take full advantages of the flexibility of the FMS. Through the lens of system theory, two types of resources were distinguished: major role and auxiliary role, and the major role was used to construct the FMS' Petri net. The method simplified the Petri net's construction and gave a clear flow chart for scheduling. Hence, the auxiliary resource allocation could be easily carried out according to the schedule, which was proposed by heuristic search algorithm. At last, the efficacy of the Petri net model for online scheduling in a resource constrained environment was discussed.展开更多
This paper proposes and evaluates two improved Petri net （PN）-based hybrid search strategies and their applications to flexible manufacturing system （FMS） scheduling. The algorithms proposed in some previous paper...This paper proposes and evaluates two improved Petri net （PN）-based hybrid search strategies and their applications to flexible manufacturing system （FMS） scheduling. The algorithms proposed in some previous papers, which combine PN simulation capabilities with A＊ heuristic search within the PN reachability graph,may not find an optimum solution even with an admissible heuristic function. To remedy the defects an improved heuristic search strategy is proposed, which adopts a different method for selecting the promising markings and reserves the admissibility of the algorithm. To speed up the search process, another algorithm is also proposed which invokes faster termination conditions and still guarantees that the solution found is optimum. The scheduling results are compared through a simple FMS between our algorithms and the previous methods. They are also applied and evaluated in a set of randomly-generated FMSs with such characteristics as multiple resources and alternative routes.展开更多
In the present paper we introduce new heuristic methods for the state minimization of nondeterministic finite automata. These methods are based on the classical Kameda-Weiner algorithm joined with local search heurist...In the present paper we introduce new heuristic methods for the state minimization of nondeterministic finite automata. These methods are based on the classical Kameda-Weiner algorithm joined with local search heuristics, such as stochastic hill climbing and simulated annealing. The description of the proposed methods is given and the results of the numerical experiments are provided.展开更多
Nesting is a common problem in industries such as shipbuilding, auto-maker, clothing, shoe-making, and furniture, in which various parts are cut off from a stock or stocks while minimizing the wastes or maximizing the...Nesting is a common problem in industries such as shipbuilding, auto-maker, clothing, shoe-making, and furniture, in which various parts are cut off from a stock or stocks while minimizing the wastes or maximizing the utilization of the stock. Berth allocation at seaside is also considered one form of two dimensional nesting problems, in which a ship is assigned a location for service during a certain time slot. This paper presents an expert system using a heuristic search method for nesting problems. The parts and stocks are represented by pixels with which utility function is used to evaluate current state in search tree. The system is developed in CLIPS, an expert system shell and applied to various example problems with different constraints and to a berth allocation example to illustrate its applicability under different conditions.展开更多
Software reverse engineering and reengineering techniques are most often applied to reconstruct the software archi-tecture with respect to quality constraints, or non-functional requirements such as maintainability or...Software reverse engineering and reengineering techniques are most often applied to reconstruct the software archi-tecture with respect to quality constraints, or non-functional requirements such as maintainability or reusability. In this paper, the performance improvement of distributed software is modeled as a search problem that is solved by heuristic search algorithms such as genetic search methods. To achieve this, firstly, all aspects of the distributed execution of a software is specified by an analytical performance evaluation function that not only evaluates the current deployment of the software from the performance perspective but also can be applied to propose the near-optimal object deploy-ment for that software. This analytical function is applied as the Heuristic search objective function. In this paper a novel statement reordering method is also presented which is used to generate the search objective function such that the best solution in the search space can be found.展开更多
This research effort presents an approach to accomplish Multidimensional Scaling (MDS) via the heuristic approach of Simulated Annealing. Multidimensional scaling is an approach used to convert matrix-based similarity...This research effort presents an approach to accomplish Multidimensional Scaling (MDS) via the heuristic approach of Simulated Annealing. Multidimensional scaling is an approach used to convert matrix-based similarity (or dissimilarity data) into spatial form, usually via two or three dimensions. Performing MDS has several important applications—Geographic Information Systems, DNA Sequencing, and Marketing Research are just a few. Traditionally, classical MDS decomposes the similarity or dissimilarity matrix into its eigensystem and uses the eigensystem to calculate spatial coordinates. Here, a heuristic search-based approach is used to find coordinates from a dissimilarity matrix that minimizes a cost function. The proposed methodology is used over a variety of problems. Experimentation shows that the presented methodology consistently outperforms solutions obtained via the classical MDS approach, and this approach can be used for other important applications.展开更多
An agile earth-observing satellite equipped with multimode cameras capable of transmitting observation data to other satellites is developed to rapidly respond to requests with multiple observation modes.This gives ri...An agile earth-observing satellite equipped with multimode cameras capable of transmitting observation data to other satellites is developed to rapidly respond to requests with multiple observation modes.This gives rise to the Multisatellite Multimode Crosslink Scheduling(MMCS)problem,which involves allocating observation requests to agile satellites,selecting appropriate timing and observation modes for the requests,and transmitting the data to the ground station via the satellite communication system.Herein,a mixed integer programming model is introduced to include all complex time and operation constraints.To solve the MMCS problem,a two-stage heuristic method,called Fast insertion Tabu Search with Conflict-avoidance(FTS-C)heuristic,is developed.In the first stage,a conflict-avoidance insertion algorithm is designed to generate a high-quality initial solution by considering the requests transmission and download.Further,the tabu search-based second stage optimizes the initial solution.Finally,an extensive empirical study based on a real-world situation demonstrates that FTS-C can generate a solution with higher quality in less time than other state-of-the-art algorithms and the CPLEX solver.展开更多
针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,JPS)算法不均匀分配初始信息素,降低蚁群前期盲...针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,JPS)算法不均匀分配初始信息素,降低蚁群前期盲目搜索的概率;然后,引入切比雪夫距离加权因子和转弯代价改进启发函数,提高算法的收敛速度、全局路径寻优能力和搜索路径的平滑程度;最后,提出一种新的信息素更新策略,引入自适应奖惩因子,自适应调整迭代前、后期的信息素奖惩因子,保证了算法全局最优收敛。实验仿真结果表明,在不同地图环境下,与现有文献结果对比,该算法可以有效地缩短路径搜索的迭代次数和最优路径长度,并提高路径的平滑程度。展开更多
目前深度强化学习算法在不同应用领域中已经取得诸多成果,然而在多智能体任务领域中,往往面临大规模的具有稀疏奖励的非稳态环境,低探索效率问题仍是一大挑战。由于智能规划能够根据任务的初始状态和目标状态快速制定出决策方案,该方案...目前深度强化学习算法在不同应用领域中已经取得诸多成果,然而在多智能体任务领域中,往往面临大规模的具有稀疏奖励的非稳态环境,低探索效率问题仍是一大挑战。由于智能规划能够根据任务的初始状态和目标状态快速制定出决策方案,该方案能够作为各智能体的初始策略,并为其探索过程提供有效指导,因此尝试将智能规划与多智能体强化学习进行结合求解,并且提出统一模型UniMP(a Unified model for Multi-agent Reinforcement Learning and AI Planning)。在此基础上,设计并建立相应的问题求解机制。首先,将多智能体强化学习任务转化为智能决策任务;其次,对其执行启发式搜索,以得到一组宏观目标,进而指导强化学习的训练,使得各智能体能够进行更加高效的探索。在多智能体即时战略对抗场景StarCraftⅡ的各地图以及RMAICS战车模拟对战环境下进行实验,结果表明累计奖励值和胜率均有显著提升,从而验证了统一模型的可行性、求解机制的有效性以及所提算法灵活应对强化学习环境突发情况的能力。展开更多
文摘Traditional models for project management have not adequately incorporated a number of factors that are important for resource allocation. This paper proposed a unified timed Petri net model in which scheduling and planning were collectively carried out to take full advantages of the flexibility of the FMS. Through the lens of system theory, two types of resources were distinguished: major role and auxiliary role, and the major role was used to construct the FMS' Petri net. The method simplified the Petri net's construction and gave a clear flow chart for scheduling. Hence, the auxiliary resource allocation could be easily carried out according to the schedule, which was proposed by heuristic search algorithm. At last, the efficacy of the Petri net model for online scheduling in a resource constrained environment was discussed.
文摘This paper proposes and evaluates two improved Petri net （PN）-based hybrid search strategies and their applications to flexible manufacturing system （FMS） scheduling. The algorithms proposed in some previous papers, which combine PN simulation capabilities with A＊ heuristic search within the PN reachability graph,may not find an optimum solution even with an admissible heuristic function. To remedy the defects an improved heuristic search strategy is proposed, which adopts a different method for selecting the promising markings and reserves the admissibility of the algorithm. To speed up the search process, another algorithm is also proposed which invokes faster termination conditions and still guarantees that the solution found is optimum. The scheduling results are compared through a simple FMS between our algorithms and the previous methods. They are also applied and evaluated in a set of randomly-generated FMSs with such characteristics as multiple resources and alternative routes.
文摘In the present paper we introduce new heuristic methods for the state minimization of nondeterministic finite automata. These methods are based on the classical Kameda-Weiner algorithm joined with local search heuristics, such as stochastic hill climbing and simulated annealing. The description of the proposed methods is given and the results of the numerical experiments are provided.
文摘Nesting is a common problem in industries such as shipbuilding, auto-maker, clothing, shoe-making, and furniture, in which various parts are cut off from a stock or stocks while minimizing the wastes or maximizing the utilization of the stock. Berth allocation at seaside is also considered one form of two dimensional nesting problems, in which a ship is assigned a location for service during a certain time slot. This paper presents an expert system using a heuristic search method for nesting problems. The parts and stocks are represented by pixels with which utility function is used to evaluate current state in search tree. The system is developed in CLIPS, an expert system shell and applied to various example problems with different constraints and to a berth allocation example to illustrate its applicability under different conditions.
文摘Software reverse engineering and reengineering techniques are most often applied to reconstruct the software archi-tecture with respect to quality constraints, or non-functional requirements such as maintainability or reusability. In this paper, the performance improvement of distributed software is modeled as a search problem that is solved by heuristic search algorithms such as genetic search methods. To achieve this, firstly, all aspects of the distributed execution of a software is specified by an analytical performance evaluation function that not only evaluates the current deployment of the software from the performance perspective but also can be applied to propose the near-optimal object deploy-ment for that software. This analytical function is applied as the Heuristic search objective function. In this paper a novel statement reordering method is also presented which is used to generate the search objective function such that the best solution in the search space can be found.
文摘This research effort presents an approach to accomplish Multidimensional Scaling (MDS) via the heuristic approach of Simulated Annealing. Multidimensional scaling is an approach used to convert matrix-based similarity (or dissimilarity data) into spatial form, usually via two or three dimensions. Performing MDS has several important applications—Geographic Information Systems, DNA Sequencing, and Marketing Research are just a few. Traditionally, classical MDS decomposes the similarity or dissimilarity matrix into its eigensystem and uses the eigensystem to calculate spatial coordinates. Here, a heuristic search-based approach is used to find coordinates from a dissimilarity matrix that minimizes a cost function. The proposed methodology is used over a variety of problems. Experimentation shows that the presented methodology consistently outperforms solutions obtained via the classical MDS approach, and this approach can be used for other important applications.
基金supported by the National Natural Science Foundation of China(No.72001212)the Hunan Provincial Innovation Foundation for Postgraduate(No.CX20200022).
文摘An agile earth-observing satellite equipped with multimode cameras capable of transmitting observation data to other satellites is developed to rapidly respond to requests with multiple observation modes.This gives rise to the Multisatellite Multimode Crosslink Scheduling(MMCS)problem,which involves allocating observation requests to agile satellites,selecting appropriate timing and observation modes for the requests,and transmitting the data to the ground station via the satellite communication system.Herein,a mixed integer programming model is introduced to include all complex time and operation constraints.To solve the MMCS problem,a two-stage heuristic method,called Fast insertion Tabu Search with Conflict-avoidance(FTS-C)heuristic,is developed.In the first stage,a conflict-avoidance insertion algorithm is designed to generate a high-quality initial solution by considering the requests transmission and download.Further,the tabu search-based second stage optimizes the initial solution.Finally,an extensive empirical study based on a real-world situation demonstrates that FTS-C can generate a solution with higher quality in less time than other state-of-the-art algorithms and the CPLEX solver.
文摘针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,JPS)算法不均匀分配初始信息素,降低蚁群前期盲目搜索的概率;然后,引入切比雪夫距离加权因子和转弯代价改进启发函数,提高算法的收敛速度、全局路径寻优能力和搜索路径的平滑程度;最后,提出一种新的信息素更新策略,引入自适应奖惩因子,自适应调整迭代前、后期的信息素奖惩因子,保证了算法全局最优收敛。实验仿真结果表明,在不同地图环境下,与现有文献结果对比,该算法可以有效地缩短路径搜索的迭代次数和最优路径长度,并提高路径的平滑程度。
文摘目前深度强化学习算法在不同应用领域中已经取得诸多成果,然而在多智能体任务领域中,往往面临大规模的具有稀疏奖励的非稳态环境,低探索效率问题仍是一大挑战。由于智能规划能够根据任务的初始状态和目标状态快速制定出决策方案,该方案能够作为各智能体的初始策略,并为其探索过程提供有效指导,因此尝试将智能规划与多智能体强化学习进行结合求解,并且提出统一模型UniMP(a Unified model for Multi-agent Reinforcement Learning and AI Planning)。在此基础上,设计并建立相应的问题求解机制。首先,将多智能体强化学习任务转化为智能决策任务;其次,对其执行启发式搜索,以得到一组宏观目标,进而指导强化学习的训练,使得各智能体能够进行更加高效的探索。在多智能体即时战略对抗场景StarCraftⅡ的各地图以及RMAICS战车模拟对战环境下进行实验,结果表明累计奖励值和胜率均有显著提升,从而验证了统一模型的可行性、求解机制的有效性以及所提算法灵活应对强化学习环境突发情况的能力。
