The necessary modules, including SimpleAI for the AI problem solving
from random import random
from IPython.display import HTML
from simpleai.search import SearchProblem, hill_climbing_random_restarts
Simple Manhattan distance
def distance(position1, position2):
x1, y1 = position1
x2, y2 = position2
return abs(x1 - x2) + abs(y1 - y2)
We define the problem as a local search problem (optimization)
class CenterProblem(SearchProblem):
def __init__(self, precission, positions, special_importances):
super(CenterProblem, self).__init__(self)
self.precission = precission
self.positions = positions
self.special_importances = special_importances
self.top = min(y for x, y in self.positions.values())
self.bottom = max(y for x, y in self.positions.values())
self.left = min(x for x, y in self.positions.values())
self.right = max(x for x, y in self.positions.values())
self.step_x = abs(self.top - self.bottom) / self.precission
self.step_y = abs(self.left - self.right) / self.precission
def actions(self, state):
x, y = state
return ((x, y + self.step_y),
(x, y - self.step_y),
(x + self.step_x, y),
(x - self.step_x, y))
def result(self, state, action):
return action
def cost(self, state1, action, state2):
return 1
def value(self, state):
return -sum(distance(state, position) * self.special_importances.get(thing, 1)
for thing, position in self.positions.items())
def generate_random_state(self):
return (self.left + random() * self.precission,
self.top + random() * self.precission)
Instantiate the problem with specific data, then solve it using hill climbing with random restarts
problem = CenterProblem(
precission = 100, # higher is more precise
positions = {
'churi': (-34.581516, -58.578009),
'papacheese': (-34.572046, -58.494067),
'sirevanac': (-34.548862, -58.481364),
'blitz': (-34.511386, -58.496985),
'svin': (-34.762215, -58.248630),
'zild': (-34.112310, -59.029679),
},
special_importances = {
'svin': 0.15,
'zild': 0.15,
}
)
result = hill_climbing_random_restarts(problem, restarts_limit=100)
print result.state, abs(result.value)
(-34.56296283235742, -58.49674475938182) 0.4075201
Finally, plot the solution with google maps
template = """<iframe
src="https://www.google.com/maps/embed/v1/place?key={maps_key}&q={position}"
style="height: 500px; width: 100%">
</iframe>
"""
HTML(template.format(maps_key='AIzaSyBLX80To6RQE7BZwAf0ClVozv4MrZ2vwxI',
position=','.join(map(str, result.state))))