Skip to content
Snippets Groups Projects
README.md 4.02 KiB
Newer Older
yujuchiu's avatar
yujuchiu committed
# kings Planner for Instock technical interview
yujuchiu's avatar
yujuchiu committed
###### tags: `path planning`
###### Assignment introduction: [The link](https://docs.google.com/document/d/1OuxEgQZhpVOiA2Ey-UwR8KYV_ftqRZBey1ZAhPB8vC4/edit?usp=sharing)
## Code organization in main folder
    ./root
    ├── README.pdf                      # Document explaining the implementation
    ├── README.md                       # Readme file for the workspace
yujuchiu's avatar
yujuchiu committed
    ├── planner.py                      # The code of the main Planner
    ├── solution.txt                    # Output of all paths of the king
yujuchiu's avatar
yujuchiu committed
    ├── problem-tests                   # The folder of testing data                         
    │   ├──1
    │   │   ├── kings.txt               # the start and goal position of kings
    │   │   ├── map.txt                 # Info of grid 
    │   ├──2 ...

## Envorinment
* programming language: python (3.9.2)
* OS: Linux, ubuntu 20.04

## Run the code(Manually)
``` bash
python planner.py
yujuchiu's avatar
yujuchiu committed
```

yujuchiu's avatar
yujuchiu committed
## Change test data
If you want to change the test data, please add a specific file name to the command.
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
For example
``` bash
python planner.py --kings ./problem-tests/2/kings.txt --map ./problem-tests/2/map.txt
```
The default is ``--kings ./problem-tests/1/kings.txt --map ./problem-tests/1/map.txt``
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
## Solution
yujuchiu's avatar
yujuchiu committed
![solution](https://imgur.com/zFbe4M4.png)
yujuchiu's avatar
yujuchiu committed
The above sample is the solution.txt generated based on the first set of test data(``./problem-tests/2``). According to the instructions, each line is a step for a king. When the first king reaches the goal, it will continue with the second king until the end.
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
## Main Code Explanation
At the beginning, I did basic A* algorithm on all kings and stored the path. Then set the global time step to start moving individual kings and check whether there are collisions (8 cells are blocked around a king).
yujuchiu's avatar
yujuchiu committed

The strategy to resolve the collision is to move to a nearby valid position(others 3 cells), reuse A* algorithm to calculate the path to the goal(target) based on this current position, and update the original path.

Of particular note is that kings who plan their roads earlier will receive higher priority. If the latter king enters the restricted area, it will move to other valid areas nearby.

yujuchiu's avatar
yujuchiu committed
If there are only some kings that cannot reach the goal, there will be no corresponding path in the ``solution.txt``. If no king reaches the goal, the terminal will display "Plan does not exist" and no ``solution.txt`` will be generated.
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
* noted: From the instock simulation video, AMR will only move adjacent to 4 cells, so the kings in this assignment will only move adjacent to 4 cells.
yujuchiu's avatar
yujuchiu committed

## Future Work:

The current method is A* replanner and it cannot improve the success rate, especially in a limited space. The path planned by A* will give priority to reaching the destination and will not avoid other kings. Until it is necessary to pause or move, it will already cause traffic jams and make it impossible to move. This is the disadvantage of A* replanner.

yujuchiu's avatar
yujuchiu committed
The better solutions to this problem can be D* or Dynamic window approach. For D*, changing the cost function based on the A*  avoid collisions in advance based on the kings ahead(increasing weight/cost). For ynamic window approach, considering the speed rate change(suitable pause in advance) may avoid collision with other kings or entering the restricted area.
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
## Reference:
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
A* search algorithm:
https://en.wikipedia.org/wiki/A*_search_algorithm
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
Hart, P. E.; Nilsson, N.J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics. 4 (2): 100–7. doi:10.1109/TSSC.1968.300136.
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
python document
https://www.python.org/
yujuchiu's avatar
yujuchiu committed

yujuchiu's avatar
yujuchiu committed
ChatGPT(for text grammar and syntax issues)
https://chat.openai.com/
yujuchiu's avatar
yujuchiu committed

D* search algorithm:
https://en.wikipedia.org/wiki/D*

Dynamic window approach
https://en.wikipedia.org/wiki/Dynamic_window_approach

Fox D , Burgard W , Thrun S . The dynamic window approach to collision avoidance[J]. IEEE Robotics & Automation Magazine, 1997, 4(1):23-33.