1
$\begingroup$

Tree search over a state space often assumes that the state can be represented compactly and repeated in each node of the search tree.

Suppose I have a large simulation with 100000's of entities each with a rich complex state. If performing a tree search over the full simulation state space, where each action affects a small number of entity, it will be inefficient to replicate the full simulation state in each node of the tree. However, the simulation constraints are tightly coupled and factoring the simulation into smaller sub-simulations is not possible.

What methods exist for performing tree search over a problem space where the state representation is huge and complex?

$\endgroup$
3
  • 1
    $\begingroup$ I'm not sure that I understand. Do you mean that in a node, you need to store a lot of data, and therefore your tree takes too much space on the machine? $\endgroup$
    – fontanf
    Oct 13, 2022 at 10:04
  • $\begingroup$ Each node is the result of an action aapplied to the parent, causing state changes for some entities in the model. But it is prohibitively expensive to replicate the entire simulation state on each node in the search tree. Do standard methods exist in literature for this class of problem? $\endgroup$ Oct 14, 2022 at 4:44
  • $\begingroup$ Is it expensive in time, or in space? If the issue is related to space, you can look at Beam Search. The number of nodes in memory is always bounded by an input parameter $\endgroup$
    – fontanf
    Oct 14, 2022 at 13:36

1 Answer 1

1
$\begingroup$

Here's a few ideas:

  1. Only store the full state in the leaf nodes. Remove it from the parent nodes once all their children are created.

  2. Only store the full state in the parent/internal nodes. Each leaf node would store the diff from parent only.

  3. Store the full state every $x$ levels in the tree; the intermediate nodes would store the diff from their parent only.

  4. Use a backtracking algorithm instead of B&B so that you can 'unapply' the change when you backtrack to the parent node.

  5. If you're using B&B, you might still be able to find a common ancestor between the incoming change and the previous change; you would only have to undo changes up to the common ancestor and then reapply changes from that point to the new leaf.

  6. Maybe you can organize your tree branches by the variables that they manipulate. Then you can have each node contain a pointer to the last node with the full state. You start with that full state but refer to your local node for some specific row of variables.

  7. It may be that that your large state doesn't have to be fully reset. Consider the LP relaxation in the MIP tree; you can change the starting point without having to reset all the data in the LP.

$\endgroup$
2
  • $\begingroup$ Hi Brannon - thanks for tehcomments. I have in fact implemented (2) already! What I'm looking for is a way to place this in the existing literature. Do you know if this general class of problem is recognized already...? $\endgroup$ Oct 19, 2022 at 23:09
  • 1
    $\begingroup$ This is purely an engineering problem, and seldom are such problems deemed worthy of a PhD dissertation in the OR dept. In related academics, a number of blockchain efforts have tried to minimize undo storage for chain re-orgs. Various text and photo editors support a treed undo system, where a similar concern might apply. Among B&B algorithms, you might look for algorithms that actively drop (likely) unreachable work items from their queue. $\endgroup$
    – Brannon
    Oct 20, 2022 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.