Robotic Brewing: Inspection Planning Algorithms (IPAs) on Tap
Speaker: Blair D. SullivanDate of Talk: November 21, 2024
Upstream link: UCLA Colloquium
It’s been a while since I wrote up one of these. Time to try this again!
1. The Inspection Planning Problem
The prototypical setting is an autonomous surgical robot. Prior to performing surgery, it needs to “scout” the patient’s organs and obtain visual or geometric information about them from multiple perspectives. What’s the most efficient way to do this?
This can be represented with a graph: each node represents a state of the robot, and edges represent “legal” transitions between the states. The presence of edges depends on external limitations — a surgical robot can’t move through ribs (under reasonable moral assumptions). Edges are weighted by “cost”, and each node contains a set of “points of interest”, a subset of finitely many pieces of information that the robot must scout out.
The problem is, given a starting vertex on this graph, find the minimal weight path that observes a given proportion of the set of points of interest. (In words, find the most efficient way to “scout out” most or all of the important information.)
In practise, the number of points of interest \(k\) is quite small while the configuration space is gigantic, a graph of \(n\gg k\) vertices. It turns out there’s a way to do this polynomially in \(n\)!
2. Integer Linear Programming, the “Charging Argument”
An algorithmic solution can be proposed as a linear programming problem: we are minimising an integer linear combination of the weights, and the constraints (that our solution is a cycle, that it hits enough colours, and that it starts and ends at a prescribed vertex) can also be encoded as linear inequalities with integer coefficients.
There is some subtlety with encoding the condition that we start and end at a certain vertex, and this is doable using a “charging argument”. By spreading charges along the path cleverly, there is a way to tell whether or not the starting vertex was included by observing the average charge along the walk! Apparently this is a common and very slick argument in graph theory, so it’s worth looking into…
3. Algebraic Circuits and Multilinear Detection
Somehow, the problem was translated into a problem about algebraic circuits. Given \(n\) variables and a “binary tree of \(+\) and \(\times\) operations”, can you find out quickly if a multilinear term appears in the resulting polynomial? Such a term corresponds to an optimal solution. This is kind of insane to me, and apparently they give an algorithm to construct such a circuit out of the configuration graph in a way to make this happen.
It’s surprising to me that this kind of random purely algebraic problem has applications like this…definitely worth looking into. The problem of determining existence was done by Koutis (2008) and Williams (2009).