OCCRA
Go to Post You can't guarantee outcomes -- only effort. If your team did its best, be satisfied. - Rick TYler [more]
Home
Go Back   Chief Delphi > Technical > Programming > Java
CD-Media  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Reply
Thread Tools Rate Thread Display Modes
  #1   Spotlight this post!  
Unread 09-02-2018, 07:18 PM
DrToWhatExtent DrToWhatExtent is offline
Registered User
AKA: James
FRC #4931 (Edwardsville Technologies)
Team Role: Programmer
 
Join Date: Feb 2018
Rookie Year: 2011
Location: Illinois
Posts: 12
DrToWhatExtent is an unknown quantity at this point
A true pathfinding library (Not a motion profiler)

I've been putting a lot of time into making a pathfinder that will take only a start and end point, and spit out a path. This uses a version of the A* algorithm. Currently it can take a 2d array, or a bitmap image to run the pathfinding on.

There's also a computating to return a path of straight line waypoints. (Could be used to make your own straight line path follower or in conjunction with a motion profiling, such as Jaci's Pathfinder.)

There's a MotorOut class which takes an accelerometer and gyro input, and gives back motor powers. Mock testing gave me a deviation from the path of ~1 inch, but we all know practice is different. Hopefully I'll be able to get this tested on an actual robot, but it probably won't happen until after GRC (End of september).

There's not a readme currently, but I did my best to make it intuitive, and I included JavaDoc. You can look at Main in github for an example. The Main class and the images folder are not included in the Jar.

I'd love to hear some feedback on whether any other teams would benefit from this.

https://github.com/ThatOneGuyFromThatOneShow/Pathfinder
Reply With Quote
  #2   Spotlight this post!  
Unread 09-18-2018, 11:32 AM
Element's Avatar
Element Element is offline
Registered User
AKA: Noah Sharum
FRC #5535 (Bionic Bison)
Team Role: Alumni
 
Join Date: Jan 2018
Rookie Year: 2017
Location: Michigan
Posts: 15
Element is an unknown quantity at this point
Re: A true pathfinding library (Not a motion profiler)

If I can get it to work on one of our robots, I believe our team could benefit from this! Thanks for sharing! Will get back to you if I can set it up.
Reply With Quote
  #3   Spotlight this post!  
Unread 09-18-2018, 11:35 AM
Element's Avatar
Element Element is offline
Registered User
AKA: Noah Sharum
FRC #5535 (Bionic Bison)
Team Role: Alumni
 
Join Date: Jan 2018
Rookie Year: 2017
Location: Michigan
Posts: 15
Element is an unknown quantity at this point
Re: A true pathfinding library (Not a motion profiler)

I will also be hopeful that you will make a readme-helper soon as well!
Reply With Quote
  #4   Spotlight this post!  
Unread 09-18-2018, 01:11 PM
DrToWhatExtent DrToWhatExtent is offline
Registered User
AKA: James
FRC #4931 (Edwardsville Technologies)
Team Role: Programmer
 
Join Date: Feb 2018
Rookie Year: 2011
Location: Illinois
Posts: 12
DrToWhatExtent is an unknown quantity at this point
Re: A true pathfinding library (Not a motion profiler)

I think I have an idea for how to structure it. I might even get it done today. I'm working on training new programmers which is why I haven't tested the path folloeer on one of our robots.

The actual Pathfinder part works. You could use it along with an autonamous system that reads each point and just goes in a straight line then turns towards the next point; repeat until at the end. We did this last year for autonomous. You can find the code here: https://github.com/frc-4931/2018-Rob...toCommand.java

On a side note. I've been going back and forth if I want to add compatibility with Jaci's path finder. If I do I'll be down the road after I get everything worked out.
Reply With Quote
  #5   Spotlight this post!  
Unread 09-26-2018, 01:52 PM
nickbrickmaster nickbrickmaster is offline
Registered User
AKA: Nick Schatz
no team ('Snow Problem, 3184 Alum)
Team Role: Programmer
 
Join Date: Jan 2015
Rookie Year: 2014
Location: Eagan MN
Posts: 478
nickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond reputenickbrickmaster has a reputation beyond repute
Re: A true pathfinding library (Not a motion profiler)

Quote:
Originally Posted by DrToWhatExtent View Post
I think I have an idea for how to structure it. I might even get it done today. I'm working on training new programmers which is why I haven't tested the path folloeer on one of our robots.

The actual Pathfinder part works. You could use it along with an autonamous system that reads each point and just goes in a straight line then turns towards the next point; repeat until at the end. We did this last year for autonomous. You can find the code here: https://github.com/frc-4931/2018-Rob...toCommand.java

On a side note. I've been going back and forth if I want to add compatibility with Jaci's path finder. If I do I'll be down the road after I get everything worked out.
The problem with this scheme is that you just have so many points (one for each pixel) and it's just not physically possible to stop and turn at every point, especially with the number of tiny turns A* takes to get the strictly shortest path.

You'll need to smooth this path out in some way for it to be useful.You could also modify the algorithm to prioritize straight lines, but the problem with applying Manhattan pathfinding to the real world is that robots, especially large tank drive robots, work on a very non-Manhattan level. One assumption that A* makes is that you can move to any other connected node with the same cost, not caring how you got to this node. This is good for video games, but very not good for robots when we consider inertia and direction of travel.

How to solve this? You can use a less discrete grid, where assumptions of A* are better satisfied. You can also use a different algorithm like Lazy Theta*, which uses line of sight to find a path.
__________________
This is a postmodern signature.
Reply With Quote
  #6   Spotlight this post!  
Unread 09-26-2018, 02:39 PM
DrToWhatExtent DrToWhatExtent is offline
Registered User
AKA: James
FRC #4931 (Edwardsville Technologies)
Team Role: Programmer
 
Join Date: Feb 2018
Rookie Year: 2011
Location: Illinois
Posts: 12
DrToWhatExtent is an unknown quantity at this point
Re: A true pathfinding library (Not a motion profiler)

Quote:
Originally Posted by nickbrickmaster View Post
The problem with this scheme is that you just have so many points (one for each pixel) and it's just not physically possible to stop and turn at every point, especially with the number of tiny turns A* takes to get the strictly shortest path.

You'll need to smooth this path out in some way for it to be useful.You could also modify the algorithm to prioritize straight lines, but the problem with applying Manhattan pathfinding to the real world is that robots, especially large tank drive robots, work on a very non-Manhattan level. One assumption that A* makes is that you can move to any other connected node with the same cost, not caring how you got to this node. This is good for video games, but very not good for robots when we consider inertia and direction of travel.

How to solve this? You can use a less discrete grid, where assumptions of A* are better satisfied. You can also use a different algorithm like Lazy Theta*, which uses line of sight to find a path.
This is very helpful, and I've considered most of this.
The idea behind the follower is to be able to smooth it out without needed to run a separate algorithm, as it doesn't directly turn at any point. I'm thinking running it into a PID type system. There is a way to reduce the path into straight lines from the A* path, only available based on the FRC implementation. I've looked into straight line search algorithms but most of them align to the grid which is not something I want.
Reply With Quote
  #7   Spotlight this post!  
Unread 09-26-2018, 02:51 PM
DrToWhatExtent DrToWhatExtent is offline
Registered User
AKA: James
FRC #4931 (Edwardsville Technologies)
Team Role: Programmer
 
Join Date: Feb 2018
Rookie Year: 2011
Location: Illinois
Posts: 12
DrToWhatExtent is an unknown quantity at this point
Re: A true pathfinding library (Not a motion profiler)

After Gateway Robot Challenge this weekend I'll be able to testing on our robots. I'm currently working on refining a couple things in order to be able to test right when I get access to the robots.
Reply With Quote
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT -5. The time now is 02:08 AM.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin®
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi