Total concurrency and uncertainty in linguistic geometry

摘要

Considers an example of application of linguistic geometry to the search multiagent problem with an extremely high branching factor, this problem is computationally hard for conventional approaches. The high computational complexity is explained by the allowance of concurrent motions of all the agents. This results in a significant growth of the branching factor (up to 300) because all the combinations of simultaneous motions are legal. Another difficulty is that when making a move, each side is uncertain about the concurrent motions of the other side. The linguistic geometry tools generated a solution of the problem demonstrating a dramatic search reduction for this totally concurrent system.