------Pathfinding Agent------ Path planning simulator for the Apparate platform. Uses Deadline-Aware Search augmented by dynamic weights. Author Pulkit Karwal Apparate platform developed by: Sebastian Sardina Andy Heng Xie Nitin Yadav Repo: https://bitbucket.org/ssardina/apparate/overview ---Introduction--- The agent uses Deadline-Aware Search (DAS) algorithm to perform efficient and time-conscious path planning. The agent is based on the Apparate platform, designed to run on Apparate using JPathPlan. The algorithm for the agent, DAS, has been sourced from the paper [1] by Dionne, Thayer and Ruml. The agent uses octile distance measure as heuristic, supported by a basic implementation of preferred operators. ---Usage Instructions--- The agent can be executed by running agents.MyCoolAgent. The agent uses an additional class agents.pulkit.GridCellInformed for operation. The class acts as a GridCell extension allowing storage of DAS-specific parameters (costs and expansions), and includes a comparator for automatic tie-breaking. ---Modifications to the DAS Algorithm--- 1. Track the average time taken to execute a DAS iteration. Don’t run the DAS loop if this amount of time is not left. Prevents over-consumption of time. - Computed as the time elapsed between node expansions. This ensures that DAS doesn’t enter a loop when it knows it won’t have enough time to complete the iteration. 2. Use Greedy search to compute a goal first. - Not only does this act as a contingency solution, it is also used to test the time we need to reserve for generating a path object. 3. Use octile distance for improved estimation. 4. Add weights to cost values as time runs out. - Weights are applied to the heuristic and actual costs (h and g) for increasing the influence of h as we run out of time. This hastens progress towards the goal. ---Agent Design--- The architecture of the agent is divided into two layers: 1. Core Search Layer While the search is performed only once for a given problem state, it is carried out in two calls to the agent’s getNextMove() function. The agents performs the following actions in those calls, respectively: 1.1 Greedy Search - First, the agent generates an incumbent solution. The agent doesn’t stop if the Greedy search can’t find a solution. A path is generated and stored, and the time taken to do so is recorded. 1.2 Deadline-Aware Search - Next, DAS is executed over whatever time is left (with some time reserved to generating the path from the solution, using the time obtained above). Each time DAS tries to recover pruned states, the weight over the heuristic is adjusted to further propel the agent towards the goal. 2. Dynamic Map Response Layer In order to cater to the varying nature of the problem, this layer is added on top of the core. It determines the action required (the degree to which we need to re-plan, for example), depending on the situation. 2.1 Map has changed - If the changes affect the current path, the agent will begin to re-plan from its current position towards the goal. 2.2 Goal has moved - If the goal has moved away from the agent, then ignore the change until we reach close to the goal (or alternatively, plan a path from the old to the new goal position and append it to the current path plan). The agent will, thus, need a much shorter time for re-planning. Else, all heuristic information is unusable now, and it is better the agent initiates a complete replan. 2.3 Time has increased - In the event that the time allotted is increase without any of the above accompanying changes, the agent will take this opportunity to resume DAS where it left off, to try and improve the solution. 3. Tie-Breaking Equally attractive nodes are distinguished using the f, g and h costs in the following order: 1. Weighted costs: f, then h, then g 2. Unweighted costs: unweighted f, unweighted g (if any) 3. Expansion time: e – allowing nodes that have been opened later to be given higher preference. ---Heuristic and Weights--- Instead of Manhattan or Euclidean distances, a common octile heuristic is used by the agent. The heuristic utilizes a rudimentary implementation of preferred operators: any direction of motion in the general (and thus, preferred) direction of the goal is rated higher than otherwise. This allows calculating heuristic value by simply incrementing or decrementing from the parent node’s heuristic value depending on the move direction. Having avoided recalculation of heuristic for every child node, this algorithm performs considerably faster. To improve the performance of DAS, the concept of automatically varying weights has been adopted from Anytime Repairing A* (ARA) algorithm [2]. If the DAS has pruned everything and finds itself trying to recover pruned states, the agent adjusts the weight of h suitably for the next DAS iteration. The weight is applied to the cost as follows: f = g + w(h) * h It depends on time and increases automatically as time runs out. w(h) = initial time allotted / time left Additionally, weight can be applied over real cost g, or specifically over the parent’s contribution towards the g cost at any intermediary node along the path. Note: Adding weight to g seems most effective, though it is infact a case of overfitting. ---References--- [1] Dionne, A. J., Thayer, J. T., Ruml, W (2011) Deadline-Aware Search Using On-line Measures of Behavior [2] Richter, S., Thayer, J. T., Ruml, W (2010) The Joy of Forgetting: Faster Anytime Search via Restarting [3] Burns, E., Hatem, M., Leighton, M. J., Ruml, W (2012) Implementing Fast Heuristic Search Code