In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log ...In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.展开更多
In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm for solving multiple resource-constrained project scheduling problems. The heuristic solves problems in two phases. In the pre...In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm for solving multiple resource-constrained project scheduling problems. The heuristic solves problems in two phases. In the pre-processing phase, the algorithm estimates distance between a state and the goal state and measures complexity of problem instances. In the search phase, the algorithm uses estimates of the pre-processing phase to further estimate distances to the goal state. The search continues in a stepwise generation of a series of intermediate states through search path evaluation process with backtracking. Developments of intermediate states are exclusively based on a bi-criteria new state selection technique where we consider resource utilization and duration estimate to the goal state. We also propose a variable weighting technique based on initial problem complexity measures. Introducing this technique allows the algorithm to efficiently solve complex project scheduling problems. A numerical example illustrates the algorithm and performance is evaluated by extensive experimentation with various problem parameters. Computational results indicate significance of the algorithm in terms of solution quality and computational performance.展开更多
现有行为识别方法在未能持续覆盖造成视频监控盲区所引起行为数据缺失的情况,难以有效实施特征分析、行为分类补全,无法准确识别出智能体完整的行为动作序列.为此,本文提出一种基于深度学习和智能规划的行为识别方法.首先,利用深度残差...现有行为识别方法在未能持续覆盖造成视频监控盲区所引起行为数据缺失的情况,难以有效实施特征分析、行为分类补全,无法准确识别出智能体完整的行为动作序列.为此,本文提出一种基于深度学习和智能规划的行为识别方法.首先,利用深度残差网络对图像进行分类训练,然后使用递归神经网络对图像特征进行提取深度信息以增强分类效果;其次,运用智能规划的STRIPS(Stanford Research Institute Problem Solver)模型,将深度学习提取的图像特征命题信息转化为规划领域的模型描述文档,并使用前向状态空间搜索规划器推导出完整的行为动作序列.在HMDB51等行为识别公共数据集中,本方法与生成式对抗网络、深度卷积逆向图网络、深度信念网络、支持向量机等同类先进方法相比展现出更好的性能.展开更多
Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm ...Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound （BB） is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.展开更多
Although amazing progress has been made in ma- chine learning to achieve high generalization accuracy and ef- ficiency, there is still very limited work on deriving meaning- ful decision-making actions from the result...Although amazing progress has been made in ma- chine learning to achieve high generalization accuracy and ef- ficiency, there is still very limited work on deriving meaning- ful decision-making actions from the resulting models. How- ever, in many applications such as advertisement, recommen- dation systems, social networks, customer relationship man- agement, and clinical prediction, the users need not only ac- curate prediction, but also suggestions on actions to achieve a desirable goal （e.g., high ads hit rates） or avert an unde- sirable predicted result （e.g., clinical deterioration）. Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract ac- tionable knowledge from additive tree models （ATMs）, one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning （OAP） problem for a given ATM, which is to extract an action- able plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal heuris- tic search method which intends to find an optimal solution. Then, we also present a sub-optimal heuristic search with an admissible and consistent heuristic function which can re- markably improve the efficiency of the algorithm. Our exper- imental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.展开更多
A profound approach about dual arm robot collision free motion planning is made. The method of configuration space is first and successfully applied to the collision free motion planning of dual arm robot, and a n...A profound approach about dual arm robot collision free motion planning is made. The method of configuration space is first and successfully applied to the collision free motion planning of dual arm robot, and a new concept, slave arm collision state graph, is presented. In this algorithm ,the problem of dual arm robot collision free motion planning is reduced to a search in the collision state graph. With this algorithm, a time optimum trajectory would be found, or the condition that there is no feasible solution for the slave arm is proved. A verification of this algorithm is made in the dual arm horizontal articulated robot SCARATES, and the results ascertain that the algorithm is feasible and effective.展开更多
基金This paper was supported by Ph. D. Foundation of State Education Commission of China.
文摘In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.
文摘In this paper we formulate a bi-criteria search strategy of a heuristic learning algorithm for solving multiple resource-constrained project scheduling problems. The heuristic solves problems in two phases. In the pre-processing phase, the algorithm estimates distance between a state and the goal state and measures complexity of problem instances. In the search phase, the algorithm uses estimates of the pre-processing phase to further estimate distances to the goal state. The search continues in a stepwise generation of a series of intermediate states through search path evaluation process with backtracking. Developments of intermediate states are exclusively based on a bi-criteria new state selection technique where we consider resource utilization and duration estimate to the goal state. We also propose a variable weighting technique based on initial problem complexity measures. Introducing this technique allows the algorithm to efficiently solve complex project scheduling problems. A numerical example illustrates the algorithm and performance is evaluated by extensive experimentation with various problem parameters. Computational results indicate significance of the algorithm in terms of solution quality and computational performance.
文摘现有行为识别方法在未能持续覆盖造成视频监控盲区所引起行为数据缺失的情况,难以有效实施特征分析、行为分类补全,无法准确识别出智能体完整的行为动作序列.为此,本文提出一种基于深度学习和智能规划的行为识别方法.首先,利用深度残差网络对图像进行分类训练,然后使用递归神经网络对图像特征进行提取深度信息以增强分类效果;其次,运用智能规划的STRIPS(Stanford Research Institute Problem Solver)模型,将深度学习提取的图像特征命题信息转化为规划领域的模型描述文档,并使用前向状态空间搜索规划器推导出完整的行为动作序列.在HMDB51等行为识别公共数据集中,本方法与生成式对抗网络、深度卷积逆向图网络、深度信念网络、支持向量机等同类先进方法相比展现出更好的性能.
基金supported by the Hi-Tech Research and Development Program of China(2012AA011201)the National Natural Science Foundation of China(61202080)+1 种基金the Major Program of the National Natural Science Foundation of China(91318301)the Open Funding of State Key Laboratory of Computer Architecture(CARCH201201)
文摘Path-oriented test case generation is in essence a constraint satisfaction problem （CSP） solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound （BB） is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms.
基金This work was supported in part by China Postdoctoral Science Foundation （2013M531527）, the Fundamental Research Funds for the Central Universities （0110000037）, the National Natural Science Foun- dation of China （Grant Nos. 61502412, 61033009, and 61175057）, Natural Science Foundation of the Jiangsu Province （BK20150459）, Natural Science Foundation of the Jiangsu Higher Education Institutions （15KJB520036）, National Science Foundation, United States （IIS-0534699, IIS-0713109, CNS-1017701）, and a Microsoft Research New Faculty Fellowship.
文摘Although amazing progress has been made in ma- chine learning to achieve high generalization accuracy and ef- ficiency, there is still very limited work on deriving meaning- ful decision-making actions from the resulting models. How- ever, in many applications such as advertisement, recommen- dation systems, social networks, customer relationship man- agement, and clinical prediction, the users need not only ac- curate prediction, but also suggestions on actions to achieve a desirable goal （e.g., high ads hit rates） or avert an unde- sirable predicted result （e.g., clinical deterioration）. Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract ac- tionable knowledge from additive tree models （ATMs）, one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning （OAP） problem for a given ATM, which is to extract an action- able plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal heuris- tic search method which intends to find an optimal solution. Then, we also present a sub-optimal heuristic search with an admissible and consistent heuristic function which can re- markably improve the efficiency of the algorithm. Our exper- imental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.
文摘A profound approach about dual arm robot collision free motion planning is made. The method of configuration space is first and successfully applied to the collision free motion planning of dual arm robot, and a new concept, slave arm collision state graph, is presented. In this algorithm ,the problem of dual arm robot collision free motion planning is reduced to a search in the collision state graph. With this algorithm, a time optimum trajectory would be found, or the condition that there is no feasible solution for the slave arm is proved. A verification of this algorithm is made in the dual arm horizontal articulated robot SCARATES, and the results ascertain that the algorithm is feasible and effective.
