Lamp Optimization Problem

0x_7777 · January 20, 2020, 3:08pm

A lamp is an object in 2D space with a scalar brightness. A sensor is a similar object, but with scalar property illumination instead of brightness. I have an arbitrary amount of lamps and sensors in an area.

Each sensors illumination is defined as follows:
Where a_kj = distance_kj^(-2) and p_j is the brightness of that lamp.

Each sensor has a desired illumination level. I wish to minimize the maximum deviated illumination level. To do so, I can control the individual brightness level of each lamp. The brightness level must be in bounds of max/min [0, 1].

What is the optimal optimization function for this? ie: set brightness of lamps in order to minimize function calculate()

local lamps = {}
local sensors = {}

local lamp = {}
local sensor = {}

local min_lamp_brightness = 0
local max_lamp_brigtness = 1

function lamp:new(position, brightness)
	local instance = {}
	instance.position = position
	instance.brightness = brightness
	setmetatable(instance, self)
	self.__index = self
	return instance
end

function sensor:new(position, illumination, desired_illumination)
	local instance = {}
	instance.position = position
	instance.illumination = illumination
	instance.desired_illumination = desired_illumination
	setmetatable(instance, self)
	self.__index = self
	return instance
end

local function calculate(lamps, sensors)
	local largest_illumination_deviation = 0
	
	for _,sensor in pairs(sensors) do
		local illumination_sum = 0
		for _,lamp in pairs(lamps) do
			local indvidual_illumination = lamp.brightness * 1/math.pow((lamp.position - sensor.position).magnitude, 2)
			illumination_sum = illumination_sum + indvidual_illumination
			-- Calculate the illumination level imparted on a sensor due to the brightness of each lamp
		end
		sensor.illumination = illumination_sum

		local illumination_deviation = math.abs(sensor.illumination - sensor.desired_illumination)
		if illumination_deviation > largest_illumination_deviation then
			largest_illumination_deviation = illumination_deviation
		end
	end
	
	return largest_illumination_deviation
end

local function optimize(lamps, sensors)
	for _,lamp in pairs(lamps) do
		lamp.brightness = math.random() -- Algorithm here to optimize the lamp brightness
		
		lamp.brightness = math.max(min_lamp_brightness, lamp.brightness) -- Must obey max/min lamp brightness
		lamp.brightness = math.min(max_lamp_brigtness, lamp.brightness)
	end
end

-- All lamps are set to 0.5 brightness
lamps[1] = lamp:new(Vector2.new(1, 2), 0.5)
lamps[2] = lamp:new(Vector2.new(4, 6), 0.5)
lamps[3] = lamp:new(Vector2.new(8, 9), 0.5)
lamps[4] = lamp:new(Vector2.new(4, 5), 0.5)

-- Sensors all have a distinct desired illumination level
sensors[1] = sensor:new(Vector2.new(0, 0), nil, 0.3)
sensors[2] = sensor:new(Vector2.new(4, 2), nil, 0.5)
sensors[3] = sensor:new(Vector2.new(8, 4), nil, 0.7)

print(calculate(lamps, sensors)) -- Calculate the maximum sensor deviation
optimize(lamps, sensors) -- Algorithm to control each lamp brightness in order to minimize the maximum sensor deviation
print(calculate(lamps, sensors)) -- Verify the maximum sensor deviation is minimized

DrKittyWaffles · January 20, 2020, 4:37pm

A hacky solution would be to just keep calling math.random() until it works, somewhat like bogosort. Might take about a minute or maybe an hour to compute, however it should at some point hypothetically return a good enough result.

Let threshold be the max deviation allowed.

repeat
     optimize(lamps)
until calculate(lamps, sensors) <= threshold

where

local function optimize(lamps)
     for _, lamp in pairs(lamps) do
          lamp.brightness = math.random()
     end
end

Not the best solution by a large margin, but alas, it is a solution.

P.S.

You have a little typo on line 8, you defined variable max_lamp_brigtness but later used the variable max_lamp_brightness, and you can’t take the max of a nil value.

You can remove the setting of the __index entirely from the class constructors,

local lamp = {}

lamp.__index = lamp

function lamp:new(...)
     --// ...
end

You can also use x^n rather than math.pow(x, n); 1 / ((a - b).Magnitude)^2

RamJoT · January 20, 2020, 4:43pm

If you are trying to restrict a value between two points then perhaps math.clamp may help.

DrKittyWaffles · January 20, 2020, 4:44pm

There is no point to clamp it at all because math.random() returns a float between 0, 1; making it useless to clamp to between the range it is already bound by.

That is why my optimize function has no math.clamp(lamp.brightness, 0, 1)

Also, the function call is likely slower than just using the built in operands due to having to pass through the c boundary and back.

Proof for my statement ↑

do
	local start = tick()
	
	for i = 1, 10^6 do
		if (i > 10) then
			i = 10
		elseif (i < 0) then
			i = 0
		end
	end
	
	print(tick() - start)
end

do
	local start = tick()
	
	for i = 1, 10^6 do
		i = math.clamp(i, 0, 10)
	end
	
	print(tick() - start)
end

TheNickmaster21 · January 20, 2020, 4:48pm

This is an interesting problem. My first thought was to use linear algebra but it’s been a while so I’m a little rusty on how optimization would look with a system of equations. You could solve this problem with machine learning. You could have all the light brightness as inputs to the system and the maximum light deviation as the value to optimize.

I’m going to do some more digging and see what I can come up with.

safazi · January 20, 2020, 5:00pm

You should probably using Rust to solve this problem. My solution would be to use an HTTP request to send the position and brightness of each lamp, as well as the position and desired illumination of each sensor. Then, simply port the Lua you’ve already written to Rust, as well as Vector3, and run the numbers when they’re sent to your server. I’d consider using Redis to cache responses in the off chance that similar cases are sent after one another.

0x_7777 · January 20, 2020, 5:07pm

What I could do, perhaps, is write a heuristic transpiler to convert the Lua problem statement into the Disciplined Convex Programming language. This then would be transmitted to my external server which would be running some sort of highly optimized convex optimization suite. Probably, I would be using CVXGEN which was written by the illustrious father of modern Convex Optimization Stephen Boyd himself. Since CVXGEN will generate a highly optimized C-solver for the problem-statement, it would then have to be transpiled back to Lua or executed on the machine and the results sent back to the Lua instance.

Attached is an image of the CVXGEN Online Generation GUI (for reference):
External Media

This, however, could be bypassed if someone ported CVXOPT/CVXPY into Lua.

safazi · January 20, 2020, 5:16pm

All those computations might take a while - I’d consider using long polling to hold onto a request while it sits in a job queue before being calculated. If the connection is hanging for a while, have the game server long poll again. Simply repeat until you can send back the answer.

TheNickmaster21 · January 20, 2020, 5:18pm

Here’s a brute force approach that gives me a lower calculate result when finished. This is by no means the optimal way to solve the problem but it does what you asked for:

[REMOVED]

UPDATE: Okay, so I think your test data is a bit of an edge case. It seems to be the best variance my model can find boosts all the brightness up to the max. With different test data, I got way more promising results:

local lamps = {}
local sensors = {}

local lamp = {}
local sensor = {}

local min_lamp_brightness = 0
local max_lamp_brigtness = 1

function lamp:new(position, brightness)
	local instance = {}
	instance.position = position
	instance.brightness = brightness
	setmetatable(instance, self)
	self.__index = self
	return instance
end

function sensor:new(position, illumination, desired_illumination)
	local instance = {}
	instance.position = position
	instance.illumination = illumination
	instance.desired_illumination = desired_illumination
	setmetatable(instance, self)
	self.__index = self
	return instance
end

local function calculate(lamps, sensors)
	local largest_illumination_deviation = 0
	
	for _,sensor in pairs(sensors) do
		local illumination_sum = 0
		for _,lamp in pairs(lamps) do
			local indvidual_illumination = lamp.brightness * 1/math.pow((lamp.position - sensor.position).magnitude, 2)
			illumination_sum = illumination_sum + indvidual_illumination
			-- Calculate the illumination level imparted on a sensor due to the brightness of each lamp
		end
		sensor.illumination = illumination_sum

		local illumination_deviation = math.abs(sensor.illumination - sensor.desired_illumination)
		if illumination_deviation > largest_illumination_deviation then
			largest_illumination_deviation = illumination_deviation
		end
	end
	
	return largest_illumination_deviation
end

local last_wait = tick()

local function sub_optimize(lamps, sensors, min_value, max_value, increment, index)
	if(tick() - last_wait > 3)then
		print('still spinning')
		wait()
		last_wait = tick()
	end
	local smallest_illumination_deviation, optimal_brightness_for_lamp, other_brightnesses = math.huge, nil, {}
	for b = min_value, max_value, increment do
		lamps[index].brightness = b
		local other_brightness_result = {}
		if(index < #lamps)then
			other_brightness_result = sub_optimize(lamps, sensors, min_value, max_value, increment, index + 1)
		end
		local sub_result = calculate(lamps, sensors)
		if(sub_result < smallest_illumination_deviation)then
			smallest_illumination_deviation = sub_result
			optimal_brightness_for_lamp = b
			other_brightnesses = other_brightness_result
		end
	end
	lamps[index].brightness = optimal_brightness_for_lamp
	if(#other_brightnesses > 0)then
		for i = index + 1, #lamps, 1 do
			lamps[i].brightness = other_brightnesses[i - (#lamps - #other_brightnesses)]
		end
	end
	table.insert(other_brightnesses, 1, optimal_brightness_for_lamp)
	return other_brightnesses
end

local function optimize(lamps, sensors, min_value, max_value, increment)
	if(not min_value)then min_value = min_lamp_brightness; end
	if(not max_value)then max_value = max_lamp_brigtness; end
	if(not increment)then increment = .05; end

	sub_optimize(lamps, sensors, min_value, max_value, increment, 1)
end

-- All lamps are set to 0.5 brightness
lamps[1] = lamp:new(Vector2.new(1, 2), 0.5)
lamps[2] = lamp:new(Vector2.new(4, 6), 0.5)
lamps[3] = lamp:new(Vector2.new(8, 9), 0.5)
lamps[4] = lamp:new(Vector2.new(4, 5), 0.5)

-- Sensors all have a distinct desired illumination level
--sensors[1] = sensor:new(Vector2.new(0, 0), nil, 0.3)
--sensors[2] = sensor:new(Vector2.new(4, 2), nil, 0.5)
--sensors[3] = sensor:new(Vector2.new(8, 4), nil, 0.7)

-- Different Test data
sensors[1] = sensor:new(Vector2.new(0, 0), nil, 0.3)
sensors[2] = sensor:new(Vector2.new(4, 4), nil, 0.1)
sensors[3] = sensor:new(Vector2.new(4, 4), nil, 0.2)

print('start', calculate(lamps, sensors)) -- Calculate the maximum sensor deviation
optimize(lamps, sensors) -- Algorithm to control each lamp brightness in order to minimize the maximum sensor deviation
print('optimized', calculate(lamps, sensors)) -- Verify the maximum sensor deviation is minimized


for i = 1, #lamps do
	print('lamp ', i, ' ', lamps[i].brightness)
end

I hope this is useful! I had fun even though the best I could come up with was a brute force solution.

acreol · February 3, 2020, 6:20pm

I want to think about this more if I can because it sounds really interesting; I think this is a more formal statement of the problem: