Lyra Graphtool Tutorial

• Introduction
  • Welcome to the Off the Beaten Path Xeek Challenge!
  • This is a fun and unique variation of the traditional travelling salesman problem.
  • In the traditional travelling salesman problem, the goal is to optimize the route that the “salesman” has to walk. This challenge introduces additional constraints and additional degrees of freedom (variables) to the problem. Not only will you be considering the distance to travel, but additional factors like simulation duration, budget, amount of rewards extracted from a particular site, and the cost of a worker. The solution to the challenge is not only the plan, but also an algorithm that will be tested on other problem setups (different graphs to explore, different values of constraints), therefore you have to keep in mind, that you are developing a universal tool for finding a solution.
  • The Xeek team has built a unique and powerful tool, called lyra_graphtool, to help you skip the graph setup part of the challenge and get to the important part; generating an algorithm to optimize the problem! This notebook, as well as a random walk exmaple solution and API Documentation will serve as your documenation and learning resources for the challenge.
  • Please use the links below if you would like to jump to a specific Object in this notebook, as well as a starter notebook with an example solution!
• Initial Setup
  • Upon starting this challenge, competitors will need to download the required matrials from the Off the Beaten Path challenge page.
  • The Xeek team will provide:
  • Note: Ensure that the lyra_graphtool folder is saved in your project folder to avoid import issues
  • Now let’s get started!
  • Run the next 3 code cells in order to setup graphs, budgets, worker costs, rewards, and duration. Double check to make sure the file paths for the lgtool.ProcessArgs.load() are correct.
• ProcessArgs Object
  • The ProcessArgs object will be used in the intial setup of the problem. Xeek will provide the setup parameters for the graph and arguments file for the challenge. Challengers do, however, have the tools to create their own argument files. Remember, the final scoring will occur on a different argument file than what is provided, so it is to your advantage to create your own argument file(s) and test your algorithm to see if it is effiecient for all scenarios. Below will explore the functionality of the ProceesArgs object, by building a test arguments/graph file.
  • Create a ProcessArgs object and pass the new argument file through it
  • ProcessArgs.save()
  • ProcessArgs.load()
  • load_graph()
  • ProcessArgs.values_to_args()
• Parameters Object
  • The loaded arguments and graph can be wrapped with lgtool.Parameters class which can be further passed to the lgtool.Configuration() object.
  • display()
• Configuration Object
  • The lgtool.Configuration() object contains not only the graph to be optimized, but also problem constraints and setup like budget, duration, and worker cost rates. Pass the arguments run through the lgtool.Parameters() section for set up. This module will be the workhorse to solve the challenge because it allows users to add, update, and extract most parameters for the challenge.
  • add_sched()
  • budget_feasible()
  • cost()
  • cost_sched()
  • feasible()
  • get_accessed_sites()
  • get_current_workers()
  • get_max_revenue()
  • get_sched_path_length()
  • get_vertices_start()
  • get_worker()
  • is_empty()
  • load_from_json()
  • revenue()
  • save()
  • save_to_json()
  • sched_all_feasible_access_sites()
  • sched_all_feasible_space()
  • sched_feasible_access_sites()
  • sched_feasible_space()
  • sched_info()
  • sched_revenue()
  • site_accessed()
  • site_accessed_at_time()
• Edge Object
  • Edge.info()
  • in_graph()
  • nearest_neighbor()
• Graph Object
  • add_vertex()
  • adjacent_vertices()
  • closest_vertices()
  • connected_components()
  • depth_first_search()
  • distance()
  • get_edges_at_vertex()
  • edges_info()
  • get_vertex_xy()
  • get_vertices_type()
  • isolated_vertices()
  • load_from_json()
  • make_graph_connected()
  • paths()
  • print_graph()
  • Graph.save()
  • Graph.save_to_json()
  • set_edges()
  • set_random_sites_origin()
  • set_vertex_type()
  • set_vertex_coords()
  • vertices_array()
  • vertices_info()
• Vertex_Type Object
  • Vertex_Type is used to store and define each location type on the graph. These variables will contain spatial location information, as well as reward amount and time to extract. SITEs 1,2 and 3 can contain varying reward amounts.
  • Vertex_Type.BASIC - BASIC is a location in space, neither a SITE nor the ORIGIN (regular point on the graph)
  • Vertex_Type.ORIGIN - starting point for workers
  • Vertex_Type.OTHER
  • Vertex_Type.OTHER2
  • Vertex_Type.SITE1 - point on graph with reward
  • Vertex_Type.SITE2 - point on graph with reward
  • Vertex_Type.SITE2 - point on graph with reward
• Vertex Object
  • The Vertex object allows users to create vertices for that graph by defining characteristics such as coordinates (x,y), Vertex_Type, rewards available at given site, site expiration time, and time to aquire. Below we create a vertex object and assign attributes.
  • Vertex.info()
  • accessible_types()
• Worker_Type Object
  • Worker_Type holds the variable information the three types of workers: WORKER1, WORKER2, and WORKER3. Each worker is assigned an order, and this can be viewed by calling .worker_types on the configuration ocject created in the initial setup.
  • In the Configuration-Object section above you can see how to get the cost rate assigned to each worker for the configuration.
• Worker Object
  • The Worker object contains the information about worker type and associated cost rate.