Time Constraint Finite-Horizon Path Planning Solution for Micromouse Extreme Problem

The original Micromouse competition was designed to educate future engineers, in robotic problem solving through active learning methods. The Micromouse Extreme (ME) Competition is proposed, to augment the pedagogical power of the original competition with a modern task set requiring skills in deep learning and creative solving methods. It also preserves the goal of original Micromouse Problem will to educate future engineers in robotic problem solving through active learning methods. The ME is a natural evolution to the simple programming nature of the original competition through the incorporation of advanced robotic tools and ideas. The platform described is fully virtual and inexpensive, providing an excellent platform for students to further their robotics education. As such, several methods of solving this setup are required to guide students along their path to proficiency in path planning. This paper discusses solutions to the ME problem such as the Traveling Salesman Problem and similar solvers to suit the proposed need. Once the problem is established we solve it using Time Constraint Finite Horizon Path Planning solution. The approach can provide a guaranteed global optimal path solution for the ME problem and can introduce students to solving methods for complex problems.

I. Introduction

MOBILE ROBOTICS tournaments have served as an effective medium to educate using mobile robotics, through student participation and publicity. Since it's intro-duction in 1972, Micromouse has been doing this job at a global level [1]. As the need for Artificial Intelligence (AI) increases in all sectors the need for AI education increases commensurately. Additionally, by creating the fully virtual Micromouse Extreme (ME) Competition we can reduce the cost required to participate while achieving our goal of AI education. This updated problem was first introduced in IEEE Philadelphia section, as a part of Engineer's week celebration in Temple University, on February 2022. Based on our best knowledge, the authors are the first group of researchers to introduce an updated Micromouse problem virtually on an AWS EC2 cloud platform. This networked format provides opportunities for students in different regions and universities to engage in robotic learning. The rest of the paper is organized as follows: a proposed ME problem is described in section II. The map of the maze can be generated using any graph-based search methods [2] by repeating the process with different destination locations until the entire maze is mapped. The authors have also developed a reinforced learning model to map the maze environment and generate a directed graph of the connected nodes as shown in Figure 3. In this paper the authors define their formulation of the problem to do all the tasks of ME in section III, through the global optimal path in section IV. The remainder of the paper details a time constrained finite horizon problem in section V, when the maximum time limit to finish the tasks is fixed. The authors have also defined a Cost-Constrained Traveling Salesman Problem (CCTSP) to solve a time constrained ME offline in section VI-B, following the section VII publishes all the MATLAB simulations used. Lastly, we discuss conclusions drawn for the competition and the proposed solvers, as well as future works to be done with the described platform. Fig. 1:

Micromoue extreme maze setup

Table I: Nomenclature used in the paper

Parameters that are to be estimated
element in the set of all the images
element in the set of all the targets
element in the set of all possible paths from any to
Maze description
any cell from the set of 256 total cells in the maze, also a node in the maze graph tree
of nodes needed to cover to reach target from cell c if followed the path p
of nodes needed to cover to reach image from cell c if followed the path p
node in the task graph
edge in the task graph
continuous time allowed to solve the problem
Rewards and cost
to be gained if reach target from image
to pay for traversing the space from image to target
to pay to reach target from image when time t has already been expended
cost to pay for crossing one edge i.e., traversing to one of the adjacent nodes
cost per time
rewards at cell c when time t has been expended
matrix valuing denoting the transition cost to move from cell i to cell j
allowable discrete cost for a given subtour