Search

Optimizing path planning for energy efficiency is critical for achieving sustainable vehicular transportation. This paper presents a novel framework for evaluating the impact of path planning algorithms (PPAs) on energy consumption within a simulated environment. We leverage the CARLA simulator to conduct a comparative analysis between the widely used A* and a Hybrid Genetic Algorithm (HGA) across diverse vehicular scenarios. This investigation aims to quantify the influence of PPA selection on vehicle energy expenditure, enabling data-driven optimization for energy minimization. We leverage an offline energy estimation model to further streamline the comparison of the two PPAs. Extensive simulations are employed to demonstrate the efficiency and adaptability of the proposed framework. The findings contribute to the development of energy-efficient path-planning strategies, promoting advancements toward sustainable transportation systems. [ABSTRACT FROM AUTHOR]

In this paper, we address the challenges faced by Value Iteration Networks (VIN) in handling larger input maps and mitigating the impact of accumulated errors caused by increased iterations. We propose a novel approach, Value Iteration Networks with Gated Summarization Module (GS-VIN), which incorporates two main improvements: 1) employing an Adaptive Iteration Strategy in the Value Iteration module to reduce the number of iterations; and 2) introducing a Gated Summarization module to summarize the iterative process. The adaptive iteration strategy uses larger convolution kernels with fewer iteration times, reducing network depth and increasing training stability while maintaining the accuracy of the planning process. The gated summarization module enables the network to emphasize the entire planning process, rather than solely relying on the final global planning outcome, by temporally and spatially resampling the entire planning process within the VI module. We conduct experiments on 2D grid world path-finding problems and the Atari Mr. Pac-man environment, demonstrating that GS-VIN outperforms the baseline in terms of single-step accuracy, planning success rate, and overall performance across different map sizes. Additionally, we provide an analysis of the relationship between input size, kernel size, and the number of iterations in VI-based models, which is applicable to a majority of VI-based models and offers valuable insights for researchers and industrial deployment.

Augmented Reality (AR) is a technology that has been used extensively in the field of cartography, with one particular application being that of navigation. However even now, AR in navigation is still at an active exploratory stage with multiple different approaches regarding the techniques, methodologies, and development processes. In this work, we present a systematic review of application development in AR navigation research, aiming to fill the gap in the literature by identifying trends in aspects such as hardware, software, and methodologies in AR navigation. We review 107 publications from the past 25 years that present AR navigation software for real-world environments, and analyze their main characteristics regarding intended environments and users, hardware, development platforms, and AR methodologies. We note a rise in AR navigation research interest from 2010 onward, driven in large part by smartphone and mobile device ubiquity, supported further by significant advances and streamlined processes in AR application development. Furthermore, we highlight a rise in the use of increasingly more complex AR methodologies in recent years, signaling that the field is steadily evolving and maturing. At the same time, we also identify significant inconsistencies and omissions regarding the reporting of technical details, with nearly half of reviewed works not reporting one or more of the aspects of interest. After identifying the level of maturity and complexity in the field AR navigation, we provide a list of recommendations and future directions for researchers aiming to develop AR navigation applications. [ABSTRACT FROM AUTHOR]

Implementation of Machine Learning (ML) to improve product and production development processes poses a significant opportunity for manufacturing industries. ML has the capability to calibrate models with considerable adaptability and high accuracy. This capability is specifically promising for applications where classical production automation is too expensive, e.g., for mass customization cases where the production environment is uncertain and unstructured. To cope with the diversity in production systems and working environments, Reinforcement Learning (RL) in combination with lightweight game engines can be used from initial stages of a product and production development process. However, there are multiple challenges such as collecting observations in a virtual environment which can interact similar to a physical environment. This project focuses on setting up RL methodologies to perform path-finding and collision detection in varying environments. One case study is human assembly evaluation method in the automobile industry which is currently manual intensive to investigate digitally. For this case, a mannequin is trained to perform pick and place operations in varying environments and thus automating assembly validation process in early design phases. The next application is path-finding of mobile robots including an articulated arm to perform pick and place operations. This application is expensive to setup with classical methods and thus RL enables an automated approach for this task as well. [ABSTRACT FROM AUTHOR]

Implementation of Machine Learning (ML) to improve product and production development processes poses a significant opportunity for manufacturing industries. ML has the capability to calibrate models with considerable adaptability and high accuracy. This capability is specifically promising for applications where classical production automation is too expensive, e.g., for mass customization cases where the production environment is uncertain and unstructured. To cope with the diversity in production systems and working environments, Reinforcement Learning (RL) in combination with lightweight game engines can be used from initial stages of a product and production development process. However, there are multiple challenges such as collecting observations in a virtual environment which can interact similar to a physical environment. This project focuses on setting up RL methodologies to perform path-finding and collision detection in varying environments. One case study is human assembly evaluation method in the automobile industry which is currently manual intensive to investigate digitally. For this case, a mannequin is trained to perform pick and place operations in varying environments and thus automating assembly validation process in early design phases. The next application is path-finding of mobile robots including an articulated arm to perform pick and place operations. This application is expensive to setup with classical methods and thus RL enables an automated approach for this task as well.

We introduce a new chamfering paradigm, locally connecting pixels to produce path distances that approximate Euclidean space by building a small network (a replacement product) inside each pixel. These “ RE-grid graphs” maintain near-Euclidean polygonal distance contours even in noisy data sets, making them useful tools for approximation when exact numerical solutions are unobtainable or impractical. The RE-grid graph creates a modular global architecture with lower pixel-to-pixel valency and simplified topology at the cost of increased computational complexity due to its internal structure. We present an introduction to chamfering replacement products with a number of case study examples to demonstrate the potential of these graphs for path-finding in high frequency and low resolution image spaces which motivate further study. Possible future applications include morphology, watershed segmentation, halftoning, neural network design, anisotropic image processing, image skeletonization, dendritic shaping, and cellular automata. [ABSTRACT FROM AUTHOR]

We present an in-depth discussion on the subband Boltzmann transport (SBTE) methodology, its evolution, and its application to the simulation of nanoscale MOSFETs. The evolution of the method is presented from the point of view of developing a commercial general-purpose SBTE solver, the GTS nano device simulator (NDS). We show a wide range of applications SBTE is suited for, including state-of-the-art nonplanar and well-established planar technologies. It is demonstrated how SBTE can be employed both as a path-finding tool and a fundamental component in a DTCO-flow. [ABSTRACT FROM AUTHOR]

We introduce a new chamfering paradigm, locally connecting pixels to produce path distances that approximate Euclidean space by building a small network (a replacement product) inside each pixel. These “ $RE$ -grid graphs” maintain near-Euclidean polygonal distance contours even in noisy data sets, making them useful tools for approximation when exact numerical solutions are unobtainable or impractical. The $RE$ -grid graph creates a modular global architecture with lower pixel-to-pixel valency and simplified topology at the cost of increased computational complexity due to its internal structure. We present an introduction to chamfering replacement products with a number of case study examples to demonstrate the potential of these graphs for path-finding in high frequency and low resolution image spaces which motivate further study. Possible future applications include morphology, watershed segmentation, halftoning, neural network design, anisotropic image processing, image skeletonization, dendritic shaping, and cellular automata. [ABSTRACT FROM AUTHOR]

Abstract This paper deals with an efficient parallel and distributed framework for intensive computation with A* algorithm based on MapReduce concept. The A* algorithm is one of the most popular graph traversal algorithm used in route guidance. It requires exponential time computation and very costly hardware to compute the shortest path on large-scale networks. Thus, it is necessary to reduce the time complexity while exploiting a low cost commodity hardwares. To cope with this situation, we propose a novel approach that reduces the A* algorithm into a set of Map and Reduce tasks for running the path computation on Hadoop MapReduce framework. An application on real road networks illustrates the feasibility and reliability of the proposed framework. The experiments performed on a 6-node Hadoop cluster proves that the proposed approach outperforms A* algorithm and achieves significant gain in terms of computation time.

Ray-tracers are used for modeling the propagation behavior of mobile communications or radar within a given scenario. The necessary CPU-time for the path-finding is often the bottleneck of the simulation. The paper shows a new interpolation method, which exploits the similarity of an incoming plane wave at a receiver position with that in the vicinity of the position. This is combined with a linear weighting, as in general the waves at other receiver positions can be used for the interpolation. Examples using a ray-tracer equipped with the method demonstrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]

In this paper, a solution to monitor the location of humans during their activity in the agriculture sector with the aim to boost productivity and efficiency is provided. Our solution is based on map-matching methods, that are used to track the path spanned by a worker along a specific activity in an agriculture culture. Two different cultures are taken into consideration in this study — olives and vines. We leverage the symmetry of the geometry of these cultures into our solution and divide the problem three-fold — initially, we estimate a path of a worker along the fields, then we apply the map-matching to such path and finally, a post-processing method is applied to ensure local continuity of the sequence obtained from map-matching. The proposed methods are experimentally evaluated using synthetic and real data in the region of Mirandela, Portugal. Evaluation metrics show that results for synthetic data are robust under several sampling periods, while for real-world data, results for the vine culture are on par with synthetic, and for the olive culture performance is reduced. [Display omitted] • Path-finding methods proposal for topology estimation on agriculture fields. • Post-processing methods proposal to ensure continuity from map-matching algorithms. • Proposed methods improve against baselines on olive and vine culture. [ABSTRACT FROM AUTHOR]

Abstract The optimal p-n junction structure in a state-of-the-art Cu(In,Ga)(Se,S) 2 thin-film solar module technology is investigated. For co-optimization design and path-finding, a TCAD model is developed with experimental samples. The engineerable parameters, i.e., F Ga , GGI avg , and CdS thickness, are demonstrated to play a critical role in determining the p-n junction properties such as dark current characteristics J dark (V), voltage-dependent photocurrent, localized carrier collection efficiency, and interface carrier transportation. We show the optimal Ga-grading is determined by a trade-off between the recombination loss in space charge region and the photo-carrier collection in quasi-neutral region. The optimal CdS thickness is determined by a trade-off between carrier collection efficiency, short-circuit current (J SC) loss, and J dark (V), which depends on varied Ga-profiles. Overall, thin CdS (≦10 nm) is preferred to reduce the J SC loss in accumulated Ga-profiles, while thicker CdS is preferred to enhance the carrier collection efficiency in flatter Ga-profiles. The band alignment effect on varied Cu(In,Ga)(Se,S) 2 /CdS junctions is also investigated. It is found sulfur-incorporation can suppress the V OC saturation behavior at wide bandgap. For CIGSeS absorber with SS = 20% and D P =15%, the maximum V OC of 780 mV can be achieved by co-optimized Ga-profile. Furthermore, varied Ga-profiles and CdS buffer layers are explored for pathfinding. An optimal p-n junction structure shows a relative +40% efficiency improvement from 15.5% to 21.9%. This work shows the efficiency headroom of reported CIGSeS thin-film solar module technology through co-optimized CIGSeS composition gradient and buffer layer. [ABSTRACT FROM AUTHOR]

• A reliable path finding model is proposed to minimize the fuel consumption budget. • Specified on-time arrival probability index is ensured by reliable path finding model. • A heuristic label setting algorithm is developed to exactly solve the formulated problem. • Real traffic data is applied for the applicability and efficiency verification. Transport activities are regarded as a major source of fuel consumption and CO 2 emission production. To reduce the negative impact of traffic-related CO 2 emission, this paper proposes a reliable path-finding algorithm for improving fuel efficiency in stochastic networks under the uncertainty of travel time and fuel consumption with the consideration of spatial correlation. A reliable constrained path-finding model is developed and formulated to minimize the fuel consumption budget while guaranteeing the specified on-time arrival probability. A heuristic label setting algorithm is developed to precisely solve the formulated problem. The proposed algorithm overcomes the time-consuming drawbacks of traditional path enumeration algorithms. The applicability and efficiency of the proposed algorithm are verified on real-world traffic data acquired from the Beijing and Xi'an networks in China. The experiments demonstrate that our proposed algorithm can significantly reduce fuel consumption compared to existing studies. The experiment in Beijing shows that using the proposed algorithm can reduce 0.9 kg of CO 2 emissions on average per trip compared to existing studies. [ABSTRACT FROM AUTHOR]

Background: As more and more biological reaction data become available, the full exploration of the enzymatic potential for the synthesis of valuable products opens up exciting new opportunities but is becoming increasingly complex. The manual design of multi-step biosynthesis routes involving enzymes from different organisms is very challenging. To harness the full enzymatic potential, we developed a computational tool for the directed design of biosynthetic production pathways for multi-step catalysis with in vitro enzyme cascades, cell hydrolysates and permeabilized cells. Results: We present a method which encompasses the reconstruction of a genome-scale pan-organism metabolic network, path-finding and the ranking of the resulting pathway candidates for proposing suitable synthesis pathways. The network is based on reaction and reaction pair data from the Kyoto Encyclopedia of Genes and Genomes (KEGG) and the thermodynamics calculator eQuilibrator. The pan-organism network is especially useful for finding the most suitable pathway to a target metabolite from a thermodynamic or economic standpoint. However, our method can be used with any network reconstruction, e.g. for a specific organism. We implemented a path-finding algorithm based on a mixed-integer linear program (MILP) which takes into account both topology and stoichiometry of the underlying network. Unlike other methods we do not specify a single starting metabolite, but our algorithm searches for pathways starting from arbitrary start metabolites to a target product of interest. Using a set of biochemical ranking criteria including pathway length, thermodynamics and other biological characteristics such as number of heterologous enzymes or cofactor requirement, it is possible to obtain well-designed meaningful pathway alternatives. In addition, a thermodynamic profile, the overall reactant balance and potential side reactions as well as an SBML file for visualization are generated for each pathway alternative. Conclusion: We present an in silico tool for the design of multi-enzyme biosynthetic production pathways starting from a pan-organism network. The method is highly customizable and each module can be adapted to the focus of the project at hand. This method is directly applicable for (i) in vitro enzyme cascades, (ii) cell hydrolysates and (iii) permeabilized cells. [ABSTRACT FROM AUTHOR]

Route planning is an important daily activity and has been intensively studied owing to their broad applications. Extracting the driving experience of taxi drivers to learn about the best routes and to support dynamic route planning can greatly help both end users and governments to ease traffic problems. Travel frequency representing the popularity of different road segments plays an important role in experience-based path-finding models and route computation. However, global frequency used in previous studies does not take into account the dynamic space-time characteristics of origins and destinations and the detailed travel frequency in different directions on the same road segment. This paper presents the space-time trajectory cube as a framework for dividing and organizing the trajectory space in terms of three dimensions (origin, destination, and time). After that, space-time trajectory cube computation and origin-destination constrained experience extraction methods are proposed to extract the fine-grained experience of taxi drivers based on a dataset of real taxi trajectories. Finally, space-time constrained graph was generated by merging drivers’ experience with the road network to compute optimal routes. The framework and methods were implemented using a taxi trajectory dataset from Shenzhen, China. The results show that the proposed methods effectively extracted the driving experience of the taxi drivers and the entailed trade-off between route length and travel time for routes with high trajectory coverage. They also indicate that road segment global frequency is not appropriate for representing driving experience in route planning models. These results are important for future research on route planning or path finding methods and their applications in navigation systems. [ABSTRACT FROM AUTHOR]

Teeth are some of the most resilient tissues of the human body. Because of their placement, teeth often yield intact indicators even when other metrics, such as finger prints and DNA, are missing. Forensics on dental identification is now mostly manual work which is time and resource intensive. Systems for automated human identification from dental X-ray images have the potential to greatly reduce the necessary efforts spent on dental identification, but it requires a system with high stability and accuracy so that the results can be trusted. This paper proposes a new system for automated dental X-ray identification. The scheme extracts tooth and dental work contours from the X-ray images and uses the Hausdorff-distance measure for ranking persons. This combination of state-of-the- art approaches with a novel lowest cost path-based method for separating a dental X-ray image into individual teeth, is able to achieve comparable and better results than what is available in the literature. The proposed scheme is fully functional and is used to accurately identify people within a real dental database. The system is able to perfectly separate 88.7% of the teeth in the test set. Further, in the verification process, the system ranks the correct person in top in 86% of the cases, and among the top five in an astonishing 94% of the cases. The approach has compelling potential to significantly reduce the time spent on dental identification. [ABSTRACT FROM AUTHOR]

Path-finding can become an important bottleneck as both the size of the virtual environments and the number of agents navigating them increase. It is important to develop techniques that can be efficiently applied to any environment independently of its abstract representation. In this paper we present a hierarchical NavMesh representation to speed up path-finding. Hierarchical path-finding ( HPA ⁎ ) has been successfully applied to regular grids, but there is a need to extend the benefits of this method to polygonal navigation meshes. As opposed to regular grids, navigation meshes offer representations with higher accuracy regarding the underlying geometry, while containing a smaller number of cells. Therefore, we present a bottom-up method to create a hierarchical representation based on a multilevel k-way partitioning algorithm ( MLkP ), annotated with sub-paths that can be accessed online by our Hierarchical NavMesh Path-finding algorithm ( HNA ⁎ ). The algorithm benefits from searching in graphs with a much smaller number of cells, thus performing up to 7.7 times faster than traditional A ⁎ over the initial NavMesh. We present results of HNA ⁎ over a variety of scenarios and discuss the benefits of the algorithm together with areas for improvement. [ABSTRACT FROM AUTHOR]

Since searching is one of the most important problem-solving methods, especially in Artificial Intelligence where it is often difficult to devise straightforward solutions, it has been given continuous attention by researchers. In this paper a new algorithm for agent path-finding is presented. Our approach is based on environment marking during exploration. We tested the performances of Q-learning and Learning Real-Time A* algorithm for three proposed mazes and then a comparison was made between our algorithm, two variants of Q-learning and LRTA* algorithm.

The formulation of pedestrian floor field cellular automaton models is generally based on hypothetical assumptions to represent reality. This paper proposes a novel methodology to calibrate these models using experimental trajectories. The methodology is based on likelihood function optimization and allows verifying whether the parameters defining a model statistically affect pedestrian navigation. Moreover, it allows comparing different model specifications or the parameters of the same model estimated using different data collection techniques, e.g. virtual reality experiment, real data, etc. The methodology is here implemented using navigation data collected in a Virtual Reality tunnel evacuation experiment including 96 participants. A trajectory dataset in the proximity of an emergency exit is used to test and compare different metrics, i.e. Euclidean and modified Euclidean distance, for the static floor field. In the present case study, modified Euclidean metrics provide better fitting with the data. A new formulation using random parameters for pedestrian cellular automaton models is also defined and tested. [ABSTRACT FROM AUTHOR]

Purpose – The purpose of this paper is to propose a path-finding algorithm to solve problems with an arbitrary load-displacement relationship which results from geometrical and material nonlinear models to simulate e.g. timber structures realistically. Design/methodology/approach – A method using combined load and displacement control for the Newton method along with path-characterising measures and sub-incremention is introduced. A path-related stiffness measure is used to identify the situation when it is necessary to select the displacement control and chose the best degree of freedom as a parameter instead of the load factor. The nonlinearity index extracts information about the convergence behaviour during one incremental step. Together with the reduction of the load increments it avoids leaving the equilibrium path. Findings – The method is discussed based on numerical examples with highly nonlinear behaviour. It is capable to solve systems with decreasing load capacity and snap-back effects. Originality/value – The algorithm combines load and displacement control and adaptively choses the method and the corresponding degree of freedom and cares for reliable path following. [ABSTRACT FROM AUTHOR]

Path-finding is a fundamental problem in many applications, such as robot control, global positioning system and computer games. Since A * is time-consuming when applied to large maps, some abstraction methods have been proposed. Abstractions can greatly speedup on-line path-finding by combing the abstract and the original maps. However, most of these methods do not consider obstacle distributions, which may result in unnecessary storage and non-optimal paths in certain open areas. In this paper, a new abstract graph-based path-finding method named Genetic Convex A * is proposed. An important convex map concept which guides the partition of the original map is defined. It is proven that the path length between any two nodes within a convex map is equal to their Manhattan distance. Based on the convex map, a fitness function is defined to improve the extraction of key nodes; and genetic algorithm is employed to optimize the abstraction. Finally, the on-line refinement is accelerated by Convex A *, which is a fast alternative to A * on convex maps. Experimental results demonstrated that the proposed abstraction generated by Genetic Convex A *guarantees the optimality of the path whilst searches less nodes during the on-line processing. [ABSTRACT FROM AUTHOR]

Abstract: In a role-playing game, finding optimal trajectories is one of the most important tasks. In fact, the strategy decision system becomes a key component of a game engine. Determining the way in which decisions are taken (e.g. online, batch or simulated) and the consumed resources in decision making (e.g. execution time, memory) will influence, to a major degree, the game performance. When classical search algorithms such as A ∗ can be used, they are the very first option. Nevertheless, such methods rely on precise and complete models of the search space so there are many interesting scenarios where its application is not possible, and hence, model free methods for sequential decision making under uncertainty are the best choice. In this paper, we propose a heuristic planning strategy to incorporate, into a Dyna agent, the ability of heuristic-search in path-finding. The proposed Dyna- algorithm selects branches more likely to produce outcomes than other branches, just as A ∗ does. However, unlike A ∗, it has the advantages of a model-free online reinforcement learning algorithm. We evaluate our proposed algorithm against the one-step Q-learning and Dyna-Q algorithms and found that the Dyna-, with its advantages, produced clearly superior results. [Copyright &y& Elsevier]

Abstract: In this work, we describe a simple and powerful method to implement real-time multi-agent path-finding on Graphics Processor Units (GPUs). The technique aims to find potential paths for many thousands of agents, using the A* algorithm and an input grid map partitioned into blocks. We propose an implementation for the GPU that uses a search space decomposition approach to break down the forward search A* algorithm into parallel independently forward sub-searches. We show that this approach fits well with the programming model of GPUs, enabling planning for many thousands of agents in parallel in real-time applications such as computer games and robotics. The paper describes this implementation using the Compute Unified Device Architecture programming environment, and demonstrates its advantages in GPU performance compared to GPU implementation of Real-Time Adaptive A*. [Copyright &y& Elsevier]

Abstract: Optimal paths computed by conventional path-planning algorithms are usually not “optimal” since realistic traffic information and local road network characteristics are not considered. We present a new experiential approach that computes optimal paths based on the experience of taxi drivers by mining a huge number of floating car trajectories. The approach consists of three steps. First, routes are recovered from original taxi trajectories. Second, an experiential road hierarchy is constructed using travel frequency and speed information for road segments. Third, experiential optimal paths are planned based on the experiential road hierarchy. Compared with conventional path-planning methods, the proposed method provides better experiential optimal path identification. Experiments demonstrate that the travel time is less for these experiential paths than for paths planned by conventional methods. Results obtained for a case study in the city of Wuhan, China, demonstrate that experiential optimal paths can be flexibly obtained in different time intervals, particularly during peak hours. [Copyright &y& Elsevier]

With the progress of IT and mobile positioning technologies, various types of location-based services (LBS) have been proposed and implemented. Finding a shortest path between two nodes is one of the most fundamental tasks in many LBS related applications. So far, there have been many research efforts on the shortest path finding problem. For instance, A* algorithm estimates neighboring nodes using a heuristic function and selects minimum cost node as the closest one to the destination. Pruning method, which is known to outperform the A* algorithm, improves its routing performance by avoiding unnecessary exploration in the search space. For pruning, shortest paths for all node pairs in a map need to be pre-computed, from which a shortest path container is generated for each edge. The container for an edge consists of all the destination nodes whose shortest path passes through the edge and possibly some unnecessary nodes. These containers are used during routing to prune unnecessary node visits. However, this method shows poor performance as the number of unnecessary nodes included in the container increases. In this paper, we focus on this problem and propose a new border line-based pruning scheme for path routing which can reduce the number of unnecessary node visits significantly. Through extensive experiments on randomly-generated, various complexity of maps, we empirically find out optimal number of border lines for clipping containers and compare its performance with other methods. [ABSTRACT FROM AUTHOR]

We argue that A*, the popular technique for path-finding for NPCs in games, suffers from three limitations that are pertinent to game worlds: (a) the grid maps often restrict the optimality of the paths, (b) A* paths exhibit wall-hugging behavior, and (c) optimal paths are more predictable. We present a new algorithm, VRA*, that varies map-resolution as needed, and repeatedly calls A*. We also present an extension of an existing post-smoothing technique, and show that these two techniques together produce more realistic looking paths than A*, that overcome the above limitations, while using significantly less memory and time than A*. [ABSTRACT FROM AUTHOR]

Abstract: Swarm robotics, active self-assembly, and amorphous computing are fields that focus on designing systems of large numbers of small, simple components that can cooperate to complete complex tasks. Many of these systems are inspired by biological systems, and all attempt to use the simplest components and environments possible, while still being capable of achieving their goals. The canonical problems for such biologically-inspired systems are shape assembly and path finding. In this paper, we demonstrate path finding in the well-studied tile assembly model, a model of molecular self-assembly that is strictly simpler than other biologically-inspired models. As in related work, our systems function in the presence of obstacles and can be made fault-tolerant. The path-finding systems use distinct components and find minimal-length paths in time linear in the length of the path. [Copyright &y& Elsevier]

Learning how biological systems solve problems could help to design new methods of computation. Information processing in simple cellular organisms is interesting, as they have survived for almost 1 billion years using a simple system of information processing. Here we discuss a well-studied model system: the large amoeboid Physarum plasmodium. This amoeba can find approximate solutions for combinatorial optimization problems, such as solving a maze or a shortest network problem. In this report, we describe problem solving by the amoeba, and the computational methods that can be extracted from biological behaviors. The algorithm designed based on Physarum is both simple and useful. [ABSTRACT FROM AUTHOR]

Abstract: We have proposed a mathematical model for the adaptive dynamics of the transport network in an amoeba-like organism, the true slime mold Physarum polycephalum. The model is based on physiological observations of this species, but can also be used for path-finding in the complicated networks of mazes and road maps. In this paper, we describe the physiological basis and the formulation of the model, as well as the results of simulations of some complicated networks. The path-finding method used by Physarum is a good example of cellular computation. [Copyright &y& Elsevier]

Abstract: Many functions on context-free languages can be expressed in the form of the least fixed point of a function whose definition mimics the grammar of the given language. Examples include the function returning the length of the shortest word in a language, and the function returning the smallest number of edit operations required to transform a given word into a word in a language. This paper presents the basic theory that explains when a function on a context-free language can be defined in this way. It is shown how the theory can be applied in a methodology for programming the evaluation of such functions. Specific results include a novel definition of a regular algebra focusing on the existence of so-called “factors”, and several constructions of non-trivial regular algebras. Several challenging problems are given as examples, some of which are old and some of which are new. [Copyright &y& Elsevier]

We were recently asked to evaluate the Footprint-to-Pathfinder1 path-finding implementation for possible reuse in OneSAF Objective System. The Footprint-to-Pathfinder path-finding code implements a variation of an algorithm described by Nils Nilsson called the A Algorithm. The A Algorithm can guarantee the optimal, lowest cost path between two points when it uses an “admissible” evaluation function. It is then called the A* (A-Star) Algorithm. The Footprint-to-Pathfinder implementation uses a simplification to the A Algorithm that preserves optimality when a particular condition exists. The condition that enables the simplification—the monotone restriction—is neither well known nor explained with most references for the A Algorithm. In fact, most references imply that an admissible evaluation function is sufficient. However, there are admissible evaluation functions that will cause the simplified implementation to return a path that is sub-optimal. OneSAF Objective System does not restrict admissible evaluation functions as Footprint-to-Pathfinder does. Thus the simplified algorithm is inappropriate for the OneSAF Objective System. Because the monotone restriction is not well publicized, this paper describes it in the context of path finding for combat simulations. [ABSTRACT FROM PUBLISHER]

This paper deals with an efficient parallel and distributed framework for intensive computation with A* algorithm based on MapReduce concept. The A* algorithm is one of the most popular graph traversal algorithm used in route guidance. It requires exponential time computation and very costly hardware to compute the shortest path on large-scale networks. Thus, it is necessary to reduce the time complexity while exploiting a low cost commodity hardwares. To cope with this situation, we propose a novel approach that reduces the A* algorithm into a set of Map and Reduce tasks for running the path computation on Hadoop MapReduce framework. An application on real road networks illustrates the feasibility and reliability of the proposed framework. The experiments performed on a 6-node Hadoop cluster proves that the proposed approach outperforms A* algorithm and achieves significant gain in terms of computation time. [ABSTRACT FROM AUTHOR]