Given my formulation of multiple construction lanes, I need to develop rigorous
invariants describing the set of structures possible to provably build in such a
way. One of the most important pieces of this is the frontier set, which is the
set of allowable blocks for a robot to place, given the current state of the
structure.
Some ideas of necessary properties of frontier set regarding eligibility:
All lower layer support blocks must be present. For a cell which will contain
a cube, this means the 9 lower layer blocks.
At least 2 manhattan adjacent blocks must be present on the same level for a
cell to be eligible for membership in the frontier set.p
Every cell in set is "accessible", meaning it has empty square manhattan
adjacent to it. Formally, all vertices in the subgraph of unoccupied cells in
the set are manhattan connected to each other.
A cell cannot be added to the frontier set if it would cause any non-member
cell to only have a single manhattan connected neighbor, unless there are only
2 unoccupied cells remaining on the structure.
Would be really awesome if the frontier set would be provably a matroid, so that
I could have robots choose the best block from it each time and be guaranteed a
near-optimal/optimal construction solution.
Given my formulation of multiple construction lanes, I need to develop rigorous invariants describing the set of structures possible to provably build in such a way. One of the most important pieces of this is the frontier set, which is the set of allowable blocks for a robot to place, given the current state of the structure.
Some ideas of necessary properties of frontier set regarding eligibility:
All lower layer support blocks must be present. For a cell which will contain a cube, this means the 9 lower layer blocks.
At least 2 manhattan adjacent blocks must be present on the same level for a cell to be eligible for membership in the frontier set.p
Every cell in set is "accessible", meaning it has empty square manhattan adjacent to it. Formally, all vertices in the subgraph of unoccupied cells in the set are manhattan connected to each other.
A cell cannot be added to the frontier set if it would cause any non-member cell to only have a single manhattan connected neighbor, unless there are only 2 unoccupied cells remaining on the structure.
Would be really awesome if the frontier set would be provably a matroid, so that I could have robots choose the best block from it each time and be guaranteed a near-optimal/optimal construction solution.