The classic route planning problem involves finding the least cost path from one point to another. Typically, the search domain will be turned into a grid, with costs associated with each cell in the grid. The cells that have high cost, represent areas that are undesirable or impossible to traverse. A search algorithm, such as depth first, breath first, or A* can search the grid beginning from the start point, with a small bias in favor of nodes nearer to the end point.
The number of divisions in the grid will affect the resolution of the result, and produce sub-optimal results when the gap between two un-traversable areas are smaller than the division itself. Increasing the number of divisions greatly increases the time taken to search.
The nature this algorithm is such that until the search travels from one point to another (or variants such as two search points beginning from the start and end points meeting in the middle), there is no solution - not even a sub-optimal one. For long routes, or when the cell divisions are very small, the search can take a long time.
Software agents are persistent programs that react autonomously to the environment, in order to achieve set goals. This project will attempt to use software agents to solve the route planning problem. Each agent will represent a single waypoint of the route, and will adjust itself continuously in order to reduce the cost incurred in traversing from the previous node to itself, and in traversing from itself to the next node.
A management agent will control all agents, creating an agent in the middle of a leg when the leg's cost exceeds a certain threshold. It will also be responsible for destroying agents when they meet at the same point, or when an agent has achieved stability while being lined up in a straight line in between two points.
This methodology allows agents to execute in parallel, for example, in multiple cores of a processor, or even distributed among multiple CPUs. It will also free the solution from the constraints of grid resolution, as agents can take steps of different sizes as they migrate to an optimum position. For example, if the current cost for an agent is very high, it may be inclined to take larger steps, while when an agent detects that it is oscillating about a certain point, or when the cost is lower, to take smaller steps to give it more precision.
The agents could also have a social ability, where agents consecutive to each other the in the route can move with some coordination.
While agents move, the solution may be sub-optimal but the cost incurred may already be below the targeted threshold, this allows the management agent to produce a quick solution, while allowing a more optimal solution to be produced later.
Uploading ....