That was very fun optimization challenge on kaggle. I got silver medal. The task was to visit all image cells by 8-axis robotic arm with minimization of number of moves and color change.
The key idea for me was to notice - that if you split whole space into 4 quarters, visiting each quarter is trivially can be done in pixel space (not in configuration space). Transition between quarters can be done by passing through red cells, look at image:
Best score what I've achieved - 74265.771731100400.
I formulated LKH symmetric tsp problem in pixel space,
allowing to move by x-direction in 1 or 2 pixels by step and allowing to move in y-direction by 1-pixel.
After getting resulting tour in pixel space,
conversion to arm configuration space is straightforward
(some cleverness is needed to convert when step > 1,
this I achieved by splitting 7 free elements of configuration into 2 equal parts, and modifying each by 1)
No comments:
Post a Comment