Search

Search Results

• ROBOT PATH PLANNING FOR MULTI-TARGETS BASED ON A HYBRID OF PRM AND AGA ALGORITHM

  Alzubairi Shaymaa М. Jawad Kadhim , А.А. Petunin , S.S. Ukolov

  6-18

  2025-11-10

  Abstract ▼

  Optimal path planning problems for mobile robots have been particularly actively studied in the last decade. The goal is to find an optimal or near-optimal path from a starting terminal to one or more terminals in an environment with various obstacles, in terms of minimizing robot travel time, distance traveled, energy costs, or other optimization criteria. In this paper, we propose a hybrid algorithm combining a probabilistic roadmap algorithm (PRM) and an adapted genetic algorithm (AGA) to solve a path planning problem with one or more independent objectives. The robot's path length is used as an optimization criterion. Compared with existing approaches used in genetic algorithms (GAs), the proposed approach has two main differences. The first is the environment representation, which relies on image processing and morphological operations, which has proven to be a more efficient method than methods based on cellular representation. In particular, the proposed method eliminates the need to find a trade-off between accuracy and speed of processing geometric information. The second is a new tactic for creating an initial population of the genetic algorithm to accelerate convergence in the presence of multiple objectives. By leveraging the capabilities of a probabilistic roadmap algorithm. Another key feature of the algorithm's implementation is the appropriate (for the domain under study) selection of numerical parameters that determine the characteristics of all stages of the evolutionary strategy, including the time required to complete each stage. This applies in particular to the parameters of the mutation operator and the elite strategy. The proposed algorithm was tested on two real-world maps with varying levels of complexity. Its effectiveness was confirmed by comparison with path planning results for test maps obtained using a standard genetic algorithm and an ant colony optimization algorithm. Experimental results demonstrate that the hybrid algorithm expands the capabilities of a conventional genetic algorithm and finds rational path variants with the best objective function value for single and multiple objectives in significantly less time than other traditional GA implementations.

• A NEW ALGORITHM FOR CONSTRUCTING THE SHORTEST TOUR OF A FINITE SET OF DISJOINT CONTOURS ON A PLANE

  А. А. Petunin, E.G. Polishchuk, S.S. Ukolov

  2021-04-04

  Abstract ▼

  The problem of tool path routing for the CNC thermal cutting machines is considered.
  Pierce points are located at the parts bounding contours, consisting of straight-line segments and
  circular arcs. Continuous cutting technique is used, each contour is cut out entirely, and no presampling
  occurs, so cutting can start from any point on the contour. General problem of minimizing
  the route length is reduced to minimizing the air move length. It is shown to be equivalent to
  finding the shortest polyline with vertices on the contours. New algorithm for constructing such a
  broken line for fixed order of contour traversing is proposed. The resulting solution is shown to be
  a local minimum. Some sufficient conditions are described for the it to be also a global minimum,
  which can be easily verified numerically, and some even visually. A technique is described for
  automatically taking into account precedence constraints for the practically important case of
  nested contours. This also decreases the size of the problem, which has a positive effect on the
  optimization time. A heuristic routing algorithm based on the variable neighborhood search (VNS)
  is proposed. Alternative approaches to the use of other discrete optimization methods along with
  the proposed algorithm for constructing the shortest polyline for solving the complete problem of
  continuous cutting, and the resulting difficulties of both theoretical and practical nature are described.
  The generalization of the problem of continuous cutting to a wider class of problems of
  (generalized) segment cutting is described, which makes it possible to advance in solving the problem
  of intermittent cutting. The scheme of application of the proposed algorithm for solving problems
  of generalized segment cutting is described. The results of numerical experiments are considered
  in comparison with the exact solution of the GTSP problem.