Search

A safe trajectory generation method for quadrotor flight in three-dimension dense environments is proposed in this letter. We propose a path search algorithm called Safe A* to search a safe, collision-free initial path in cluttered environments. Subsequently, a safe and smooth trajectory with minimum snap is obtained by solving a quadratic problem in closed form. Our method is tested in various simulations, results turn out that our method can significantly increase the success rate of trajectory generation, and generate a safer trajectory as compared to the standard A* algorithm.

Transform-MinER (Transforming Molecules in Enzyme Reactions) is a web application facilitating the exploration of chemical biosynthetic space, guiding the user toward promising start points for enzyme design projects or directed evolution experiments. Two types of search are possible: Molecule Search allows a user to submit a source substrate enabling Transform-MinER to search for enzyme reactions acting on similar substrates, whereas Path Search additionally allows a user to submit a target molecule enabling Transform-MinER to search for a path of enzyme reactions acting on similar substrates to link source and target. Transform-MinER searches for potential reaction centers in the source substrate and uses chemoinformatic fingerprints to identify those that are situated in molecular environments similar to native counterparts, prioritizing steps that move closer to the target using reactions most similar to native in its exploration of search space. The ligand-based methodology behind Transform-MinER is presented, and its performance is validated yielding 90% success rates: first, on a data set of native pathways from the KEGG database, and second, on a data set of de novo enzyme reactions.

The coordinates of nodes are very important in the application of wireless sensor networks (WSN). The range-free localization algorithm is the best method to obtain the coordinates of sensor nodes at present. Range-free localization algorithm can be divided into two stages: distance estimation and coordinate calculation. For reduce the error in the distance estimation stage, a node localization algorithm for WSN based on virtual partition and distance correction (VP-DC) is proposed in this paper. In the distance estimation stage, firstly, the distance of each hop on the shortest communication path between the unknown node and the beacon node is calculated with the employment of virtual partition algorithm, then, the length of the shortest communication path is obtained by summing the distance of each hop, finally, the unknown distance between nodes is obtained according to the optimal path search algorithm and the distance correction formula. This paper innovative proposes the virtual partition algorithm and the optimal path search algorithm, which effectively avoids the distance estimation error caused by hop number and hop distance, and improves the localization accuracy of unknown nodes.

Because inorganic solid electrolytes are one of the key components for application to all-solid-state batteries, high-ionic-conductivity materials must be developed. Therefore, we propose a method of efficiently evaluating the activation energy of ionic diffusion by calculating a potential-energy surface (PES), searching for the optimal diffusion path by an algorithm developed using dynamic programming (DP), and calculating the corresponding activation energy by the nudged elastic band (NEB) method. Taking beta-Li3PS4 as an example, the activation energy of Li-ion diffusion was calculated as 0.43, 0.25, and 0.40 eV in the a-, b-, and c-axis directions, respectively, which is in good agreement with previously reported values. By comprehensively searching for the lowest energy path by PES-DP, the arbitrariness of the path selection can be eliminated, and the activation energy must only be calculated using the NEB method a few times, which greatly reduces the computational cost required for evaluating activation energy and enables the high-throughput screening of solid state electrolytes., 8 pages, 10 figures

In this paper, we designed a compound algorithm which combined the advantages of Dijkstra and ant colony optimization to complete the robot path planning. The compound algorithm is one that uses the Dijkstra algorithm for initial path planning under a viewable environment model, and then optimizes the initial path with an improved ACO. Pointing at the problem that the ACO is slow to converge and easy to fall into the local optimal solution, the performance of ACO is improved by constructing a new heuristic function and improving the pheromone update principle. Through the simulation on MATLAB, the designed algorithm shows higher path search efficiency and path optimization rate than the traditional algorithms.

With the continuous development of UAV technology, autonomous path planning methods suitable for UAVs are also evolving. In complex environments, UAVs not only need to consider the dynamics and time constraints, but also find the best and collision-free path. Although many researchers have conducted research on UAV path planning, there is a lack of comprehensive investigation and intuitive display of UAV path planning in a three-dimensional complex unknown environment. This article comprehensively analysis the path search algorithm and trajectory optimization method for UAVs in a three-dimensional environment, classifies them and compares them for each category, analyses the advantages and disadvantages of these methods.

Unsupervised fact checking approaches for knowledge graphs commonly combine path search and scoring to predict the likelihood of assertions being true. Current approaches search for said metapaths in the discrete search space spanned by the input knowledge graph and make no use of continuous representations of knowledge graphs. We hypothesize that augmenting existing approaches with information from continuous knowledge graph representations has the potential to improve their performance. Our approach Esther searches for metapaths in compositional embedding spaces instead of the graph itself. By being able to explore longer metapaths, it can detect supplementary evidence for assertions being true that can be exploited by existing fact checking approaches. We evaluate Esther by combining it with 10 other approaches in an ensemble learning setting. Our results agree with our hypothesis and suggest that all other approaches can benefit from being combined with Esther by 20.65% AUC-ROC on average. Our code is open-source and can be found at https://github.com/dice-group/esther.

At present, range-free localization algorithm is the mainstream of node localization method, which has made tremendous achievements. However, there are few algorithms that can be used in concave regions, and the existing algorithms have defects such as hop distance error, excessive time complexity and so on. To solve these problems, this paper proposes a two-stage PSO (Particle Swarm Optimization) algorithm for wireless sensor nodes localization in &ldquo, concave regions&rdquo, In the first stage, it proposes a method of distance measuring based on similar path search and intersection ratio, and completes the initial localization of unknown nodes based on maximum likelihood estimation. In the second stage, the improved PSO algorithm is used to optimize the initial localization results in the previous stage. The experimental result shows that the localization error of this algorithm is always within 10% and the execution time is maintained at about 20 s when the communication radius and beacon node ratio is changing. Therefore, the algorithm can obtain high localization accuracy in wireless sensor network with &ldquo, requiring low computing power for nodes, and energy consumption. Given this, it can greatly extend the service life of sensor nodes.

Path search is designed to find a path by traversing the state spaces from the initial state to the target state. Given enough memory and run time, the A* algorithm can find an optimal solution, but it expends much time to distinguish similar paths. Therefore, many scholars have proposed variants of the A* algorithm that find a suboptimal solution to speed up the searching efficiency. In this paper, the A* algorithm is improved and a new anytime dynamic heuristic search algorithm (ADHS) is proposed. It can find a solution quickly and then continuously optimize the quality of the solution to find the suboptimal solution until the end of time. The ADHS includes two stages, in the exploration stage, given an arbitrary cost bound, the solution is quickly obtained; in the update stage, where no setting parameters are required, reuses the previous search results. According to the cost of the latest solution, the dynamic weight factor w is introduced, which is half of the error between the current cost bound and the current solution. The next cost bound is dynamically adjusted, and the suboptimal solution is output. We tested the performance of the ADHS on the grid maps, and the experiments demonstrated that the performance of the ADHS was better than other algorithms.

In internet age, the interaction among people becomes more and more frequent. Therefore, the trust relationships between people are becoming more and more important. So it has become one of the hot spots in the research of multi-agent systems and trust path search. Trust network is established based on the transitivity of trust, and it is useful to use the network to evaluate the trust between two indirectly connected users on the reliable path. Aggregating trust of all possible trust paths can improve the accuracy of trust inference, so it is necessary to extend the problem of finding a single path to multiple trust paths. This paper mainly summarizes the study of trust path search and comprises four parts: the basic study of trust and trust network; some kinds of heuristic search algorithms including unidirectional and bidirectional searching for the shortest path, single-agent and multi-agent searching for multiple paths; the researches on path search based on trust; and the future directions of trust path search.

The bottleneck of today’s airspace is the Terminal Maneuvering Areas (TMA), where aircraft leave their routes to descend to an airport or take off and reach the en-route sector. To avoid congestion in these areas, an efficient design of departure and arrival routes is necessary. In this work, a solution for designing departure and arrival routes is proposed, which takes into account the runway configuration, the surroundings of the airport and operational constraints such as limited slopes or turn angles. The routes consist of two parts: a horizontal path in a graph constructed by sampling the TMA around the runway, to which is associated a cone of altitudes. The set of all routes is optimized by the Simulated Annealing metaheuristic. In the process and at each iteration, each route is computed by defining adequately the cost of the arcs in the graph and then searching a path on it. The costs are chosen so as to avoid zigzag behaviors as much as possible. Several tests were performed, one on an artificial problem designed specifically to test this approach and the three others on instances taken from the literature. The obtained results are satisfying with regard to the current state of air operations management and constraints.; Les TMAs (Terminal Maneuvering Areas) sont aujourd’hui un goulot d’étranglement de l’espace aérien, dans lequel les avions quittent leur phase de croisière pour atterrir à un aéroport, ou au contraire effectuent leur montée pour rejoindre leur route de croisière. Afin d’éviter la congestion de ces zones, il est nécessaire de construire des routes de départ et d’arrivée efficaces. Dans ce travail, une solution pour la création de routes de départ et d’arrivée est proposée, prenant en compte la configuration des pistes, les environs de l’aéroport, ainsi qu’un ensemble de contraintes opérationnelles telles que les angles de montée ou de virages limités.Les routes sont en deux parties : un chemin horizontal construit dans un graphe discrétisant la TMA, auquel est associé un cône d’altitudes. L’ensemble des routes est optimisé à l’aide d’un algorithme de recuit simulé. Dans ce processus, à chaque itération, chaque route est construite en valuant les arcs du graphe, puis en effectuant une recherche de chemin dans celui-ci. Les coûts des arcs sont choisis de manière à éviter autant que possible les phénomènes de zigzag.Plusieurs tests ont été effectués : un sur un cas artificiel créé spécifiquement pour cette approche, et trois autres sur des cas tirés de la littérature. Les résultats obtenus sont satisfaisants au regard de l’état actuel de la gestion du trafic aérien et des contraintes afférentes.

The bottleneck of today's airspace is the Terminal Maneuvering Areas (TMA), where aircraft leave their routes to descend to an airport or take off and reach the en-route sector. To avoid congestion in these areas, an efficient design of departure and arrival routes is necessary. In this work, a solution for designing departure and arrival routes is proposed, which takes into account the runway configuration, the surroundings of the airport and operational constraints such as limited slopes or turn angles. The routes consist of two parts: a horizontal path in a graph constructed by sampling the TMA around the runway, to which is associated a cone of altitudes. The set of all routes is optimized by the Simulated Annealing metaheuristic. In the process and at each iteration, each route is computed by defining adequately the cost of the arcs in the graph and then searching a path on it. The costs are chosen so as to avoid zigzag behaviors as much as possible. Several tests were performed, one on an artificial problem designed specifically to test this approach and the three others on instances taken from the literature. The obtained results are satisfying with regard to the current state of air operations management and constraints., Les TMAs (Terminal Maneuvering Areas) sont aujourd'hui un goulot d'étranglement de l'espace aérien, dans lequel les avions quittent leur phase de croisière pour atterrir à un aéroport, ou au contraire effectuent leur montée pour rejoindre leur route de croisière. Afin d'éviter la congestion de ces zones, il est nécessaire de construire des routes de départ et d'arrivée efficaces. Dans ce travail, une solution pour la création de routes de départ et d'arrivée est proposée, prenant en compte la configuration des pistes, les environs de l'aéroport, ainsi qu'un ensemble de contraintes opérationnelles telles que les angles de montée ou de virages limités. Les routes sont en deux parties : un chemin horizontal construit dans un graphe discrétisant la TMA, auquel est associé un cône d'altitudes. L'ensemble des routes est optimisé à l'aide d'un algorithme de recuit simulé. Dans ce processus, à chaque itération, chaque route est construite en valuant les arcs du graphe, puis en effectuant une recherche de chemin dans celui-ci. Les coûts des arcs sont choisis de manière à éviter autant que possible les phénomènes de zigzag. Plusieurs tests ont été effectués : un sur un cas artificiel créé spécifiquement pour cette approche, et trois autres sur des cas tirés de la littérature. Les résultats obtenus sont satisfaisants au regard de l'état actuel de la gestion du trafic aérien et des contraintes afférentes.

This paper briefly introduced the vehicular communication network, vehicular ad-hoc network (VANET), and the ant colony algorithm for path search in the network, improved the ant colony algorithm, carried out a simulation experiment on the improved ant colony algorithm on the simulation platform, and compared it with the traditional ant colony algorithm and the geographical location-based routing algorithm. The results showed that the network packet loss rate and time delay showed a tendency of increasing first and then decreasing under the three algorithms with the increase of vehicle nodes in VANET; with the increase of nodes, the network reliability under the improved ant colony algorithm showed a tendency of increasing first and then being stable, and the network reliability under the other two algorithms showed a tendency of increasing first and then decreasing; under the same number of nodes, the packet loss rate and average delay were lower, and the reliability was higher under the improved ant colony algorithm.

An autonomous underwater vehicle (AUV) is an economical and safe tool that is well-suited for search, investigation, identification, and salvage operations on the sea floor. Path planning technology, which primarily includes modeling methods and path search algorithms, is an important technology for AUVs. In recent years, the AUV path planning technology has rapidly developed. Compared with land robots, AUVs must endure complex underwater environments and consider various factors, such as currents, water pressure, and topography. Challenges exist in terms of online obstacle avoidance, three-dimensional environment path planning, and the robustness of the algorithms. Adapting a complex environment and finding a suitable path planning method comprise the main problem that must be solved. In this paper, we summarize the principles, advantages, and disadvantages of modeling and path search technologies for AUVs. The most prominent feature of this paper is to summarize the improvement methods of various technical shortcomings and improve the original methods, such as dynamic obstacle avoidance, optimization path, coverage, and processing speed. In addition to summarizing the characteristics of each algorithm, this paper intuitively demonstrates the experimental environment, the real-time nature, the path planning range of the AUV, and so on. We also discuss the application scenarios of various modeling and path search technologies for AUVs. In addition, we discuss the challenges of AUVs and the direction of future research.

Tsunami hazard in coastal areas susceptible to flooding, although reduced (in terms of probability of occurrence), may pose a high risk. Therefore, in these areas, a detailed evacuation planning of the affected population is required as a risk mitigation measure. The knowledge and enforcement of evacuation routes may reduce the population vulnerability, making it more resilient and reducing risk. This paper presents a GIS approach for modelling evacuation routes based on the optimal path search problem, of the graph theory, which is implemented on ArcCasper tool. The methodology proposed considers the elements involved in the evacuation process, the worst credible tsunami inundation scenario (hazard extent and travel time), the number of people that needs to be evacuated in different time scenarios, the safe areas or destination points of the evacuation routes, the roads network characteristics and finally the time available to evacuate. The knowledge of those elements allows predicting some possible outcomes of the evacuation, such as the arrival time of the evacuees to a shelter and the identification of congestion hot spots resulting from the application of a flocking model which simulates the path to be used by evacuees avoiding obstacles. The municipality of Cascais was used to test the methodology proposed in this study. Cascais is one of the largest urban centres located about 25 km west of Lisbon, Portugal, with a high density of infrastructure along the coastline whereby most of the population and economic activities are exposed to a tsunami. The results, presented in the form of maps, allow identifying the optimal evacuation routes as well as the unfeasible routes. This crucial information could be used to the evacuation optimization regarding the location of meeting points and vertical shelters as well as to improve the accessibility of the areas to be evacuated.

Submitted by Aline Batista (alinehb.ufpel@gmail.com) on 2020-08-11T21:36:07Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Stephano_Machado_Moreira.pdf: 3252235 bytes, checksum: 16f91f7fc566bd22ffa09aa59c0d5b72 (MD5) Approved for entry into archive by Aline Batista (alinehb.ufpel@gmail.com) on 2020-08-13T11:59:17Z (GMT) No. of bitstreams: 2 Tese_Stephano_Machado_Moreira.pdf: 3252235 bytes, checksum: 16f91f7fc566bd22ffa09aa59c0d5b72 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Made available in DSpace on 2020-08-13T11:59:30Z (GMT). No. of bitstreams: 2 Tese_Stephano_Machado_Moreira.pdf: 3252235 bytes, checksum: 16f91f7fc566bd22ffa09aa59c0d5b72 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2020-01-15 Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES Detailed routing is one of the most challenging and time-consuming steps of the design of integrated circuits. The routing solution must obey all of the design rules so that the circuit can be properly manufactured. However, design rule handling may be very challenging, regarding its algorithmic solutions and implementation, and may easily lead to unfeasible runtimes. In order to make the detailed routing resolution more feasible, it is divided into two steps, where in the first, called initial detailed routing, an almost complete solution is achieved by relaxing design rules. In the second step the remaining design rule violations are solved. However, the more these rules are left to be handled in the second stage, the greater is the chance that they will not be completely solved, and this usually occurs. Thus, it is necessary to face the challenge of dealing with as many rules as possible in the first step without compromising the runtime. Thus, this work proposes an initial detailed router, called SmartDR, to meet these needs, that is, to provide a good design rule handling while keeping a good runtime. The main features of the router that meet these goals are pin access and path search techniques. This work proposes a novel pin access method, in which the pin access paths share the same routing resources and are dynamically legalized and implemented. It is also proposed a new path search algorithm, based on A *-interval search, which is aware of several design rules. A new method to improve the A * heuristic function is also proposed, taking into account the peculiarities of detailed routing, which leads to a better runtime. Using ISPD 2018 Contest benchmarks, all proposed methods were evaluated separately and altogether in the proposed router, which was compared with state-of-the-art routers. The experiments show that the proposed techniques contribute to runtime and design rule handling improvement, as well as it demonstrates that SmartDR is superior to the state-of-the-art routers in these metrics. O roteamento detalhado é uma das etapas mais desafiadoras e demoradas do projeto de circuitos integrados. A solução do roteamento deve obedecer a todas as regras de projeto para que o circuito possa ser corretamente fabricado. No entanto, o tratamento de regras de projeto pode ser muito desafiador, quanto a suas soluções algorítmicas e sua implementação, e pode facilmente levar a tempos de execução inviáveis. Para tornar a resolução do roteamento detalhado mais factível, ele é dividido em duas etapas, onde, na primeira, chamada de roteamento detalhado inicial, uma solução quase completa é obtida mediante a flexibilização das regras de projeto. Na segunda etapa as violações remanescentes de regras de projeto são resolvidas. No entanto, quanto mais o tratamento dessas regras é deixado para a segunda etapa, maior é a chance de elas não serem resolvidas completamente, e isto costuma ocorrer. Assim, é necessário enfrentar o desafio de lidar com o maior número possível de regras na etapa inicial sem comprometer o desempenho do roteamento. Dessa forma, este trabalho propõe um roteador detalhado inicial, chamado SmartDR, para atender essas necessidades, isto é, apresentar uma boa lida com regras de projeto ao mesmo tempo que mantendo um bom desempenho. As principais características do roteador, que atendem a esses objetivos, são técnicas de acesso a pinos e de busca de caminhos. Este trabalho propõe um novo método de acesso a pinos, em que os caminhos de acesso a pinos compartilham os mesmos recursos de roteamento e são legalizados e implementados dinamicamente. Também é proposto um novo algoritmo de busca de caminhos, baseado na busca A* com intervalos, o qual é ciente de várias regras de projeto. É proposto também um novo método para melhorar a função heurística da busca A* levando em consideração peculiaridades do roteamento detalhado, o que leva a um melhor desempenho. Utilizando os benchmarks da competição ISPD 2018, todos os métodos propostos foram avaliados separadamente e em conjunto no roteador proposto, o qual foi comparado com os roteadores estado-da-arte. Os experimentos mostram que as técnicas propostas contribuem para uma melhoria em desempenho e um bom tratamento de regras de projeto, assim como demonstra que o SmartDR é superior aos roteadores estado da arte nesses mesmos quesitos.

Maze Chase is a game that has a maze background. In this game there are players who have the task, which is to take all the points in the labyrinth. In the Maze Chase game there is also an NPC (Non-Playable Character) that aims to chase players so that players cannot take all the points in the labyrinth. Players can be considered to have won the game is that all the points in the labyrinth have been taken by the player. The author implements the A* and RIBS path search algorithms for NPCs so that NPCs can chase players. That way we get the travel time comparison to the players on each path search algorithm. After testing the average travel time to NPC players with the A* algorithm faster 0.116196% than NPC with the RIBS algorithm.

In view of the disadvantages of the basic ant colony algorithm in solving non-deterministic polynomial problems, such as slow convergence rate and local optimal solution. In this paper, the updating rules of pheromone and the updating strategy of target city in ant colony algorithm are improved, and an improved ant colony algorithm (IACA) is proposed. In addition, it is applied to the shortest traversal path search of travel salesman problem. Taking 33 provincial capitals and berlin52 problems as test objects, this paper compares the search efficiency of the proposed algorithm with that of the basic ant colony algorithm. It can be seen from the simulation results that IACA has a faster convergence rate than the basic ant colony algorithm. IACA is obviously superior to the basic ant colony algorithm in terms of convergence and the quality of the optimal solution. It provides a new choice for solving similar optimization problems.

In this paper, the path planning problem in known environments was studied. According to Dijkstra algorithm and ant colony optimization (ACO), we designed a hybrid algorithm to search the path. Based on the environment model, constructed by using visual graph method, Dijkstra algorithm was used for initial path planning. Then the ACO was improved and used to optimizes the initial path to minimize the path of the robot. The simulation on MATLAB showed that the path planning algorithm based on Dijkstra-ACO has higher efficiency of path search and good effect of path planning. The algorithm is effective and feasible.

In order to solve the problem of AGV path planning and obstacle avoidance in intelligent warehouse, this paper proposes an optimized particle swarm optimization (POS) algorithm. Through the immune information adjustment and optimization mechanism in the immune algorithm, the particle diversity in the particle group is improved and the understanding ability is improved. The overall nature. The grid map is simulated by MATLAB. The results show that the optimized particle swarm optimization algorithm has better adaptability, and the optimal path search capability has a certain improvement, which makes the AGV running path shorter, thus improving the efficiency of the intelligent warehouse.

Optimization of the path planning algorithms is an important direction in many research fields, such as robot and map. In this paper, a noval graph lossless compression method is presented for layout partitioning to shorten the time for path planning. This compression algorithm is designed for layout files, based on polygons in each layer of the layout. It can be loaded on various path search algorithms and optimization methods to find a path bypassing polygons between two points as a cutting line. The proposed algorithm not only improves the partition efficiency significantly, but also makes it easier to restore the layouts. Then the small irregular partitioned patterns can be used for next layout operation: Optical Proximity Correction(OPC).

The symmetry concept is mainly used in two senses. The first from the aesthetic point of view of proportionality or harmony, since human beings seek symmetry in nature. Or the second, from an engineering point of view to attend to geometric regularities or to explain a repetition process or pattern in a given phenomenon. This special issue dedicated to geometry in engineering deals with this last concept, which aims to collect both the aspects of geometric solutions in engineering, which may even have a certain aesthetic character, and the aspect of the use of patterns that explain observed phenomena.

One approach to solve detailed routing is net-by-net using a fast A∗-based path search algorithm to handle long connections. Such path search algorithms usually rely on the manhattan distance to implement their heuristic function, providing a poor lower bound since the search is constrained by the global routing guide. This work proposes a new technique to provide a more realistic lower bound in this scenario. We precompute some lower bounds before the path search by applying a modified version of Dijkstra's algorithm on tunnels (sections of the global routing guide). This information is used during the search, reducing the runtime by 58% in average, in comparison to the classic manhattan distance, on ISPD 2018 benchmarks. We also show an improvement of our technique over existing work [10]. Our preprocessing method runtime is negligible, maximizing the benefit of using the improved heuristic function during the path search.

Various traffic network usage formats have arisen along with the popularization of automobiles and the continued service extension of busses, subways, and other forms of public transportation. Due to various characteristics of public transportation networks, unlike general street networks, many issues can affect public transportation, and an optimal course search should be considered. Present research considers plans to improve the overall efficiency of public transportation systems with regard to destination, means, route, and other factors to be selected efficiently in this environment as public transportation usage increases. From this perspective, it suggests the characteristics that a multimodal transit network route search algorithm should have and a corrective algorithm that implements this in an applicable program. Implementation was done in Google android application which provides a simple user interface to find optimal routes in Google Map. The proposed application would enable overall quality-of-service improvement and balanced usage of public transportation, efficient traffic management, and other advantages.

Search speed, quality of resulting paths and the cost of pre-processing are the principle evaluation metrics of a pathfinding algorithm. In this paper, a new algorithm for grid-based maps, rectangle expansion A∗ (REA∗), is presented that improves the performance of A∗ significantly. REA∗ explores maps in units of unblocked rectangles. All unnecessary points inside the rectangles are pruned and boundaries of the rectangles (instead of individual points within those boundaries) are used as search nodes. This makes the algorithm plot fewer points and have a much shorter open list than A∗. REA∗ returns jump and grid-optimal path points, but since the line of sight between jump points is protected by the unblocked rectangles, the resulting path of REA∗ is usually better than grid-optimal. The algorithm is entirely online and requires no offline pre-processing. Experimental results for typical benchmark problem sets show that REA∗ can speed up a highly optimized A∗ by an order of magnitude and more while preserving completeness and optimality. This new algorithm is competitive with other highly successful variants of A∗.

In this study, the improved Dynamic Time Warping (DTW) algorithm is used in MATLAB to perform simulation classification and recognition simulation on the sounds of Nycticorax nycticorax and other 10 birds in the Wuzhishan Islands Reserve in Zhoushan, Zhejiang. By setting the slope of the path, the path is restricted in a fixed parallelogram. The algorithm combines with global restrictions can effectively speed up the path search, reduce the amount of calculation, reduce the memory requirements, reduce the recognition time, and thus improve the recognition efficiency. Experimental results show that compared with the traditional DTW algorithm, the improved DTW algorithm increases the recognition speed by 36.49%, the accuracy rate by 4.08%, and the recognition efficiency is greatly improved.

As an efficient data mining technique, data clustering has been widely-used for data analysis and extracting valuable hidden information. Leveraging the simplicity and effectiveness, the evolutionary optimization-driven clustering algorithms have exhibited promising performance and attracted tremendous attention. Up to the present, how to enable these algorithms to escape from local optima and accelerate convergence rates is an ongoing challenge. In this paper, we propose a novel adaptive Differential Evolution (DE) variant to deal with the above challenge when clustering data. In the improved DE algorithm, the four interdependent components, including mutation strategy, crossover strategy, scaling factor value, and crossover rate, are adaptively configured in an integrated manner via ant colony optimization (ACO) during the problem-solving process. To be specific, the relationships of four components in the DE algorithm are modeled as a directed acyclic graph, and a path in the graph exactly corresponds to a configuration for DE. During the optimization process, ant colony optimization is employed to search for a reasonable path for each individual of DE in terms of pheromones on arcs. In this manner, the configuration of the four interdependent components of DE will be generated dynamically, which is then used to guide the successive search behaviors of individuals in DE. Each individual has a path, representing a configuration for each component. After each iteration, individuals that generate promising solutions are allowed to deposit pheromone on the paths, resulting in more pheromones on the arcs appearing in better algorithm configurations (paths) more frequently. Through this manner, the search strategies and parameters of DE are comprehensively adapted by ACO. The proposed algorithm is named ACODE for short. To verify its effectiveness, the proposed ACODE is compared with four representative data clustering algorithms on eight widely-used benchmark datasets. The experimental results demonstrate the advantages of ACODE over half of the datasets.

Different from global routing, detailed routing takes care of many detailed design rules and is performed on a significantly larger routing grid graph. In advanced technology nodes, it becomes the most complicated and time-consuming stage. We propose Dr. CU, an efficient and effective detailed router, to tackle the challenges. To handle a 3D detailed routing grid graph of enormous size, a set of two-level sparse data structures is designed for runtime and memory efficiency. For handling the minimum-area constraint, an optimal correct-by-construction path search algorithm is proposed. Besides, an efficient bulk synchronous parallel scheme is adopted to further reduce the runtime usage. Compared with the first place of ISPD 2018 Contest, our router improves the routing quality by up to 65% and on average 39%, according to the contest metric. At the same time, it achieves 80--93% memory reduction, and 2.5--15X speed-up.

This paper presents some results of the routing task formulation and solving for the software defined networks. We consider the routing task as search of the optimal path and the task of the resources distribution. Choosing of the path search method affects on the network resources utilization and quality of service. We consider this task as the optimization problem and consider the objective functions forming in the points of view of both of the tasks. Some examples of solutions were obtained by using of simulation method. Analysis of these results shows difference between the different approaches for the objective function formulation.