Grant: Discovery Launch Supplement

The interplay between research and application is as old as human civilization. As theoretical research has found application in real life problems, similarly advent of civilization and industrial revolution has created new problems for researchers to solve. I am interested in applying my research into solving reconfiguration problems relevant to industries such as additive manufacturing. Reconfiguration problem has attracted the attention of researchers for decades due to its usefulness in exploring the solution space of problems that are hard to solve. Typical questions that arise in this field include: whether there exist a reconfiguration sequence between two given solutions (or, configurations); what is the shortest such sequence; under which constraints the reconfiguration graph is connected (the connectivity problem), and what is the diameter of the reconfiguration graph. We search for answers to these questions for reconfiguration of Hamiltonian cycles and paths. Given two Hamiltonian cycles/paths in the same graph, reconfiguration problem asks whether one can transform one cycle/path to the other using specific operation such that a Hamiltonian cycle is built after each operation. Cycles and paths in grid graphs have been studied for a long time; the same can be said about reconfiguration problems. However, reconfiguration of cycles and paths is a novel problem with important applications in robot navigation. Bedel et al. showed an application of reconfiguration of Hamiltonian cycles in optimizing the "toolpath" of 3D printers under orientation objectives. Reconfiguration of Hamiltonian paths and cycles also has the potential to improve turn costs, travel time, and navigation accuracy for mobile robots. The long-term goal of my research is to solve problems in the robot industry, especially in robot movements and path planning, using reconfiguration. Often finding an optimal configuration is computationally extensive, where reconfiguration techniques can be used to reduce the cost of computation and thus, to make the process more efficient. However, each industrial setting is very different from others, and requires specific research in that area. To achieve my long-term goal, I will pursue the following three short-term objectives for the next five years: (OBJ-1) expand theoretical knowledge and develop efficient algorithms for reconfiguration of paths and cycles in grid graphs; (OBJ-2) apply reconfiguration of paths and cycles in 3D printing to obtain toolpaths with certain properties; (OBJ-3) apply reconfiguration in generating collision-free and efficient toolpaths for additive manufacturing; and to obtain optimal toolpaths to fabricate objects with certain properties.  My research directly aims to expand our knowledge on reconfiguration algorithms and designing more efficient algorithms. This research would help advance the additive manufacturing industry of our country, paving the way for Canada to be a leader in this industry.