FIT5222 Planning and automated reasoning Introduction to Flatland Version 1.1 Flatland Flatland is an open-source toolkit for developing Multi-Agent Pathfinding algorithms in grid rail worlds. It provides a two-dimensional grid environment in which many agents can be placed, and each agent must solve one or more navigational tasks in the grid world. The library was developed by SBB, AIcrowd, and numerous contributors and AIcrowd research fellows from the AIcrowd community. In this unit, you can implement anything you learnt in Flatland. Part 1: Installation Refer to Week 1 Installation Guide to Install Flatland on your computer. You must update your flatland code and installation before starting the assignment: ● Under flatland folder ● git stash save (In case you have unstaged changes made in week 1) ● git pull ● git stash pop ● python3 setup.py install ● Now, run command python3 -m pip list , you should see flatland-rl version is updated to 2.2.4 ● (Hint, use python instead of python3 if python points to the right one on your machine)FIT5222 Planning and automated reasoning Part 2: Basic Rules with Flatland Characteristics: ● Flatland simulates a railway environment in a 2-dimensional grid space of any size. ● Flatland is a discrete-time simulation. A discrete-time simulation performs all actions within a constant time step. ● An agent can move in any direction on well-defined transitions from cells to cells. ● The capacity of a cell is usually one. Thus usually only one agent can be located at a given cell. ● At each step, the agents can choose an action. For the chosen action the attached transition will be executed. ● While executing a transition, Flatland checks whether the requested transition is valid. If the transition is valid, the transition will update the agent’s position. ● While executing a transition, a malfunction may happen which prevents agents from moving toward their intended target locations. Each malfunction lasts for a certain period of time and during the malfunction affected trains are unable to move. Malfunctions only occur in question 3. ● Also, each agent is assigned a start and goal location. Our target is to find paths for each agent while minimizing the sum of their individual path costs or total makespan. ● Each instance have a max time step limit, which is 1.5 * rail.height * rail.width. All agents need to arrive at their destination before this max time step limit. Grid: A rectangular grid of integer shape (dim_x, dim_y) defines the spatial dimensions of the environment. We use North, East, West, South as orientation indicators where North is Up, South is Down, West is left and East is Right. Each cell in the grid environment can be located by (row, column) coordinate. Here is an example:FIT5222 Planning and automated reasoning A pair of row and column coordinates can also be converted to a single integer by row × map_width + column. Tile Types: Each Cell within the simulation grid consists of a distinct tile type which in turn limits the movement possibilities of the agent through the cell. For railway specific problem 8 basic tile types can be defined which describe a rail network. As a general fact in the railway network, there are at most two branches available at any junction point with any entry direction. The following image gives an overview of the eight basic tile types. These can be rotated in steps of 45° and mirrored along the North-South of the East-West axis. Refer to Appendix A for a complete list of tiles. ● Case 0 represents a wall, thus no agent can occupy the tile at any time. ● Case 1 represents a passage through the tile. While on the tile the agent can make no navigation decision. The agent can only decide to either continue, i.e. passing on to the next connected tile, or wait at the current tile. ● Case 2 represents a simple switch, thus when coming to the top position (south in the example) a navigation choice (West or North) must be taken. Generally, the straight transition (S->N in the example) is less costly than the bent transition. Therefore in Case 2 the two choices may be rewarded differently. Case 6 is identical to case 2 from a topological point of view, however, there is no preferred choice when coming from the South. ● Case 3 can be seen as a superposition of Case 1. As with any other tile at maximum one agent can occupy the cell at a given time.FIT5222 Planning and automated reasoning ● Case 4 represents a single-slit switch. In the example, a navigation choice is possible when coming from the West or South. ● In Case 5 coming from all directions, a navigation choice must be taken. ● Case 7 represents a dead-end, thus only stop or backward motion is possible when an agent occupies this cell. Execution and Termination ● For each question, the simulator will execute the computed plan for each agent. ● Execution proceeds by applying the next planned action for each agent in some specified ordering determined by the simulator. ● Execution stops when any agent is unable to execute their next planned action. At this point the simulator calls a replan function and all agents have an opportunity to recompute their paths. ● Evaluation of current instance terminates, when one of the following conditions is met: ○ All agents reach their destination collision-free. ○ All of the planned actions of all agents are executed or, ○ The maximum number of timestep is reached Part 3: How to interact with the flatland environment. Information related to question 1 and question 2 Flatland environment All the information about the map is stored in an object of GridTransitionMap. In the example of the next chapter, the variable rail is the object of GridTransitionMap. Width and height: ● Get map width by rail.width ● Get map height by rail.height Get available transitions: cell_transitions = rail.get_transitions(x, y, direction) and in return you get an array with possible transitions in each of the four cardinal directions [North, East, South, West]. The x and y is the location coordinate of the current cell where x in [0, height] and y in [0, width]. Depending on the tile type, at most two of the returned directions will be valid transitions. Be careful with the heading direction! Different heading direction for the same cell will return different available transitions. Thus you need to correctly specify the current position and direction. These important pieces of information are both parts of your agent’s state! Also, be careful about heading direction’s influence on heuristics!FIT5222 Planning and automated reasoning Cannot find paths: In question 2, it is possible that a very small number of agents’ paths cannot be found by your algorithm as moving obstacles may traverse through the start location of your agent. You can simply return an empty list in this case, and the agent with an empty list will not show on the map. Note, this only happens to not more than 5 or 6 instances, with only 1~2 agents have no paths. Information related to question 3 Get agent information: Agents information is stored in agents which is a list of EnvAgent objects. An EnvAgent object contains the following attribute: ● initial_position A tuple of (x,y). The initial location of the agent. ● initial_direction An integer in [0,1,2,3]. The initial heading direction of the agent. ● target A tuple of (x,y). The goal location of the agent. ● position A tuple of (x,y). The current location of the agent, this is used when a plan is in execution, which means . ● direction An integer in [0,1,2,3]. The current heading direction of the agent. ● status An integer in [0,1,2]. The current status of the agent. ● deadline An integer indicates the expected latest arrival timestep of the agent. ● malfunction_data A dictionary stores data related to malfunctions. You will use the initial_position, initial_direction, and target of each agent to plan paths for them. The position and direction will be used on the execution stage. Agents arriving at goal locations after the deadline timestep will receive a penalty. The heading direction of the train is represented by an integer: ● 0: North. ● 1: East. ● 2: South. ● 3: West. The status is an integer: ● 0: The agent is not active (not on the map). ● 1: The agent is active (on the map).FIT5222 Planning and automated reasoning ● 2: The agent reaches the goal location. ● 3: The agent reaches the goal location and is removed from the map. Executing your coordinated plan By default, when plan execution starts, the status of the agent is 0 and the position is None. By giving a move forward command, the status turns to 1, position=initial_position and you can start executing your plan. When the agent reaches its goal location the status of the agent turns to 3. During execution, it is possible your planned actions may fail due to malfunctions (i.e., the train experiences a mechanical problem) . The malfunction_data object is a dictionary that contains the following information: ● “malfunction” : int A number that indicates how many timesteps n the malfunction lasts for. When n > 0 the agent will not be able to execute any command for the next n timesteps. In other words, the agent must wait in place for the malfunction to pass (i.e., until the train is repaired!). Replan When a new malfunction occurs or if two agents plan to execute a pair of incompatible actions (i.e., leading to a collision), the system will call a replan function to provide a new set of feasible paths. The new paths should consider that agents can only wait at the current location during the malfunction timesteps. Some extra information that is available to the replan function: ● current_timestep At which timestep during the execution, the replan function is called. ● existing_paths The paths from the previous get_path/replan function call. ● new_malfunction_agents A list of ids of agents that have a new malfunction happens at the current time step (Does not include agents already have malfunctioned in past timesteps). ● failed_agents A list of ids of agents that failed to reach their intended location at the current timestep. It usually includes new malfunction agents, other agents influenced by the malfunction agents (i.e., knock-on effects), and agents with failure execution due to collisions in their current plans. Should find paths for all agents: In question 3, you have full control on all agents. Thus, we expect you to find paths for all agents.FIT5222 Planning and automated reasoning Part 4: Codes for Assignment 1. Get Piglet assignment 1 branch We release the assignment 1 code base as a separate branch in piglet. Follow the following steps to switch between branches in piglet and get assignment 1 branch. 1. Assuming you are currently working in the “single-agent-prac” branch, and want to checkout to the “assignment1_2023” branch. (To know what branch you are currently working on, use ‘git branch’ command under piglet-public) 2. Discover new branches in the remote repository: git fetch this command should show what it discovered from remote repo. 3. If you made any changes in the “single-agent-prac” branch, you should stage and commit your changes to the piglet (which saves all your changes and allows you to checkout to another branch): cd to the piglet-public folder. git add * this command will stage all your changes in piglet (or use git add path/to/changed/file to stage a single file) git commit -m “Describe what you did” this command will commit (save) all your changes. 4. Checkout to the target assignment branch: git checkout assignment1_2023 You could discover more geek style usage of git from the git tutorials we recommended on week 1, which could speed up your version management and development efficiency. Question scripts You will find question1.py, question2.py, and question3.py in the root folder of the piglet. ● question1.py requires you to implement a single-agent pathfinding algorithm for flatland. ● question2.py requires you to avoid conflicts with existing paths. ● question3.py requires you to implement a multi-agent pathfinding algorithm, and a replan function to handle malfunctions. Each question python script includes a get_path() function with different parameters. You need to implement your algorithm inside the get_path() function and return the required data. On default get_path() functions include some dummy implementation. They only can generate some dummy paths. Replace them with your implementation. Also, you can read these dummy implementations to learn how we use parameters and what kind of data we return.FIT5222 Planning and automated reasoning Test your implementation To test your implementation, run command (Make sure your conda virtual environment is activated): python3 question1.py You can replace question1.py with question2.py or question3.py for other questions. The script will output statistic data at the same time. Debug and visualizer You can find two variables “debug” and “visualizer” in each question script. If “debug” is set to True, the script will: ● output detailed execution information. ● pause program if conflict happened or meet other errors. ● output conflict details. If “visualizer” is set to True, the script will: ● show your plan with a nice visualizer. ● show agent id if “debug” also True. If “test_single_instance” is set to True, the script will: ● evaluate only instance specified by “level” and “test”. Submission of Assignment Follow instructions in the assignment description to submit the zip file to moodle. Follow the Contest Server submission instructions to submit to the contest server. Part 5: Practice – Navigate a train with your keyboard (Optional). This part helps you learn more about Flatland. Follow these instructions to create a keyboard navigated train driving program with Flatland. 1. Create an empty python file 2. Insert following codes to import necessary modules that will be used in this practice:FIT5222 Planning and automated reasoning #import necessary modules that this python scripts need. from flatland.envs.rail_generators import complex_rail_generator from flatland.envs.schedule_generators import complex_schedule_generator from flatland.envs.rail_env import RailEnv from flatland.utils.rendertools import RenderTool, AgentRenderVariant import time 3. Insert following codes to initialize Flatland Railway environment: #Initialize Flatland Railway environment railWaySettings = complex_rail_generator( nr_start_goal=10, # Number of start location and train station pairs nr_extra=10, # Extra rails between each pair of start and goal. min_dist=10, # Minimum distance between start and goal locations max_dist=99999, seed=999) env = RailEnv( width=15, #Width/columns of grids height=15, #Height/rows of grids rail_generator= railWaySettings, number_of_agents=1) # How many trains are enabled. env.reset() # initialize railway env # Initiate the graphic module render = RenderTool(env, gl=”PILSVG”, show_debug=False, screen_height=500, # Window resolution height screen_width=500) # Window resolution width render.render_env(show=True, frames=False, show_observations=False) window=render.gl.window #We will use this window object to capture user input 4. Insert following codes to capture keyboard press event and store the key to a variable: #Capture key press event from window and set pressed key to pressedKey variable pressedKey = None #store pressed key here keyMap={“Left”:1,#Turn left “Up”:2,#Go forward “Right”:3,#Turn right “Down”:4#Stop } def _keypress(event): global pressedKeyFIT5222 Planning and automated reasoning if event.keysym in keyMap.keys(): pressedKey = keyMap[event.keysym] #retrieve corresponding actions from keyMap window.bind(“<KeyPress>”, _keypress) # bind keypress event to our function 5. Insert following codes to define controller function, which is the most important part you should pay attention: #Define Controller def my_controller(number_agents,timestep=False): _action = {} global pressedKey #declare pressedKey is a global variable if timestep: #In the first frame of flatland, agents aren disabled, # use any action to enable agents. for i in range(0,number_agents): _action[i] = 2 return _action #Retrieve pressed action and put it into an action dictionary. #We only have 1 agent in this practice, # thus we assign the pressed action only to agent 0 if pressedKey is not None: _action[0] = pressedKey else: _action[0] = 0 pressedKey = None return _action 6. Insert following codes to create the main loop of this practice: #Main loop cost_dict={} #Record cost for each agent timestep = -1 #all agents are disabled in the first makespan, so we start from -1.. all_done = False while not all_done: #Call controller function to get the action dictionary for all agents _action = my_controller(len(env.agents), timestep == -1) #Pass action dictionary to railway env and execute all actions. obs, all_rewards, done, info = env.step(_action) all_done = done[“__all__”]FIT5222 Planning and automated reasoning #count cost for each agent for key,value in done.items(): if value == False and key != “__all__”: if key not in cost_dict.keys(): cost_dict[key] = 1 else: cost_dict[key] += 1 timestep+=1 render.render_env(show=True, frames=False, show_observations=False) time.sleep(0.25) print(“Sum of individual cost: “, sum(cost_dict.values())) print(“Total makespan: “, makespan) 7. Run the python program under the virtual environment you created. If you use a Python IDE, you should try to find a virtual environment setting and select the correct one. Making sure the railway window is in the front when you press array keys. Hint: Flatland Documentation: The Flatland simulator has a rich API with many useful functions and descriptions of how they work. You may find it helpful to explore the official documentation when developing your planner. Selecting a virtual environment: When editing with VS code or Pycharm, the default environment is likely base python. This environment does not have the necessary libraries for the Flatland environment. For this reason you will likely need to specify the correct virtual environment you have already set up for the Flatland challenge. VS Code: 1. Install python extension for your VS Code. 2. Select a virtual environment by clicking the “Python” text on the bottom-left corner of the window: Pycharm: 1. Click the “Python” text on the bottom-right corner to select virtual environment:FIT5222 Planning and automated reasoning