Decision Optimization

Hello,

I am currently grappling with a dilemma in modeling a particular problem. Here is a detailed description of the problem:

Consider a 2D grid area divided into square cells. An agent (robot) needs to sweep the entire area. The robot can move in four directions: up, down, right, and left, and moves directly between the centers of adjacent cells. Assume each move by the robot consumes one unit of time. For simplicity, assume the robot starts from the lower-left corner of the grid (indicated as the green cell in the diagram below). The goal is to sweep the entire grid while adhering to a specific constraint (caveat): each cell is assigned a priority, with higher-priority cells needing to be visited sooner. Assume priorities range from 1 to 4, with 4 being the highest priority.

Here is the dilemma I face: The objective is to sweep the grid as quickly as possible, while also prioritizing cells with higher priorities — the sooner high-priority cells are visited, the better. This creates a trade-off between two seemingly conflicting criteria:

1. Sweeping the grid in a linear fashion (similar to a lawn-mower pattern) may result in higher-priority cells being visited later, but avoids revisits to cells.
2. Prioritizing high-priority cells first may ensure these cells are visited sooner, but could lead to revisits of some cells, potentially increasing the total distance traveled.

The challenge is to find the optimal balance between these two objectives. To address this, I propose introducing a measure of "urgency" — for instance, visiting a priority 4 cell at time step 3 should be valued differently compared to visiting it at time step 7.

As an example, consider a 5x5 grid with randomly assigned priorities, represented by the matrix:

{{2, 4, 1, 2, 1}, {1, 3, 4, 4, 2}, {1, 3, 2, 3, 1}, {1, 1, 2, 2, 1}, {2, 2, 3, 4, 2}}, like in the picture below:

Color Coding:

• Green: Indicates the starting position of the agent.
• Red: Represents the highest priority cells (priority 4 being the highest).

I am interested in exploring how to effectively balance these criteria to achieve an optimal sweeping strategy.

What methodologies might be effective for this problem? What literature should I review?

In existing literature, the problem falls under the category of (Complete) Coverage Path Planning, where every cell must be visited. However, traditional algorithms for coverage path planning do not account for cell priorities (here comes the caveat). I am interested in exploring how to model this problem using Mixed Integer Programming (MIP). Specifically, I seek guidance on how to:

1. Formulate Decision Variables: How should decision variables be defined to capture both the sweeping actions and the prioritization of cells?

2. Define the Objective Function: How can the objective function be structured to balance the total sweeping time with the urgency of visiting high-priority cells?

3. Develop Constraints: What constraints are necessary? Especially to ensure the sequentiality of decisions at each time step?

I am particularly intrigued by how to manage the sequential nature of decisions in this context. Have you encountered similar problems or seen methodologies that address these concerns? Are there similar problems in the literature?

Thank you for considering my inquiry.

Best,

Yusup

------------------------------
Yusup Allyyev
------------------------------