A* with dynamic operator reception
In some applications, some of the operators involved in A* might not be relevant to reach goal state. If we somehow (machine learning etc.) sort the operators by their relevance, we can apply operators by giving priority to operators of high relevance. Therefore, the objective is to tweak the A* algorithm such that it can cope with dynamic addition of operators to it’s operator set. This article discusses several approaches which preserve completeness and optimality of the algorithm while achieving our objective.
A* algorithm
A* algorithm is a search algorithm which uses fcost, sum of path cost and heuristic estimate, as it’s cost function and tries to achieve goal. If the heuristic estimate being used is admissible, then A* algorithm finds optimal solution. In A* algorithm, we use open list and closed list to keep track of unexplored and explored nodes respectively.
Dynamic A*
Dynamic A* (DA*) is an algorithm which can cope with increasing number of operators. We will receive several operatorchunk which are set of some operators. Each time we consider a new operatorchunk, we add it to our set of operators operatorlist. We’ll also assume that we’ll get indication, haltmessage, indicating that no more operatorchunk will be received. In the following subsections, we will discuss several versions of DA*
Subspace Exhaustion DA*

In this version DA* algorithm (SEDA*), we take latest operatorchunk, explore the search space until it’s exhausted, then take the next. We loop until we receive haltmessage or expand the goal state.

In SEDA*, instead of maintaining open list and closed list, we maintain fresh list and stale list.

In SEDA*, as soon as we consider a new operatorchunk, we add all operators in operatorlist. Also, we move operatorchunk to freshoperators (we don’t add, we substitute).

States are operated upon sequentially, first we operate all states in stale list with freshoperators and add all the newly generated states to fresh list. Once we exhaust stale list, we start operating states in fresh list with operatorlist. We add all the newly generated states back to fresh list in that order so that states in stale list are sorted according to fcost (for maintaining the optimality of the algorithm). Also we add all the operated states in fresh list to stale list.

Visited states are tracked (all visited states are in stale list) and no visited state is added to fresh list.

All the states in fresh list are sorted according to their fvalue and operated accordingly.

Next operatorchunk is requested once the fresh list is exhausted.
Time Exhaustion DA*

In this version of DA* algorithm (TEDA*), we take an operatorchunk, explore the search space until it’s operatetime is exhausted, then consider the next. The operatetime represents how long to explore search space using the operatorchunk under consideration.

TEDA* maintains following state lists:
 open list
 Used as a local open list (with respect to operatorchunk) while operating using an operatorchunk. The states in this list are sorted according to their fvalues.
 stale list
 Used as a local (with respect to operatorchunk) closed list while using an operatorchunk.
 closed list
 It’s a permanent closed list.
Note: During simulation (using an operatorchunk) all the explored nodes are moved to stale list (acting like closed list in A*) and nodes are nodes are picked from open list (acting like open list in A*).

We operate states from open list (if not already visited by current operatorchunk) using operatorchunk under consideration. Now there can be few cases:

If haltmessage is not received, the expanded node is added to stale list.

If haltmessage is received and the operatorchunk is not the last chunk (for details read points below), the expanded node is added to stale list.

If haltmessage is received and the operatorchunk is the last chunk, the expanded node is added to closed list.
Whenever we consider the next operatorchunk, all the nodes in the stale list are filled back into open list.


In TEDA*, we record all the operatorchunk and store the m^{th} operatorchunk as m^{th}_gen_operators. We’ve knowledge of what all states are operated with i^{th}_gen_operators (We can do this by annotating each states with all operatorchunk applied to it).

There are two instances under which this algorithm halts:

It receives a haltmessage and open list is empty.

It expands the goal state.


The operatetime here can be chosen as per choice and purpose of use. One can try to choose operatetime that has correlation with the degree of relevance of operators etc.

Just for clarification, every i^{th}_gen_operators will be run for operatetime corresponding to it’s operatechunk.

We assume atomicity of expanding a state with respect to operatorchunk.
Conclusion
We discussed two A* based techniques which can handle dynamic operator reception. These techniques can be useful when we learn about our operators dynamically. Also they are helpful when we have some relevance based sorting of our operators, since we’ll reach goal state faster in the new restricted search space.
Lashit Jain