Hashing

[eakirtas]

Hello Team,

As the hashing is necessary for me I come up with the following idea.

• Every Predicate has a name with the following form:
  • <Predicate_name>_<arg0><arg1>
  • ex. Robot_robota
• Every state uses all predicate to define it's name
  • <Pedicate_name_1>_<arg0><arg1><Pedicate_name_2>_<arg0><arg1>
  • ex. Robot_robotaAt_roomaballb
• Finally, get MD5 hash of the state name (I call it ID)
  • ex. 31ae6009aaa5b874dd25b139533afe05

The great about MD5 hash is the fact that any small change in the state name cause great change in the ID

Robot_robotaAt_roomaballb -> 31ae6009aaa5b874dd25b139533afe05 Robot_robotaAt_roombballb -> 96c3ba1f837d7eab22d8773070079d28

However, this should be transformed into a unique number. Do you have any ideas how?

[Adamantios]

Why not a unique number for every predicate and every object and then simply concatenate the numbers? No MD5 hashing needed and a unique number occurs. For example:

• Move (RobotA, RoomA, RoomB), Move (RobotB, RoomA, RoomB) -> 0134 , 0234

After that it is easier to go back from 0134 , 0234 to Move (RobotA, RoomA, RoomB), Move (RobotB, RoomA, RoomB) which is something we need, in order to print the final plan.

[eakirtas]

This means that we should make a preprocess over the data. We need to iterate among all arguments and set them with a unique number. We should no fail to mention that arguments dont have a class, they are just lists of strings. Except that we dont know the size of arguments' list prior to runtime. If the can overcome those problem I totally agree with.

[Adamantios]

We need to iterate among all arguments and set them with a unique number

I don't think this is a problem, compared to the string comparisons that would need to be done without the hashing.

Arguments don't have a class.

Why is this a problem?

We don't know the size of arguments list prior to runtime.

We don't need to know it prior to runtime. We are going to do the hashing after the parsing. In fact I think we could do the hashing in realtime, using the unique ids of the actions and arguments and not store all the possible hashed values.

[tsampazk]

First of all @ManosMagnus is talking about hashing states, @Adamantios example talks about hashing actions. We need to clear that up.

Following @Adamantios line of thinking, we need to assign a unique integer number starting from 1* to all objects (values assigned to parameters) and actions. This is easy to do during startup, by creating a "dictionary".

(* the final int shouldn't start with 0?)

Then for every action occurring on various steps of the algorithm, we convert it to a unique integer by concatenating integers from the "dictionary". So, for comparing, searching, etc. over vectors of Actions, we work with integers and not strings (this, i suppose is our goal for all of these).

To sum up, we need two methods, one that takes a string (eg. "actionName(par1Val, par2Val)" or "move(roomA, roomB)") and uses a predefined "dictionary" of action names and objects to ints, to convert it to an integer. The second method takes an integer and using the "dictionary" in reverse, produces the action as a string. This second methods need a delimiter to figure out where each separate integer is. For example if a converted action is something like 1234, it might be action 12, object 3, object 4, or action 1 with objecs 2,3,4, etc.

[Adamantios]

First of all @ManosMagnus is talking about hashing states, @Adamantios example talks about hashing actions. We need to clear that up.

I think we should encode anything the Planner interacts with.

This second methods need a delimiter to figure out where each separate integer is

Great point! We could use a number for this. Lets say 9, for example.

[efikalti]

Great point! We could use a number for this. Lets say 9, for example.

So the example @tsampazk mentioned would be encoded like : 129394 , for Action 12 and params 3 and 4

So the encoder will skip all the numbers containing a 9 when building the dictionary

[tsampazk]

@Adamantios , @efikalti i suggest 0, because it will not be used anyway. This also means that we skip all numbers containing it, eg. 10, 20, 30, etc.

[efikalti]

Sounds good. I can work on it tonight if everyone agrees. Just to clarify a dictionary for both actions and states or two different dictionaries, one for actions and one for states?

[tsampazk]

Wouldn't it be better to have a single dictionary for everything so as not to have to make distinctions later?

In separate dictionaries we will have 'collisions', eg. action 32 vs object 32 vs predicate 32, etc.

[efikalti]

Pushed Hashing branch with variables and functions as discussed. Minor change: instead of string with name and params, functions expect and return vector<string> with these objects. I thought it would be easier to handle both inside and outside of Hashing, instead of tokenizing and concatenating strings. @ManosMagnus check it and tell me if you need anything @Adamantios @tsampazk

[Adamantios]

Using C++ built in hash from now on.