A Decentralized Approach to the Art Gallery Problem

Lass, Grauer, Sultanik, Regli

art gallery constraint optimization distributed dcop ai

@inproceedings{lass:fwcg2007,
  title={A Decentralized Approach to the Art Gallery Problem},
  author={Robert N. Lass and Michael J. Grauer and
          Evan A. Sultanik and William C. Regl},
  booktitle={Fall Workshop on Computational Geometry},
  year={2007}
}

Art gallery problem: Place a minimal number of guards to cover a set of paintings in a gallery

• Extension here: Guards have limited fields of view, limited range (distance) of view

Takes gallery and discretizes, runs DCOP to assign robots to discretized points

• Takes into account distance traveled to reach that point

Uses DCOPOLIS to do the solving, explores some state pruning techniques