Search
Filters
total: 14
filtered: 13
Chosen catalog filters
Search results for: PATH FINDING
-
Finding small-width connected path decompositions in polynomial time
PublicationA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Experimental research on evolutionary path planning algorithm with fitness function scaling for collision scenarios
PublicationThis article presents typical ship collision scenarios, simulated using the evolutionary path planning system and analyses the impact of the fitness function scaling on the quality of the solution. The function scaling decreases the selective pressure, which facilitates leaving the local optimum in the calculation process and further exploration of the solution space. The performed investigations have proved that the use of scaling...
-
Generating optimal paths in dynamic environments using RiverFormation Dynamics algorithm
PublicationThe paper presents a comparison of four optimisation algorithms implemented for the purpose of finding the shortest path in static and dynamic environments with obstacles. Two classical graph algorithms –the Dijkstra complete algorithm and A* heuristic algorithm – were compared with metaheuristic River Formation Dynamics swarm algorithm and its newly introduced modified version. Moreover, another swarm algorithm has been compared...
-
Client-server Approach in the Navigation System for the Blind
PublicationThe article presents the client‐server approach in the navigation system for the blind ‐ “Voice Maps”. The authors were among the main creators of the prototype and currently the commercialization phase is being finished. In the implemented prototype only exemplary, limited spatial data were used, therefore they could be stored and analysed (for path-finding process) in the mobile device’s memory without any difficulties. The...
-
Efficiency of service recovery in scale-free optical networks under multiple node failures
PublicationIn this paper we examine the properties of scale-free networks in case of simultaneous failures of two networknodes. Survivability assumptions are as follows: end-to-end path protection with two node-disjoint backup pathsfor each working path. We investigate three models of scale-free networks generation: IG, PFP and BA.Simulations were to measure the lengths of active and backup paths and the values of service recovery time.We...
-
Evolutionary Algorithms in MPLS network designing
PublicationMPLS technology become more and more popular especially in core networks giving great flexibility and compatibility with existing Internet protocols. There is a need to optimal design such networks and optimal bandwidth allocation. Linear Programming is not time efficient and does not solve nonlinear problems. Heuristic algorithms are believed to deal with these disadvantages and the most promising of them are Evolutionary Algorithms....
-
Behaviometrics of Digital Games for Children with Autism Spectrum Disorder
PublicationTe paper reports current stage of the project Automated Terapy Monitoring for Children with Developmental Disorders of Autism Spectrum (AUTMON), that aims at development of methods and tools to allow for the automatic evaluation of the therapy progress among children with autism. Finding objective measures suitable for evaluating therapy progress would let create a system supporting those who diagnose autism and the therapists...
-
THE EFFECT OF LOG SORTING STRATEGY ON THE FORECASTED LUMBER VALUE AFTER SAWING PINE WOOD
PublicationThe optimal transformation path for the resource is determined by the quality of a log combined with its dimension. The commercial value of derived products is also closely connected with the size and extent of containing wood deficiencies. The results of studies with three diverse strategies for log sorting are presented in the paper. Resource assessment by a worker without extensive experience in sorting logs, the certified grading...
-
Thermal Image Processing for Respiratory Estimation from Cubical Data with Expandable Depth
PublicationAs healthcare costs continue to rise, finding affordable and non-invasive ways to monitor vital signs is increasingly important. One of the key metrics for assessing overall health and identifying potential issues early on is respiratory rate (RR). Most of the existing methods require multiple steps that consist of image and signal processing. This might be difficult to deploy on edge devices that often do not have specialized...
-
An Efficient Noisy Binary Search in Graphs via Median Approximation
PublicationConsider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a strategy, that identifies an initially unknown target vertex in a graph by asking queries. Each query is conducted as follows: the strategy selects a vertex q and receives a reply v: if q is the target, then =, and if q is not the target, then v is a...
-
Minimizing Greenhouse Gas Emissions From Ships Using a Pareto Multi-Objective Optimization Approach
PublicationTo confront climate change, decarbonization strategies must change the global economy. According to statements made as part of the European Green Deal, maritime transport should also become drastically less polluting. As a result, the price of transport must reflect the impact it has on the environment and on health. In such a framework, the purpose of this paper is to suggest a novel method for minimizing emissions...
-
On Tradeoffs Between Width- and Fill-like Graph Parameters
PublicationIn this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...
-
Sailing Vessel Routing Considering Safety Zone and Penalty Time for Altering Course
PublicationIn this paper we introduce new model for simulation sea vessel routing. Besides a vessel types (polar diagram) and weather forecast, travel security and the number of maneuvers are considered. Based on these data both the minimal travelling costs and the minimal processing time are found for different vessels and different routes. To test our model the applications SailingAssistance wad improved. The obtained results shows that...