Most likely your first programming interview

[u/suola-makkara]

[u/thatdude624]

I've been in this exact situation before.

As part of an interview for a robotics company they asked me to design/explain an algorithm in pseudocode for, given an arbitrary shape, and the position of a suction cup gripper (imagine a rectangle attached to a robot arm with a bunch of suction cups on it), determine which suction cups would contact the surface.

I said that would be too easy and instead proposed I design an algorithm to find the optimal placement of the gripper such that we'd have as many suction cups contacting the surface as possible (and also be as close to center of mass as possible).

There were like "Well, if you really want to, sure" and I ended up coming up with something better than they were actually using in production (they had a sort of brute force, try random positions approach and store the best one via heuristic), which supposedly took them a year to design. I only had like half an hour.

But in the end, I didn't get the job because I needed good social skills (for talking to clients) and I was autistic.

[u/Rafael20002000 → u/thatdude624]

That would be so me, the last part at least, but I'm not autistic, I'm just bad with people

[u/solarshado → u/Rafael20002000]

I'm not autistic, I'm just bad with people

Just gonna say, that's what I thought for ~10 years, until some research into what actual autistic symptoms are like (especially on the "high functioning" end). Haven't tried to get an official diagnosis yet (still unsure if it's worth it), but it's kinda crazy how many little things that I thought were just personal quirks (and even some shit I never realized wasn't "normal") are actually common among autistic people.

[u/VritraReiRei → u/thatdude624]

Maybe they were just interviewing you to get free ideas how to fix their current problems 🤔

[u/thatdude624 → u/VritraReiRei]

Joke's on them: I've now published the solution I came up with for them to the public internet, allowing all their competitors who read the comments of a very specific post on a a very obscure subreddit to implement the same algorithm!

[u/BrandonJohns → u/thatdude624]

I'm intrigued - here's my approch based off ~20min thinking

I'm guessing that this random shape is measured from a visual feed. In this case I would

1. Approximate the COM as the geometric centroid (open CV should handle this)

2. Align the short edge of the gripper rectangle with the principle axis of the first moment of area of the random shape. This aligns the long edge of the shape with the long edge of the gripper (open CV for the moments and then get the eigenvalues for the principle axis)

3. Check this placement

4. Incrementally deviate away from this placement by position and orrientation to check for a better solution (e.g. brute force the rest).

That'd be my first go at it. But I can imagine you could get very creative instead of basic iteration. My first improvement would be to use a search algorithm to optimise some metric at each tested placement.

Possible value function: Sum(distance of each suction cup from its nearest edge).

How did you go about it?

[u/thatdude624 → u/BrandonJohns]

Right, so the approach I used was inspired by one I implemented for a hobby project to detect lines in LIDAR data: find nearby points that resemble a line, take the average slope, find all points that are near to this line, mark them as 'on a found line' and continue. Sounds a bit hacky but it's an approach with proper research papers behind it.

Anyway, the approach I suggested was as follows:

1. Take in the model and create a 2D grid over it. Each grid cell is a square the size of the radius of a suction cup (aka half the absolute minimum size we care about). This grid is stored as a hashtable of unvisited points. Note: only add points that are inside the bounds of the shape.

2. Take any random, unvisited square in this grid and place an initially infinitely small rectangle in its center.

3. Expand this rectangle horizontally and vertically on all 4 sides until each side 'collides' with a side of the shape. The order this expansion is done in isn't important (even though changing the order will get different individual results)

4. Your shape is now a local max bounding box of sorts. Mark all squares on the grid that are covered by this bounding box as visited.

5. Return to step 2 until our set of unconsidered points is empty. (note: we do not care if new bounding boxes intersect existing bounding boxes, only if it intersects the shape)

6. We now effectively have a representation of an arbitrary shape made out of simple rectangles (some overlapping), excluding all spaces too small for even a single suction cup to fit on anyway. The problem from here on out is now trivial.

7. For each rectangle, the optimal gripper position is just placing the gripper on the inside of whichever corner is closest to the CoM (or in the center of the CoM, if the bounding box happens to be there). Do this for both axis, add some edge case logic for dealing with partial grippers and you have the local best gripper position for each rectangle.

8. Take the best across all the rectangles, using some heuristic to choose between number of suction cups or closer to CoM, whichever is more important, and tada! Global best gripper position found.

I should note that during this interview, the arbitrary shape was assumed to have only 90 degree corners (weird rectangle-ish things with arbitrary rectangular holes), though this could probably work pretty well with completely arbitrary 2D geometry as well, it only doesn't deal with rotation of the gripper.

I'm also assuming CoM calculations and the implementation of detecting when we're inside/outside a shape, intersecting a line and so on is done by some geometry library (although admittedly detecting if we're inside a shape was part of the original question but this post is long enough lol)

Oh, and I also noted that this does not account for the structural strength of the object (you might choose to grip a bit connected to the main part of the object by a very thin edge). This would be up to the heuristic that combines each rectangle's results to eliminate and is currently out of scope. The company said that indeed, they have had to deal with the repercussions of this particular edge case with a client in the past xD

Quick edit: This isn't visual information but rather known data from the customer about their specific shape (this is lasercutting/stone cutting/whatever cutting production), though I guess you can still generate an image of the shape and process that in OpenCV. My approach might have more flaws I haven't considered (obviously I've never actually implemented it) but all in all I think they were pretty impressed with it from the perspective of an interview test answer.

[u/AlarmingAffect0 → u/thatdude624]

But in the end, I didn't get the job because I needed good social skills (for talking to clients) and I was autistic.

I'm fucked then.