So i am attempting to optimize the following pointing problem. I have a set of sensors (cameras) and a set of targets. Each camera can be oriented directly at one one target, but based on its FOV it may see multiple targets. The goal is to cover as many targets as possible with the user defined number of cameras (i.e stereo, 2)
I initially took the approach of using MATLAB and intlinprog and will show the formulation, but seeing as I am new to MILP I am open to criticism and suggestions
- S sensors
- T targets
- P pointing options for each S sensor
- T == P
- R required coverage level (i.e 2 for stereo or 1 for mono)
The source data for the problem is logical/binary 3D array called Vis (P x T x S) indexed (i,j,k)
- Each Layer (3rd Dimension S) represents a camera
- Each Row in a layer represents a pointing option
- The column in a given row and layer is true if that target is seen
Vis (i,j,k) = true if Camera(k) can see target (j) using pointing option (i)
- Each camera can be assigned only one pointing option
Goal: Maximize the number of targets that have atleast the requried coverage level.
I am going to insert an example of my code below. Some notes are that I take the matrix of Vis and convert it to a 2-D array by concating each "layer" alond the first dimension.
There is a binary decision variable for each pointing option for each camera and a binary switching variable used to switch for the optimizing the number of targets with the desired coverage level.
S = 156; %100 Cameras T = 100; %100 Targets P = T; %100 Pointing options R = 2; % Required Coverage Level (stereo) % Load Vis Matrix it is (P x T X S) %When the matrix is very scattered the solver works fine, the problem is %a few cameras can see alot of targets and some can see none load('Vis.mat'); %Use permute and reshape matrix so that each "3rd" dimension layer is %concated onton the bottom of the previous one VisNew = permute(Vis,[1 3 2]); VisNew = reshape(VisNew,,size(Vis,2),1); [m,n] = size(VisNew); %% Optimization Problem Setup %The first set of variables will be the logical t/f for the pointing %option's (m) . The last set of Logic t/f will be the coverage variables (n) NumVars = m + n; % All variables are integers prob_struct.intcon = 1:NumVars; % All Variables have lb of 0 and ub of 1 prob_struct.lb = zeros(NumVars,1); prob_struct.ub = ones(NumVars,1); % The "maximization" (min for the function) is the sum of the "Required % Coverage" switching variables which are only true if the required % coverage is obtained prob_struct.f = [zeros(m,1); -1*ones(n,1)]; %The equality constraint comes from that each camera can only %be tasked 1 pointing option. So the sum of those options variables for each %camera should sum to 1 prob_struct.Aeq = zeros(S,NumVars); for x = 1:S prob_struct.Aeq(x,((x-1)*P+1:x*P)) = 1; end prob_struct.beq = ones(S,1); % The inequality constraint is just ensuring that the coverage % variable is only switched when there is enough coverage for that target prob_struct.Aineq = [VisNew'.*-1 R.*eye(n)]; prob_struct.bineq = zeros(n,1); % Define which solver to use prob_struct.solver = 'intlinprog'; prob_struct.options = optimoptions('intlinprog'); %Solve the problem [X,Y] = intlinprog(prob_struct);