Optimizing 2D grid surveillance with Python and Julia

Surveillance optimization using ILP

Project Details

I participated with Thimoté Dupuch in a programming contest where we worked on an surveillance optimization project. Our mission was to optimize the placement of surveillance points to cover specific targets while avoiding obstacles in a 2D grid. The goal is to minimize the number of surveillance points needed to effectively monitor all targets in the grid. Before settling on the final implementation in Julia using linear programming, we first explored various approaches in Python. We experimented with algorithms like local search, greedy, genetic, heuristic, and recursive methods to compare their performances and identify the most efficient solution. Then, we used Julia to formulate the problem as a binary linear programming model and efficiently solved it with the HiGHS solver.



PYTHON VERSION

Surveillance Optimization Algorithms




During the initial stages of the project, we first decided to explore multiple strategies to solve the surveillance optimization problem. We opted to use Python as our programming language for its versatility and ease of implementation. We developed several algorithms, each with its own unique approach to the problem.

  • Local Search Algorithm: We devised a local search approach that iteratively explored the neighboring solutions to improve the objective function. This method aimed to find local optima by iteratively making small adjustments to the initial solution.

  • Greedy Algorithm: The greedy algorithm focused on making locally optimal choices at each step with the hope of finding a global optimal solution. It involved selecting the best possible decision at each stage without considering the long-term impact.

  • Genetic Algorithm: Inspired by the process of natural selection, we designed a genetic algorithm that involved creating a population of potential solutions, applying genetic operations like mutation and crossover, and selecting the best-fit individuals for the next generation.

  • Heuristic Algorithm: The heuristic algorithm employed a rule-based approach to make educated guesses and approximate solutions efficiently, even if not guaranteed to be optimal.

  • Recursive Algorithm: We also experimented with a recursive approach, where the algorithm called itself with smaller subsets of the problem until reaching a base case and then backtracked to find the optimal solution.

  • After implementing these algorithms, we thoroughly tested and compared their performances on various instances of the surveillance problem. However, it became evident that the linear programming approach using the JuMP package in Julia outperformed all the other methods. It provided a more robust and optimal solution for the problem at hand.



    JULIA VERSION

    Solving an Integer Linear Programming Problem




    The provided code is written in the Julia programming language and aims to solve a surveillance optimization problem. The goal is to determine the minimum number of surveillance points required to cover all specified target locations while avoiding obstacles. The code uses the JuMP library to formulate and solve the optimization problem, and the HiGHS solver is employed to find the optimal solution. Let's break down the structure and purpose of the code:

  • Imports: The code begins by importing two required libraries, JuMP and HiGHS, which are used for mathematical modeling and optimization, respectively.

  • `is_visible` Function: This function checks if a target is visible from a given surveillance point on a grid. It takes the coordinates of the target and surveillance point as inputs, along with the grid containing obstacle information. The function uses simple geometric calculations to determine visibility, ensuring there are no obstacles in the line of sight.

  • Reading Input and Initializing the Grid: The code reads input data from the file "Instances/gr16.txt." The first two lines of the file provide the number of rows and columns in the grid. The subsequent lines specify the locations of targets and obstacles. The grid is initialized with zeros, and each target and obstacle location is marked with a value of 1 and 2, respectively.

  • `assign` Function: This function is a helper function that assigns values (1 or 2) to the grid cells based on the input "objet," which can be either "CIBLE" (target) or "OBSTACLE."

  • JuMP Model Creation: The code creates a JuMP model using the HiGHS optimizer. JuMP provides an intuitive way to define the optimization problem and the variables to be optimized.

  • Decision Variables: The code defines decision variables `surveillant` as a binary matrix. Each element (i, j) in the matrix indicates whether there is a surveillance point at position (i, j) in the grid.

  • Constraints: The code creates constraints to ensure that each target is observed by at least one surveillance point. It iterates through each target location and adds a constraint that sums the surveillance points' variables within the visibility range of the target. If a target is visible from a surveillance point and there are no obstacles in the line of sight, the constraint is added.

  • Objective Function: The objective is to minimize the number of surveillance points needed. Therefore, the code defines an objective function that sums the surveillance point variables across the entire grid.

  • Time Limit Setting: The code sets a time limit of 180 seconds for the optimization process to avoid excessive computation time.

  • Model Optimization: The code calls the `optimize!` function to solve the optimization problem and find the minimum number of surveillance points.

  • Result Display: After solving the optimization problem, the code displays the positions of the surveillance points and the total number of surveillance points used.

  • Writing Results to File: The code writes the results to the file "Submissions/res_16.txt." It includes the team name ("EQUIPE theo_thimote.jpeg"), the instance number ("INSTANCE 16"), and the coordinates of the surveillance points.

  • Overall, the code follows a structured approach to solve the surveillance optimization problem by formulating it as a binary linear programming model using JuMP and finding the optimal solution with the HiGHS solver. It effectively uses functions to organize and encapsulate related tasks, making the code modular and easy to understand.

    
    using JuMP
    using HiGHS
    
    # Function to check if a target is visible from a given surveillance point
    function is_visible(x_cible, y_cible, x_surv, y_surv, grille)
    	if grille[x_surv, y_surv] == 2  # If the surveillance point is on an obstacle
    		return false
    	end
    
    	dx = x_cible - x_surv
    	dy = y_cible - y_surv
    
    	if dx == 0 && dy == 0
    		return true
    	end
    
    	# Check visibility on a single row
    	if dx == 0
    		direction = sign(dy)
    		for j in y_surv + direction:direction:y_cible - direction
    			if grille[x_surv, j] == 2  # If there is an obstacle on the row
    				return false
    			end
    		end
    		return true
    	end
    
    	# Check visibility on a single column
    	if dy == 0
    		direction = sign(dx)
    		for i in x_surv + direction:direction:x_cible - direction
    			if grille[i, y_surv] == 2  # If there is an obstacle on the column
    				return false
    			end
    		end
    		return true
    	end
    
    	return false  # The target and surveillance point are neither on a row nor on a column
    end
    
    # Read input from a file and initialize the grid
    f = open("Instances/gr16.txt", "r") 
    lines = readlines(f)
    nb_lignes_fichier = size(lines)[1]
    
    nb_lignes = parse(Int, lines[1][end-1:end])
    nb_colonnes = parse(Int, lines[2][end-1:end])
    
    grille = zeros(nb_lignes, nb_colonnes)
    
    # Function to assign a value to grid cells based on the input
    function assign(objet)
    	if objet == "CIBLE"
    		return 1
    	else
    		return 2
    	end
    end
    
    # Initialize the grid based on the input file
    for i in 4:size(lines)[1]  # Ignore the first three lines
    	line = lines[i]
    	parts = split(line)
    	objet = parts[1]
    	x = parse(Int, parts[2]) + 1
    	y = parse(Int, parts[3]) + 1
    
    	int_objet = assign(objet)
    	grille[x, y] = int_objet
    end
    
    # Create a JuMP model using HiGHS optimizer
    m = Model(HiGHS.Optimizer)
    
    # Decision variables
    @variable(m, surveillant[1:nb_lignes, 1:nb_colonnes], Bin)
    
    # Constraint 1: Each target must be surveilled at least once
    for i in 1:nb_lignes
    	for j in 1:nb_colonnes
    		if grille[i, j] == 1  # If it is a target
    			@constraint(m, sum(surveillant[x, y] for x in 1:nb_lignes, y in 1:nb_colonnes 
    						if is_visible(i, j, x, y, grille) && grille[x, y] != 2) >= 1)
    		end
    	end
    end
    
    # Objective: Minimize the number of surveillance points
    @objective(m, Min, sum(surveillant[i, j] for i in 1:nb_lignes, j in 1:nb_colonnes))
    
    # Set time limit for the optimization
    set_time_limit_sec(m, 180.0)
    
    # Solve the model
    optimize!(m)
    
    # Display the positions of the surveillance points
    resultats_optim = []
    
    println("Surveillance points positioned:", objective_value(m))
    for i in 1:nb_lignes
    	for j in 1:nb_colonnes
    		if value(surveillant[i, j]) > 0.5
    			push!(resultats_optim, (i - 1, j - 1))
    		end
    	end
    end
    
    println(resultats_optim)
    
    # Write the results to a file
    fichier = open("Submissions/res_16.txt", "w")
    write(fichier, "EQUIPE theo_thimote.jpeg\n")
    write(fichier, "INSTANCE 16\n")
    for resultat in resultats_optim
    	x, y = resultat
    	write(fichier, "$x $y\n")
    end
    close(fichier)