Shortest Path Solvers. From Software to Wetware

The edges of a graph are assigned weights and passage times which are assumed to be positive integers. We present a parallel algorithm for finding the shortest path whose total weight is smaller than a pre-determined value. In each step the processing elements are not analyzing the entire graph. Instead they are focusing on a subset of vertices called active vertices. The set of active vertices at time t is related to the boundary of the ball \(B_t\) of radius t in the first passage percolation metric. Although it is believed that the number of active vertices is an order of magnitude smaller than the size of the graph, we prove that this need not be the case with an example of a graph for which the active vertices form a large fractal. We analyze an OpenCL implementation of the algorithm on GPU for cubes in \(\mathbb Z^d\).

The gathering problem has been largely studied in the last years with respect to different environments. The requirement is to move a team of robots initially placed at different locations toward a common point. Robots move based on the so called Look-Compute-Move model. Each time a robot wakes up, it perceives the current configuration in terms of robots’ positions (Look), it decides whether and where to move (Compute), and makes the computed move (Move) in the case that the decision was affirmative. All the phases are performed asynchronously for each robot. Robots are oblivious, anonymous, silent, and execute the same distributed and deterministic algorithm. So far, the goal has been mainly to detect the minimal assumptions that allow to accomplish the gathering task, without taking care of any cost measure of the provided solutions. We provide an overview of recent results that first extend the classic notion of optimization problem to the context of robot-based computing systems, and then show that the gathering problem can be optimally solved. As cost measure, the overall traveled distance performed by all robots is considered. This implies that the provided optimal algorithms must be able to solve the gathering by moving robots through shortest paths. The presented optimal algorithms refer to robots moving on either the plane or graphs. In the latter case, different topologies are considered, like trees, rings, and infinite grids.

The number of hops (or arcs) of a path is a frequent objective function with applications to problems where network resources utilization is to be minimized. In this chapter we solve bicriteria path problems involving this objective function and two other common metrics, the path cost and the path capacity. Labeling algorithms are introduced, which use a breadth-first search tree in order to compute the maximal and the minimal sets of non-dominated paths. Dominance rules are derived for the two bicriteria problems and the properties of this data structure are explored to better suit the number of hops objective function and thus simplify the labeling process. Computational experiments comparing the new methods with standard approaches on randomly generated test instances and on instances that simulate video traffic are presented and discussed. Results show a significant speed-up over generic standard methods.

Computing and updating distributed shortest paths is a core functionality of today’s communication networks. The solutions known in the literature are classified into two categories, namely Distance-Vector and Link-State algorithms. Distance-Vector algorithms usually require each node of the network to store the distance toward every other node in a data structure called routing table, thus requiring linear storage per node. Such a data structure is used to compute the next hop to be used to forward data toward any destination node of interest. This is usually done by solving very simple equations, thus requiring few computational time per node. The main drawback of Distance-Vector algorithms is that, in dynamic scenarios, they can suffer of the looping and count-to-infinity phenomena, though quite efficient countermeasures for such issues are known. Link-State algorithms, instead, require a node of the network to know and store the entire network topology, to compute its distance and next hop toward any destination. This is usually done by means of a centralized shortest-path algorithm, hence requiring quadratic storage and rather high computational effort per node. The main drawback of Link-State algorithms is that, notwithstanding they do not incur in looping and count-to-infinity problems, they perform quite poorly in dynamic scenarios, since nodes need to receive and store up-to-date information on the entire network topology after each change. In the last years, there has been a renewed interest in devising new light-weight distributed shortest-path solutions for large-scale Ethernet networks, where Distance-Vector algorithms are an attractive alternative to Link-State solutions when scalability and reliability are key issues or when the memory resources of the nodes of the network are limited. In this chapter, we hence focus on Distance-Vector solutions by reviewing classic approaches and recent algorithmic developments in this category.

We propose a Parallel Multi-Start Multiobjective Influenza Virus Algorithm (PMS-MOIVA) for the solution of the Multiobjective Energy Reduction Open Vehicle Routing Problem. The PMS-MOIVA could be categorized in the Artificial Immune System algorithms, as it simulates the process of annual evolution of influenza virus in an isolated human population. Two different versions of the algorithm are presented where their main difference is the fact that in the first version, PMS-MOIVA1, the algorithm focuses on the improvement of the most effective solutions using a local search procedure while in the second version, PMS-MOIVA2, the use of the local search procedure is applied equally in the whole population. In order to prove the effectiveness of the proposed algorithm a comparison is performed with the Parallel Multi-Start Non-dominated Sorting Genetic Algorithm II (PMS-NSGA II). The Multiobjective Energy Reduction Open Vehicle Routing Problem has two different objective functions, the first corresponds to the optimization of the total travel time and the second corresponds to the minimization of the fuel consumption of the vehicle taking into account the travel distance and the load of the vehicle when the decision maker plans delivery. A number of modified Vehicle Routing Problem instances are used in order to evaluate the quality of the proposed algorithm.

We study practical algorithms for solving the all-pairs shortest path problem. The Floyd-Warshall algorithm is frequently used to solve the aforementioned problem, and we show how it can be augmented to drastically reduce the number of path combinations examined. Very favorable results are shown via empirical tests that compare the new algorithm with known algorithms on random graphs. In addition to the all-pairs shortest path problem, we also investigate the highly related all-pairs bottleneck paths problem, and give an efficient average case algorithm. On top of that, we show how the bottleneck paths problem relates to the decremental transitive closure problem, and specifically how algorithms for the latter can be used to solve the former.

We describe cellular-automaton-based algorithms for solving two shortest path problems on arbitrary connected, directed, and weighted graphs with n vertices. The first problem is that of finding the shortest path from a given vertex to another given vertex of the graph. A two-dimensional cellular automaton, shaped as a triangle, with \(O(n^2)\) cells, is used. The algorithm runs in O(n) time. The second problem requires that all shortest paths between pairs of vertices be obtained. An \(n \times n\) cellular automaton solves the problem in \(O(n \log n)\) time.

Cellular Automata (CAs) are computational models that can capture the essential features of systems in which global behavior emerges from the collective effect of simple components, which interact locally. During the last decades, CAs have been extensively used for mimicking several natural processes and systems to find fine solutions in many complex hard to solve computer science and engineering problems. Among them, the shortest path problem is one of the most pronounced and highly studied problems that scientists have been trying to tackle by using a plethora of methodologies and even unconventional approaches. The proposed solutions are mainly justified by their ability to provide a correct solution in a better time complexity than the renowned Dijkstra’s algorithm. Although there is a wide variety regarding the algorithmic complexity of the algorithms suggested, spanning from simplistic graph traversal algorithms to complex nature inspired and bio-mimicking algorithms, in this chapter we focus on the successful application of CAs to shortest path problem as found in various diverse disciplines like computer science, swarm robotics, computer networks, decision science and biomimicking of biological organisms’ behaviour. In particular, an introduction on the first CA-based algorithm tackling the shortest path problem is provided in detail. After the short presentation of shortest path algorithms arriving from the relaxization of the CAs principles, the application of the CA-based shortest path definition on the coordinated motion of swarm robotics is also introduced. Moreover, the CA based application of shortest path finding in computer networks is presented in brief. Finally, a CA that models exactly the behavior of a biological organism, namely the Physarum’s behavior, finding the minimum-length path between two points in a labyrinth is given. The CA-based model results are found in very good agreement with the computation results produced by the in-vivo experiments especially when combined with truly parallel implementations of this CA in a Field Programmable Gate Array (FPGA) and on a Graphical Processing Unit (GPU). The presented implementations succeed to take advantage of the CA’s inherit parallelism and significantly improve the performance of the CA algorithm when compared with software in terms of computational speed and power consumption.

Considered is a multi-agent system with agents, modeled by Cellular Automata. The agents have the task to form a checkerboard (CB) pattern on an \(n \times n\) square field. The objective is to find the behavior (an algorithm) for the agents (realized by finite state automata, or finite state machines FSM), which can solve this task in shortest time, i.e. moving on a shortest path (space filling curve) for a single agent system. The target pattern class can be described by local matching patterns (\(3 \times 3\) templates). The degree of order is the number of template hits. Our goal is to find perfect CB patterns with a maximum degree of order. Firstly, a single-agent algorithm G1 with four states is designed, where the agent starts in a corner. The agent walks on a shortest path, but needs some additional steps to turn to a free direction when sensing a border. Secondly, FSM algorithms for multi-agent systems are evolved (found) by a Genetic Algorithm for an 8 \(\times \) 8 field. Now the agents may start at any random position. Optionally an agent can emit a signal which can be sensed by another nearby agent. This signal was introduced to speedup the task. The evolved single-agent FSM algorithm uses another strategy than G1, a spiral-like trajectory. The fully packed system with 64 agents is the fastest, but it is also the most costly one, in terms of the product (time-steps \(\times \) number of agents).

Ant Colony Optimization (ACO) is a widespread optimization technique used to solve complex problems in a broad range of fields, including engineering, software development and logistics. It was inspired by the behaviour of ants which can collectively select the shorter of two paths leading to a food source. They are able to do so even without any single ant comparing the lengths of the two paths. Ants, like other eusocial insects, have no central authority to coordinate the sophisticated and complex work of their colony members. Coordination is achieved through self-organization, principles of which inspired the development of ACO algorithms. Here we discuss both the similarities and the considerable differences between the behaviour of real ant colonies and techniques used by ACO. We also describe some of the latest findings in ant research and how they may contribute to new ACO algorithms.

In this chapter, we introduce a mathematical model inspired by slime mould Physarum polycephalum, an amoeboid organism that exhibits phenomenal path-finding behavior. By comparing it to one of the classic shortest path algorithms—Dijkstra algorithm, we highlight and summarize the key characteristics that are unique in Physarum algorithm, namely flow continuity and adaptivity. Due to these features, the Physarum model responses autonomously to the changes of external environment, thereby converging to optimal solutions adaptively. Herein, we take advantage of its superior properties and develop various models to address several significant network optimization problems, including traffic flow assignment and supply chain network design. By comparing its performance with the state-of-the-art methods in terms of solution quality and running time, we demonstrate the efficiency of the proposed algorithms.

Moving cells have surprising abilities to navigate efficiently through complex microscale human-engineered mazes. Most often, they follow chemical gradients established by diffusion from a source to a sink. Cells steer towards the steepest gradients and move along the shortest paths towards the source. Occasionally, the gradients are self-generated by the moving cells themselves. While the cells also respond to the same gradients they create, a self-sustained loop is established, which guides the cells towards the shortest path towards exit from confined spaces. Precision measurements of human cell maze-navigation performance could ultimately enhance our capabilities to diagnose, monitor, and treat various diseases that range from inflammation to cancer.

Shortest path problems are a touchstone for evaluating the computing performance and functional range of novel computing substrates. Much has been published in recent years regarding the use of biocomputers to solve minimal path problems such as route optimisation and labyrinth navigation, but their outputs are typically difficult to reproduce and somewhat abstract in nature, suggesting that both experimental design and analysis in the field require standardising. This chapter details laboratory experimental data which probe the path finding process in two single-celled protistic model organisms, Physarum polycephalum and Paramecium caudatum, comprising a shortest path problem and labyrinth navigation, respectively. The results presented illustrate several of the key difficulties that are encountered in categorising biological behaviours in the language of computing, including biological variability, non-halting operations and adverse reactions to experimental stimuli. It is concluded that neither organism examined are able to efficiently or reproducibly solve shortest path problems in the specific experimental conditions that were tested. Data presented are contextualised with biological theory and design principles for maximising the usefulness of experimental biocomputer prototypes.

Maze solving and finding the shortest path or all possible exit paths in mazes can be interpreted as mathematical problems which can be solved algorithmically. These algorithms can be used by both living entities (such as humans, animals, cells) and non-living systems (computer programs, simulators, robots, particles). In this chapter we summarize several chemistry-based concepts for maze solving in two-dimensional standard mazes which rely on surface tension driven phenomena at the air-liquid interface. We show that maze solving can be implemented by using: (i) active (self-propelled) droplets and/or (ii) passive particles (chemical entities).

A physical method to solve a maze using an electric circuit is presented. The temperature increase due to Joule heating is observed with a thermal camera and the correct path is instantaneously enlightened. Various mazes are simulated with Kirchhoff’s circuit laws. Finally, the physical mechanisms explaining how the electric current chooses the correct path are discussed.

There is a growing interest towards implementation of maze solving in spatially-extended physical, chemical and living systems. Several reports of prototypes attracted great publicity, e.g. maze solving with slime mould and epithelial cells, maze navigating droplets. We show that most prototypes utilise one of two phenomena: a shortest path in a maze is a path of the least resistance for fluid and current flow, and a shortest path is a path of the steepest gradient of chemoattractants. We discuss that substrates with so-called maze-solving capabilities simply trace flow currents or chemical diffusion gradients. We illustrate our thoughts with a model of flow and experiments with slime mould. The chapter ends with a discussion of experiments on maze solving with plant roots and leeches which show limitations of the chemical diffusion maze-solving approach.