I’d like to implement this as well, and was wondering if anyone had already done so. Could be very useful both in autonomous, and aiding the driver in teleop.
I can’t seem to find the code for their A* pathfinding algorithm implementation, just their “In Control” dashboard software.
The pathfinding software isn’t public yet, I’m currently in the process of polishing it and documenting it before release. I’d be willing to add you to the repo for it though if you want to take a look.
1 Like
Would you be willing to add me as well? I have spent a little time working with FRC 8561 on an A* based dynamic pathing system (GitHub - CshCyberhawks/ObstacleAvoidance) with the goal of testing it out in our offseason comp this October but have had some difficulty when trying to smooth out the generated paths. My GitHub is PY44N
1 Like
There, I’ve invited you.
@viggy96 If you’re interested in checking it out let me know your github username and I’ll add you.
My GitHub username is “viggy96”. Is the version of the code that runs on the roboRIO also in that repo?
Sorry for the delayed response, I got busy with something else and forgot to check. I just invited you. Also, the code that we actually ran that includes the auto scoring logic and all of that is not in this repository, but there is an example project in the i’m currently working on in the repo if you’re curious. It’s very incomplete at the moment though.
My FTC team implemented it during the 2022 offseason: https://photos.app.goo.gl/sUn2hHFWnUw65YWE7
1 Like
Wondering if I could be added too, Blaziumm is my GitHub username.
-Blazium
Just added you. I also just made a ton of changes including finally proper documentation and tons of bug fixes.
1 Like
@nab138 Any way to get more info about this project, or if you could add me to the repo? Github username is admlvntv
I’m interested to know what you think the advantage is of the pathfinder algorithm. with a preset field is it not possible to just continue using the pathing tools we already have? What are the advantages? Are we trying to produce something that can navigate arroyos other robots? Im just curious to learn what I’m missing here.
The big purpose of tools like these is to create dynamic “on the fly” trajectories, rather than having premade trajectories. This can be useful for when a driver pushes a button the robot can reach a setpoint in the shortest distance no matter its current location and without hitting anything in the field. This likely won’t be able to avoid other robots, but instead obstacles that are always in the same place on the field, such as a scoring area in the center of the field.
1 Like
I would love to be invited as well “yotam201410”
My team (2129) developed a pathfinder over the past two seasons. We started out with A* but transitioned to Theta* as it produced much better results. Our pathfinder still has both modes for comparison, but we are using the Theta* mode as it creates smoother paths. You can check out our code on our GitHub. Of the two programmers on the team, I am not the one that developed our pathfinder. We are currently using it to pathfind within a state space representation of our arm to prevent it from going into illegal positions. We used it for our first regional to score game pieces but found a human to be more reliable. I’d be happy to talk to the other programmer if you have any questions.
Update: Here’s a link to the version of our pathfinder that is written in Rust. It runs about 20x faster than the java version.
We’ve been working on our own path finding script for a short while now (after making this thread lol). It is in its early stages, but it performs pretty well. Can solve for a path in 1 second on a RK3588 powered board (like a Rock 5A or an Orange Pi 5).
Note, on initial run, it “builds” a field grid based on the selected obstacle JSON file. The resulting 2D array is then saved and used for subsequent runs.
I would appreciate thoughts/comments.
1 Like
This looks very reasonable for a first pass at A*. I can see several possible optimizations and general improvements though.
-
Don’t use Python for this! While Python gets a lot of undeserved hate for the speed of its interpreter, I think this is a case where it makes a lot of sense to switch, especially since you’re implementing all the logic in Py and not using bindings to something else. Java and C++ are the obvious alternatives, although they each have their own obvious problems. Maybe something more exotic (Rust, Go) even? With a little luck you could be around ~100 ms per execution.
-
Try making
neighborsan attribute of each node, soget_neighbors()doesn’t have to be called so much. These neighbors could also be embedded inside your cache (although I don’t know anything about numpy serialization/deserialization so I don’t know if this is easily possible). -
Splines work great for tracking hand-drawn trajectories or unobstructed on-the-fly paths, but have some significant issues when working with obstacles. The biggest problem is that they can easily end up clipping through an obstacle. This is a fairly hard problem to fix, but it is possible. I would try doing something like enforcing a minimum distance from an obstacle to a corner as a first measure, as well as using a different spline like a (scipy.interpolate.)CubicSpline.
I believe I’ve already solved the third point. There is a configurable “buffer distance” for each obstacle to help ensure that the robot doesn’t clip obstacles along the way. The buffer distance is added to the “robot radius” to produce the light grey area in the visualisation. I will try a cubic spline though.
Thanks for your other points. I started this in Python because of the speed of thought to code. But you’re probably right, I likely can’t make this much faster in Python. I’ll consider other language options.
I added you to the repo (and @yotam201410), if you have specific questions you can ask here, dm me on discord, email me, or whatever else.
I’m currently working on a video to visualize and explain how the pathfinder works, no promises but if I manage to scrape enough motivation together to finish it should be pretty cool
Glad to see theres so much interest in these projects!
1 Like