Dr Bart Jaworski

Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in an environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called the (edge) search strategy. Unfortunately calculating both the… Pokaż więcej

Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in an environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called the (edge) search strategy. Unfortunately calculating both the optimal search strategy and the search number is NP-hard for general graphs. Furthermore, due to the complexity of the pursuit rules, the application of heuristic solutions is not straightforward. In this paper we suggest a method of applying genetic algorithms to solve graph searching problem. The idea is based on LaPaugh's result on graph searching monotonicity and utilizes representation of a search strategy as a permutation of edges. Pokaż mniej

Genetic algorithms (GA) are a well-known tool used to obtain approximate solutions to optimization problems. Successful application of a genetic algorithm in solving given problem is largely dependant on selecting appropriate genetic operators. Selection, mutation and crossover techniques play a fundamental role in both time needed to obtain results and their accuracy. In this paper we focus on applying genetic algorithms in calculating (edge) search number and search strategy for general… Pokaż więcej

Genetic algorithms (GA) are a well-known tool used to obtain approximate solutions to optimization problems. Successful application of a genetic algorithm in solving given problem is largely dependant on selecting appropriate genetic operators. Selection, mutation and crossover techniques play a fundamental role in both time needed to obtain results and their accuracy. In this paper we focus on applying genetic algorithms in calculating (edge) search number and search strategy for general graphs. Our genetic representation of problem domain is based on representing search strategy as a permutation of edges and fitness function is based on the number of searchers needed to perform a given strategy. Our implementation of GA is utilized to compute search strategies for selected graph classes. We compare and discuss results obtained while employing different reproduction strategies. Pokaż mniej

This article compares an impact of using various selection schemes on the quality of the solution for the problem of planning the path for a moving object using the evolutionary method. In study case problem of avoiding collisions at sea is analyzed. The modelled environment includes static constraints (lands, canals, etc.) and dynamic objects (moving ships). Article analyses behaviour of selection schemes in two similar environments which differ in number of dynamic objects (highly congested… Pokaż więcej

This article compares an impact of using various selection schemes on the quality of the solution for the problem of planning the path for a moving object using the evolutionary method. In study case problem of avoiding collisions at sea is analyzed. The modelled environment includes static constraints (lands, canals, etc.) and dynamic objects (moving ships). Article analyses behaviour of selection schemes in two similar environments which differ in number of dynamic objects (highly congested areas). Research has proven that application of specific selectors improves results of study case evolutionary path planning situation. Pokaż mniej

This paper focuses on presenting the principals and early research on a modification of the Evolutionary Planner/Navigator (EP/N) system, that will introduce an agent system, that based on a hierarchy established with the help of AIS and radar, also incorporating COLREGs rules will be presenting a coordinated traffic plan for all ships in the analysed environment. The idea of this concept will be presented along with its requirements and research already undertaken. The new ahEP/N will maintain… Pokaż więcej

This paper focuses on presenting the principals and early research on a modification of the Evolutionary Planner/Navigator (EP/N) system, that will introduce an agent system, that based on a hierarchy established with the help of AIS and radar, also incorporating COLREGs rules will be presenting a coordinated traffic plan for all ships in the analysed environment. The idea of this concept will be presented along with its requirements and research already undertaken. The new ahEP/N will maintain all of the benefits of the original algorithm (such as near real time work) and will allow the coordination of safe and economic path planning between all the ships in the area overseen by the watchkeeper. Pokaż mniej

This 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 calcula-tion process and further exploration of the solution space. The performed investigations have proved that the use of scaling in the evolutionary path planning method makes it possible to… Pokaż więcej

This 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 calcula-tion process and further exploration of the solution space. The performed investigations have proved that the use of scaling in the evolutionary path planning method makes it possible to preserve the diversity of solu-tions by a larger number of generations in the exploration phase, what could result in finding better solution at the end. The problem of avoiding collisions well fitted the algorithm in question, as it easily incorporates dy-namic objects (moving ships) into its simulations, however the use scaling with this particular problem has proven to be redundant.

Side note: This paper was granted "Best paper award" on the Transnav 2011 conference. Pokaż mniej

he main goal of this present paper is to propose a structure for a tool helping to determine how algorithm would react in a real live application, by checking it’s adaptive capabilities in an extreme situation. Also a different idea of an additional genetic operator is being presented. As Genetic Algorithms are directly inspired by evolution, extinction events, which are elementary in our planet’s development history, became a foundation for those concepts.

The article analyses the impact of fitness function scaling on the quality of the solution to the problem of planning the path for a moving object using the evolutionary method. 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 in the evolutionary path planning method makes it possible to preserve the… Pokaż więcej

The article analyses the impact of fitness function scaling on the quality of the solution to the problem of planning the path for a moving object using the evolutionary method. 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 in the evolutionary path planning method makes it possible to preserve the diversity of solutions by a larger number of generations in the exploration phase. The problem of avoiding collisions at sea was selected as the test case. The modelled environment includes static constraints (lands, canals, etc.) and dynamic objects (moving ships). Pokaż mniej

This paper presents the use of mean crossover genetic operator for path planning using evolutionary algorithm for collision avoidance on sea. Mean crossover ensures widening of the possible solutions’ set that can be achieved in comparison to exchange crossover variant. The research shown, that the mean crossover allows to achieve results independent from the initial generation and quicker transition of the algorithm from the exploration to the exploitation phase. New version of the algorithm… Pokaż więcej

This paper presents the use of mean crossover genetic operator for path planning using evolutionary algorithm for collision avoidance on sea. Mean crossover ensures widening of the possible solutions’ set that can be achieved in comparison to exchange crossover variant. The research shown, that the mean crossover allows to achieve results independent from the initial generation and quicker transition of the algorithm from the exploration to the exploitation phase. New version of the algorithm allows for an effective solution search for the problem of a collision scenario on sea. Pokaż mniej

This paper presents the use of mean crossover genetic operator for path i planning using evolutionary algorithm for collision avoidance on sea. ! Mean crossover ensures widening of the possible solutions' set that can be achieved in comparison to exchange crossover variant. The research i shown, that the mean crossover allows to achieve results independent i from the initial generation and quicker transition of the algorithm from the exploration to the exploitation phase. New version of the… Pokaż więcej

This paper presents the use of mean crossover genetic operator for path i planning using evolutionary algorithm for collision avoidance on sea. ! Mean crossover ensures widening of the possible solutions' set that can be achieved in comparison to exchange crossover variant. The research i shown, that the mean crossover allows to achieve results independent i from the initial generation and quicker transition of the algorithm from the exploration to the exploitation phase. New version of the algorithm i allows for an effective solution search for the problem of a collision scenario on sea. Pokaż mniej