Fuel efficiency is an ever present problem in today's modern world. The United States in particular is in need of a solution to lowering greenhouse gas emissions caused by transit and freight across its spread out cities. In fact in the United States the average commute time of an individual is 26 minutes, meaning that round trip people are driving about an hour every day, to and from work. But that gas consumption is pittiling compared to that of the freight industry. Heavy Duty Vehicles (HDVs) commonly known as semi trucks, account for three quarters of US freight emissions and 7.5% of total US greenhouse gas emissions [2]. But this can be cut down considerably with the implementation of platooning. Platooning is when multiple vehicles follow in close distance to reduce aerodynamic drag, causing significant fuel savings. In this paper, we will go over an algorithm to help vehicles join with already formed platoons on the road, increasing their fuel efficiency and therefore saving cost to the driver in addition to lessening the negative effect on the planet. This will be done using a modified A* algorithm. The base weight of zero will be the amount of gas the vehicle would consume taking the shortest path that google maps recommends, alone, with no platooning. Paths may end up with negative weights due to the fuel savings caused by joining existing platoons during the vehicles’ travel. The algorithm will have access to a map of the roadways and the GPS data of nearby platoons. It will then perform a cost-benefit analysis to determine if the fuel savings from joining a platoon will outweigh the cost of going outside of its original path in order to join the other vehicles.

The zebrafish neuromuscular system is an elegant model to study neural development. To reveal a specific programme for zebrafish motor axon pathfinding I established a method to selectively block motor axon pathfinding by interfering with LIM domain transcription factor signaling. LIM homeodomain proteins (LIM-HDs) are an important class of transcriptional regulators and involved in neural development as well as neuron fate decision in vertebrates. DD domain dimerization of CLIM (cofactor of LIM-HDs) can activate LIM-HDs and downstream gene transcription while over-expression of dominant-negative CLIM (DN-CLIM), which lacks the DD domain, blocks LIM-HD activity. Motor neurons fluoresce in HB9:GFP transgenic zebrafish as the promoter of the motor neuron specific gene Hb9 drives expression of GFP. Motor axons in DN-CLIM injected HB9:GFP zebrafish are unable to exit the spinal cord, instead they grow inside the spinal cord. Thus axon pathfinding, but not general growth appears to be impaired in these neurons. This provides an excellent research model to find genes involved in motor axon pathfinding downstream of LIM-HDs. Gene array expression profiling was carried out on GFP+ motor neurons by fluorescence-activated flow sorting (FACS) with and without prior injection of DN-CLIM mRNA to elucidate the potential genes relevant to motor axon pathfinding. Genes that were most strongly down-regulated in DN-CLIM injected embryos were considered to belong to a motor axon specific guidance programme. Calca, tac-1 and chodl genes, retrieved from the gene array data, showed specific expression pattern in motor neuron and obvious down-regulation after DN-CLIM injection by in situ hybridization. This validated the array results. Chodl contains a C-type lectin domain representing a potential cell surface receptor for guidance factors. Gene knock-down experiments with two independent morpholinos led to stalling of CaP motor axons at the horizontal myoseptum, a pivotal choice point for axon pathfinding. This suggests that this novel gene specifically affects motor axon pathfinding in zebrafish. Single stranded DNA binding protein 1 (SSDP1) functions as an activator of SSDP1/CLIM/LIM-HD complex which involved in the transcriptional control of embryonic development. To verify how SSDP1 function in neural development in zebrafish, I have cloned Zebrafish SSDP1a and SSDP1b, which are most closely related to mouse and human SSDP1. SSDP1a is widely expressed during zebrafish development while SSDP1b is specifically expressed in sensory trigeminal and Rohon-Beard neurons. Over-expression of the N-terminal portion of SSDP1 (N-SSDP1) increases endogenous CLIM protein levels in vivo and impairs the formation of eyes and midbrain-hindbrain boundary. In addition, SSDP1b knock down impairs trigeminal and Rohon-Beard sensory axon growth. N-SSDP1 can partially rescue the inhibition of axon growth induced by DN-CLIM. These results reveal specific functions of SSDP1 in neural patterning and sensory axon growth which are in part due to the stabilization of LIM-HD/CLIM complexes. In summary, co-factors of LIM-HDs play important roles in neural development, cell fate specification as well as axon pathfinding.

Title: Pathfinding within a Hierarchical Navmesh Based on Geometry Analysis Author: Miroslav Chomut Department / Institute: Department of Software and Computer Science Education Supervisor of the master thesis: Mgr. Tomáš Plch, Media and Communications Office Abstract: Pathfinding is a common problem in the computer science dealing with navigation from a starting point to a destination point. Common algorithms today are mostly based on A* search on a graph representation of navigated world. Another common approach is creation of navigation structure of convex navigation meshes and navigating on them. Our goal is to propose pathfinding algorithm on hierarchical navigation meshes, based on the terrain geometry, which benefits from complexity of hierarchical search yet provides paths comparable in length to reference ones. This thesis analyses and describes our proposed approach of navigation including generation of the navigation structure. Keywords: navmesh, pathfinding, A*, hierarchy, terrain analysis, geometry

Emergencies that require immediate evacuation should be encountered with effective preparedness. With over 14 billion dollars in damages and 3,000 people killed each year, fire emergency preparedness is of critical importance. Fire drills aim to prepare and educate people on how to react properly, in order to avoid as many casualties possible. Fire drills can be expensive and time consuming to conduct, and in most cases lack the level of realism to properly educate the trainees. In this thesis, a virtual reality (VR) emergency evacuation training platform is presented. With VR, we aim to eliminate the real life constraints that exist, while succesfully training individuals. The application operator can spawn fires in any desired location, and at the same time the user being trained is getting informed about the safest and fastest path available, while being provided with constant feedback. We generate a grid graph on a given floor plan to run a pathfinding algorithm. We use Linear Temporal Logic (LTL) to formulate the existing constraints in our approach.

Artificial intelligence is often used when creating believable virtual characters in games or in other types of virtual environments. The intelligent behavior these characters show to the player is often flawed, leading to a worse gameplay experience. In particular, there is often little or no emotional impact on the decision making of the characters. This thesis focuses on extending decision-making and pathfinding mechanisms for virtual characters, with a particular focus on the use of emotions. The thesis is divided into three parts. The first part is an introductory study concerning the requirements designing a believable virtual character places on the architecture used. Gameplay design patterns are used as a tool to analyze the proposed agent architecture and discussions are presented regarding the necessary properties of such an architecture with respect to gameplay. The second part extends two action selection mechanisms to include emotional impact. In particular, behavior networks are extended to take complex emotional impact into account, including emotional parameters, emotional goals, and emotional influences.Moreover, time-discounting is introduced into behavior networks as a factor in the decision making. The time-discounting is also under emotional influence. The second action selection mechanism extended to use emotional impact is behavior trees. Since behavior trees are widely used by game designers, allowing full control over the characters’ behaviors, the work in this thesis proposes a new type of emotional selector which only affects a part ofthe behavior tree, leaving the control in the hands of the designer. The third part focuses on more complex pathfinding where more factors than finding the shortest collisionfree path through an environment are considered. A new type of visibility map is introduced. Using the knowledge of the virtual character about previous enemy positions, a more accurate visibility map is created. The visibility map is used for covert pathfinding, where the character tries to find a path through an environment while trying to minimize the risk of being seen by the enemy. Finally, a new kind of pathfinding, emotional pathfinding, is introduced, based on the use of emotion maps. Humans often have emotional attachment to geographical locations because they have previously felt emotions at those locations. This approach takes advantage of this knowledge and enables a virtual character to find a path through an environment that is as emotionally pleasant as possible.

No description available.

The most basic requirement for any computer controlled game agent in a video game is to be able to successfully navigate the game environment. Pathfinding is an essential component of any agent navigation system. Pathfinding is, at the simplest level, a search technique for finding a route between two points in an environment. The real-time multi-agent nature of video games places extremely tight constraints on the pathfinding problem. This study aims to provide the first complete review of the current state of video game pathfinding both in regards to the graph search algorithms employed as well as the implications of pathfinding within dynamic game environments. Furthermore this thesis presents novel work in the form of a domain specific search algorithm for use on grid-based game maps: the spatial grid A* algorithm which is shown to offer significant improvements over A* within the intended domain. Copyright / Dissertation (MSc)--University of Pretoria, 2011. / Computer Science / unrestricted

Background. Pathfinding plays a big role in both digital games and robotics, and is used in many different ways. One of them is multi-goal pathfinding (MGPF) which is used to calculate paths from a start position to a destination with the condition that the resulting path goes though a series of goals on the way to the destination. For the most part research on this topic is sparse, and when the complexity is increased through obstacles that are introduced to the scenario, there are only a few articles in the field that relate to the problem.Objectives. The objective in this thesis is to conduct an experiment to compare four algorithms for solving the MGPF problem on six different maps with obstacles, and then analyze and draw conclusions on which of the algorithms is best suited to use for the MGPF problem. The first is the traditional Nearest Neighbor algorithm, the second is a variation on the Greedy Search algorithm, and the third and fourth are variations on the Nearest Neighbor algorithm. Methods. To reach the Objectives all the four algorithms are tested fifty times on six different maps of varying sizes and obstacle layout. Results. The data from the experiment is compiled in graphs for all the different maps, with the time to calculate a path and the path lengths as the metrics. The averages of all the metrics are put in tables to visualize the difference between the results for the four algorithms.Conclusions. The conclusions were that the dynamic version of the Nearest Neighbor algorithm has the best result if both the metrics are taken into account. Otherwise the common Nearest Neighbor algorithm gives the best results in respect to the time taken to calculate the paths and the Greedy Search algorithm creates the shortest paths of all the tested algorithms.

During nervous system development, growing axons navigate towards their targets using signals from their environment. These signals may be biochemical or mechanical in nature; however, the role of mechanical cues in axon pathfinding in vivo, and the spatiotemporal dynamics of embryonic brain mechanics, are still largely uncharacterised. Here, I have identified a role for tissue mechanics in embryonic axon guidance in vivo, using retinal ganglion cell (RGC) axon outgrowth in the developing Xenopus laevis optic tract (OT) as a model system. Using atomic force microscopy (AFM) to map brain stiffness in vivo, I found that embryonic Xenopus brain tissue was mechanically heterogeneous at both early and later stages of OT outgrowth, i.e. just before RGC axons make a stereotypical turn in the mid-diencephalon, and when they reach their target, respectively. The final path of RGC axon turning followed a clear mechanical gradient: by the later stage, tissue rostral to the OT had become stiffer than tissue caudal to it. This mid-diencephalic stiffness gradient was an intrinsic property of the underlying brain tissue, and correlated with local cell body densities (with higher density rostral to the OT and lower density caudal to it). Crucially, inhibiting cell proliferation in vivo during OT outgrowth abolished the stiffness gradient and reduced OT turning at the later stage. Next, I developed a time-lapse AFM technique to track tissue stiffness and RGC axon behaviour simultaneously in vivo. Using this approach, I followed the evolution of the mid-diencephalic stiffness gradient during intermediate developmental stages, around the time when the OT’s caudal turn is initiated. The stiffness gradient was shallow pre-turn, but increased in magnitude during axon turning (mostly due to an increase in tissue stiffness rostral to the OT). This increase in stiffness gradient preceded the rise in OT turning angle, suggesting that the stiffness gradient is not caused by the invading axons. The observed rise in stiffness gradient correlated with stage-specific increases in local cell density, and was attenuated by blocking mitosis in vivo during time-lapse AFM measurements (which also reduced OT turning). As final confirmation that brain stiffness contributes to RGC axon pathfinding, I disrupted mechanical gradients by artificially stiffening brain tissue in vivo. Importantly, global stiffening via application of transglutaminase eliminated the mid-diencephalic stiffness gradient by increasing tissue stiffness caudal of the OT, and reduced the OT turning angle. Sustained mechanical compression of small areas using an AFM probe stiffened brain locally and repelled RGC axons, consistent with the way they turned away from rapidly stiffening tissue regions during time-lapse AFM experiments. Taken together, these results are consistent with a function for tissue mechanics in axon pathfinding in vivo.

Quantum walks on graphs have been proven to be a useful tool in quantum algorithm construction for various problems. In this thesis we introduce a new type of continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. We first consider the quantum snake walk on the line. The analysis of the eigenvalues and the eigenvectors of the Hamiltonian governing the walk reveals that most states initially localized in a segment on the line always remain in that same segment. However, there are exponentially small (in the length of the snake) fraction of states which move on the line as wave packets with momentum inversely proportional to the length of the snake. Next we show how an algorithm based on the quantum snake walk might be able to solve an extended version of the glued trees problem which asks to find a path connecting both roots of the glued trees graph. No efficient quantum algorithm solving this problem is known yet. For that reason we consider a specific extension of the glued trees graph and analyze how the quantum snake walk behaves on it. In particular we show that the quantum snake walk on the infinite binary tree, restricted to certain superpositions, in many aspects is very similar to the quantum snake walk on the line. We also argue why the quantum snake walk, initialized in certain superpositions on one side of the glued trees graph, after certain amount of time is likely to be found on the other side of the graph. This seems to be crucial if we want our algorithm to work.