A greedy path planning algorithm based on pre-path-planning and real-time-conflict for multiple automated guided vehicles in large-scale outdoor scenarios

With the wide application of automated guided vehicles(AGVs) in large scale outdoor scenarios with complex terrain,the collaborative work of a large number of AGVs becomes the main trend.The effective multi-agent path finding(MAPF) algorithm is urgently needed to ensure the efficiency and realizability of the whole system. The complex terrain of outdoor scenarios is fully considered by using different values of passage cost to quantify different terrain types. The objective of the MAPF problem is to minimize the cost of passage while the Manhattan distance of paths and the time of passage are also evaluated for a comprehensive comparison. The pre-path-planning and real-time-conflict based greedy(PRG) algorithm is proposed as the solution. Simulation is conducted and the proposed PRG algorithm is compared with waiting-stop A^(*) and conflict based search(CBS) algorithms. Results show that the PRG algorithm outperforms the waiting-stop A^(*) algorithm in all three performance indicators,and it is more applicable than the CBS algorithm when a large number of AGVs are working collaboratively with frequent collisions.

Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags

Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem（PFSP with time lags） is concentrated but non-permutation problem（non-PFSP with time lags） seems to be neglected. With the aim to minimize the makespan and satisfy time lag constraints, efficient algo- rithms corresponding to PFSP and non-PFSP problems are proposed, which consist of iterated greedy algorithm for permutation（IGTLP） and iterated greedy algorithm for non-permutation （IGTLNP）. The proposed algorithms are verified using well-known simple and complex instances of permutation and non-permutation problems with various time lag ranges. The permutation results indicate that the proposed IGTLP can reach near optimal solution within nearly 11% computational time of traditional GA approach. The non-permutation results indicate that the proposed IG can reach nearly same solution within less than 1% com- putational time compared with traditional GA approach. The proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.

Using Greedy algorithm： DBSCAN revisited Ⅱ

The density-based clustering algorithm presented is different from the classical Density-Based Spatial Clustering of Applications with Noise (DBSCAN) (Ester et al., 1996), and has the following advantages: first, Greedy algorithm substitutes for R*-tree (Bechmann et al., 1990) in DBSCAN to index the clustering space so that the clustering time cost is decreased to great extent and I/O memory load is reduced as well; second, the merging condition to approach to arbitrary-shaped clusters is designed carefully so that a single threshold can distinguish correctly all clusters in a large spatial dataset though some density-skewed clusters live in it. Finally, authors investigate a robotic navigation and test two artificial datasets by the proposed algorithm to verify its effectiveness and efficiency.

Low Complexity Precoded Greedy Power Allocation Algorithms for OFDM Communication Systems

In this paper, an enhanced greedy bit and power allocation algorithms for orthogonal frequency division multiplexing (OFDM) communication systems are introduced. These algorithms combine low complexity greedy power allocation algorithms with a simplified maximum ratio combining (MRC) precoding technique at the transmitter for maximizing the average data throughput of OFDM communication systems. Results of computer simulations show that precoding is an effective technique for improving the throughput performance of the proposed bit and power allocation algorithms.

GREEDY NON-DOMINATED SORTING IN GENETIC ALGORITHM-ⅡFOR VEHICLE ROUTING PROBLEM IN DISTRIBUTION

Vehicle routing problem in distribution （VRPD） is a widely used type of vehicle routing problem （VRP）, which has been proved as NP-Hard, and it is usually modeled as single objective optimization problem when modeling. For multi-objective optimization model, most researches consider two objectives. A multi-objective mathematical model for VRP is proposed, which considers the number of vehicles used, the length of route and the time arrived at each client. Genetic algorithm is one of the most widely used algorithms to solve VRP. As a type of genetic algorithm （GA）, non-dominated sorting in genetic algorithm-Ⅱ （NSGA-Ⅱ） also suffers from premature convergence and enclosure competition. In order to avoid these kinds of shortage, a greedy NSGA-Ⅱ （GNSGA-Ⅱ） is proposed for VRP problem. Greedy algorithm is implemented in generating the initial population, cross-over and mutation. All these procedures ensure that NSGA-Ⅱ is prevented from premature convergence and refine the performance of NSGA-Ⅱ at each step. In the distribution problem of a distribution center in Michigan, US, the GNSGA-Ⅱ is compared with NSGA-Ⅱ. As a result, the GNSGA-Ⅱ is the most efficient one and can get the most optimized solution to VRP problem. Also, in GNSGA-Ⅱ, premature convergence is better avoided and search efficiency has been improved sharply.

Adaptive block greedy algorithms for receiving multi-narrowband signal in compressive sensing radar reconnaissance receiver

This paper extends the application of compressive sensing(CS) to the radar reconnaissance receiver for receiving the multi-narrowband signal. By combining the concept of the block sparsity, the self-adaption methods, the binary tree search,and the residual monitoring mechanism, two adaptive block greedy algorithms are proposed to achieve a high probability adaptive reconstruction. The use of the block sparsity can greatly improve the efficiency of the support selection and reduce the lower boundary of the sub-sampling rate. Furthermore, the addition of binary tree search and monitoring mechanism with two different supports self-adaption methods overcome the instability caused by the fixed block length while optimizing the recovery of the unknown signal.The simulations and analysis of the adaptive reconstruction ability and theoretical computational complexity are given. Also, we verify the feasibility and effectiveness of the two algorithms by the experiments of receiving multi-narrowband signals on an analogto-information converter(AIC). Finally, an optimum reconstruction characteristic of two algorithms is found to facilitate efficient reception in practical applications.

Greedy Algorithm Applied to Relay Selection for Cooperative Communication Systems in Amplify-and-Forward Mode

Using a relaying system to provide spatial diversity and improve the system performance is a tendency in the wireless cooperative communications. Amplify-and-forward （AF） mode with a low complexity is easy to be implemented. Under the consideration of cooperative communication systems, the scenario includes one information source, M relay stations and N destinations. This work proposes a relay selection algorithm in the Raleigh fading channel. Based on the exhaustive search method, easily to realize, the optimal selection scheme can be found with a highly complicated calculation. In order to reduce the computational complexity, an approximate optimal solution with a greedy algorithm applied for the relay station selection is proposed. With different situations of the communication systems, the performance evaluation obtained by both the proposed algorithm and the exhaustive search algorithm are given for comparison. It shows the proposed algorithm could provide a solution approach to the optimal one.

Greedy Constructive Procedure-Based Hybrid Differential Algorithm for Flexible Flow shop Group Scheduling

Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential evolution( HDE) algorithm based on greedy constructive procedure( GCP) is proposed,which combines differential evolution( DE) with tabu search( TS). DE is applied to generating the elite individuals of population,while TS is used for finding the optimal value by making perturbation in selected elite individuals. A lower bounding technique is developed to evaluate the quality of proposed algorithm. Experimental results verify the effectiveness and feasibility of proposed algorithm.

A greedy algorithm based on joint assignment of airport gates and taxiways in large hub airports

With the rapid development of civil aviation in recent years,the management and assignment of airport resources are becoming more and more difficult.Among the various airport resources,gates and taxiways are very important,therefore,many researchers focus on the airport gate and taxiway assignment problem.However,the joint assignment algorithm of airport gates and taxiways with realistic airport data has not been well studied.A greedy algorithm based on joint assignment of airport gates and taxiways using the data of a large hub airport in China is proposed.The objective is maximizing the ratio of fixed gates and minimizing the ratio of taxiway collisions.Simulation results show that it outperforms other assignment schemes.

Numerical Studies of the Generalized <i>l</i>₁Greedy Algorithm for Sparse Signals

The generalized l1 greedy algorithm was recently introduced and used to reconstruct medical images in computerized tomography in the compressed sensing framework via total variation minimization. Experimental results showed that this algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in reconstructing these medical images. In this paper the effectiveness of the generalized l1 greedy algorithm in finding random sparse signals from underdetermined linear systems is investigated. A series of numerical experiments demonstrate that the generalized l1 greedy algorithm is superior to the reweighted l1-minimization and l1 greedy algorithms in the successful recovery of randomly generated Gaussian sparse signals from data generated by Gaussian random matrices. In particular, the generalized l1 greedy algorithm performs extraordinarily well in recovering random sparse signals with nonzero small entries. The stability of the generalized l1 greedy algorithm with respect to its parameters and the impact of noise on the recovery of Gaussian sparse signals are also studied.

Dynamic thermal management by greedy scheduling algorithm

Chip multiprocessors(CMPs) allow thread level parallelism,thus increasing performance.However,this comes with the cost of temperature problem.CMPs require more power,creating non uniform power map and hotspots.Aiming at this problem,a thread scheduling algorithm,the greedy scheduling algorithm,was proposed to reduce the thermal emergencies and to improve the throughput.The greedy scheduling algorithm was implemented in the Linux kernel on Intel's Quad-Core system.The experimental results show that the greedy scheduling algorithm can reduce 9.6%-78.5% of the hardware dynamic thermal management(DTM) in various combinations of workloads,and has an average of 5.2% and up to 9.7% throughput higher than the Linux standard scheduler.

基于I-Greedy求解CVaR模型的传感器网络布局优化

无线传感器网络在机械设备状态监测领域有着重要的作用,为了解决传统随机优化方法不适合某些复杂场传感器网络布局景的问题,提出了一种基于I-Greedy求解CVaR模型。采用惰性赋值的方法完成算法的简化过程,为τ设置了相应的搜索间隔Δ和搜索区间(0,Γ),防止算法出现局部最优解的情况,通过惰性赋值的方式实现快速搜索的功能。研究结果表明:τ搜索上界Γ设定成50和置信水平α=0.9时,能够确保各置信水平都搜索获得全局最优解。逐渐增加传感器节点数量后,布局效益获得了持续提升。计算得到互信息相对随机部署方法增加69%,与传统贪婪算法相比增加14.1%。CVaR布局模型相对传统布局模型可以达到更低损失程度,能够获得更优布局结果,提升了模型鲁棒性。算法能够显著降低时间复杂度,特别是进行大规模传感器布局时表现出了更强的优越性。

Greedy Algorithm in m-Term Approximation for Periodic Besov Class with Mixed Smoothness

Nonlinear m-term approximation plays an important role in machine learning, signal processing and statistical estimating. In this paper by means of a nondecreasing dominated function, a greedy adaptive compression numerical algorithm in the best m -term approximation with regard to tensor product wavelet-type basis is pro-posed. The algorithm provides the asymptotically optimal approximation for the class of periodic functions with mixed Besov smoothness in the L q norm. Moreover, it depends only on the expansion of function f by tensor pro-duct wavelet-type basis, but neither on q nor on any special features of f.

An Algorithm for the Inverse Problem of Matrix Processing: DNA Chains, Their Distance Matrices and Reconstructing

We continue to consider one of the cybernetic methods in biology related to the study of DNA chains. Exactly, we are considering the problem of reconstructing the distance matrix for DNA chains. Such a matrix is formed on the basis of any of the possible algorithms for determining the distances between DNA chains, as well as any specific object of study. At the same time, for example, the practical programming results show that on an average modern computer, it takes about a day to build such a 30 × 30 matrix for mnDNAs using the Needleman-Wunsch algorithm;therefore, for such a 300 × 300 matrix, about 3 months of continuous computer operation is expected. Thus, even for a relatively small number of species, calculating the distance matrix on conventional computers is hardly feasible and the supercomputers are usually not available. Therefore, we started publishing our variants of the algorithms for calculating the distance between two DNA chains, then we publish algorithms for restoring partially filled matrices, i.e., the inverse problem of matrix processing. Previously, we used the method of branches and boundaries, but in this paper we propose to use another new algorithm for restoring the distance matrix for DNA chains. Our recent work has shown that even greater improvement in the quality of the algorithm can often be achieved without improving the auxiliary heuristics of the branches and boundaries method. Thus, we are improving the algorithms that formulate the greedy function of this method only. .

Selection of Metaheuristic Algorithm to Design Wireless Sensor Network

The deployment of sensor nodes is an important aspect in mobile wireless sensor networks for increasing network performance.The longevity of the networks is mostly determined by the proportion of energy consumed and the sensor nodes’access network.The optimal or ideal positioning of sensors improves the portable sensor networks effectiveness.Coverage and energy usage are mostly determined by successful sensor placement strategies.Nature-inspired algorithms are the most effective solution for short sensor lifetime.The primary objective of work is to conduct a comparative analysis of nature-inspired optimization for wireless sensor networks(WSNs’)maximum network coverage.Moreover,it identifies quantity of installed sensor nodes for the given area.Superiority of algorithm has been identified based on value of optimized energy.The first half of the paper’s literature on nature-inspired algorithms is discussed.Later six metaheuristics algorithms(Grey wolf,Ant lion,Dragonfly,Whale,Moth flame,Sine cosine optimizer)are compared for optimal coverage of WSNs.The simulation outcomes confirm that whale opti-mization algorithm(WOA)gives optimized Energy with improved network coverage with the least number of nodes.This comparison will be helpful for researchers who will use WSNs in their applications.

改进RRT算法的采摘机械臂路径规划

针对采用传统的快速随机扩展树(RRT)算法的采摘机械臂在果园工作环境中搜索路径时间长,最终路径不平滑、拐点多等问题,提出了一种改进的RRT避障算法。改进的算法采用高斯采样策略,减少了采样的随机性,避免产生更多不必要的随机树,增加规划的导向性;再添加A*代价函数去除路径的冗余点,最后使用贪婪算法简化路径,减少拐点,让机械臂可以快速、准确、平稳地沿着最佳路径运动到目标点。仿真表明,改进后的算法有效地减少了路径规划的时间,缩短了路径长度,具有良好的可行性和有效性。

一种多无人机协同优先覆盖搜索算法

针对应急救援行动中存在的受灾区域大、重点区域分布不均匀、救援时间有限等问题,提出一种多UAV协同区域优先覆盖搜索算法。对搜索区域进行离散栅格化处理,根据灾情预估信息对搜索区域中的每个网格进行概率标记;通过K-means++聚类算法将搜索区域划分成大小相似、个数与UAV数量相等的子区域,依据聚类中心确定每个子区域的搜索起点,使多架UAV分区协同搜索整个区域;根据网格概率和当前距离之间的平衡关系计算出每个网格的分数,改进贪心算法,以此分数为基准在子区域中进行优先搜索和减少重复路径,引入A^(*)算法解决网格分数冗余问题。仿真结果表明:所提算法在保证优先搜索的同时缩短了路径长度和搜索时间,为应急救援中的搜索难题提供了一种有效的解决办法。

基于层间垫平的囊匣三维装箱优化设计

目的为提高囊匣的装载率及装箱效率,研究层间垫平的强异构类的三维装箱问题,实现快速计算囊匣装箱方案和衬垫方案并指示装箱。方法基于囊匣实际装箱需求,以衬垫体积最小为目标,设计基于贪心策略与改进的装箱顺序策略的两步优化启发式算法,对装箱与衬垫方案进行优化;并根据不同放置方向,设计不同的输出效果以指示装箱。结果与装箱优化前数据进行对比实验证明,该算法推荐的装箱方案与衬垫方案可以减少木箱的使用数量与体积,减少垫平用衬垫体积7.21%,装箱时间缩短了约一半。结论文中设计的混合启发式算法能为囊匣装箱问题找到合适的装箱与衬垫方案,减少衬垫的使用,提高装载率以及装箱效率。

基于改进遗传算法的细纱接头路径指引方法

为了提高细纱车间整体断头的接头效率,在细纱单锭监测系统响应到细纱断头信息的条件下,建立以整体车间断头接头路径最优化为目标函数的细纱接头路径指引模型,并运用Python编程语言分别实现对贪心算法、遗传算法和改进遗传算法接头路径模型的求解,结合传统巡回式接头路径与3种算法在效率、运行速度和解的质量上的仿真测试,对比验证改进遗传算法用于细纱接头路径指引方法的可行性。试验结果表明:相较于传统巡回式路径,改进遗传算法平均效率提升了11.8%,且解均优于其他两种算法;相较于遗传算法,改进遗传算法的响应时间缩短较多,平均为1.25 s,且波动较小,时间效率提升了80.3%。认为:改进遗传算法在效率、运行速度和解的质量上都优于其他算法,在细纱接头领域具有较高的应用优势,能够显著提高接头效率和降低成本。

基于深度强化学习和隐私保护的群智感知动态任务分配策略

在移动群智感知(Mobile Crowd Sensing,MCS)中,动态任务分配的结果对提高系统效率和确保数据质量至关重要。然而,现有的大部分研究在处理动态任务分配时,通常将其简化为二分匹配模型,该简化模型未充分考虑任务属性与工人属性对匹配结果的影响,同时忽视了工人位置隐私的保护问题。针对这些不足,文章提出一种基于深度强化学习和隐私保护的群智感知动态任务分配策略。该策略首先通过差分隐私技术为工人位置添加噪声,保护工人隐私;然后利用深度强化学习方法自适应地调整任务批量分配;最后使用基于工人任务执行能力阈值的贪婪算法计算最优策略下的平台总效用。在真实数据集上的实验结果表明,该策略在不同参数设置下均能保持优越的性能,同时有效地保护了工人的位置隐私。