Turning a tablature file into a set of physical motions on the robot involves a lot of software work: parsing a GuitarPro file, considering potential fingerings for each note, planning the transitions between those fingerings, and optimizing the solution around the physical constraints of the machine. While it is tempting to build a robot first and program it later, much of the software work that will eventually be required anyway can be used to help consider different physical limitations of the machine. This information informs the prototype design and hopefully reduces the number of iterations required to build a functioning robot guitar!
Fingering Analysis
The general goal for this fingering analysis is to expand on the chord analysis used in the previous post to include the effects of transitionings between different fret positions. Instead of using a dataset of static chord fingerings, a representative selection of melodies (in the form of guitar pro tablature files) were used as the basis for the analysis.
Existing Research
There is quite a lot of academic research on algorithms for determining ‘optimal’ guitar fingering of a melody based on a supplied tablature. Some of it focuses on chords, using lots of heuristics to determine ‘comfort’ and ‘trickiness’ of each fingering, although that may not be very applicable to a machine. Most of the papers use some kind of graph approach to score fingerings and transitions between fingerings, which opens up a ton of mathematical and software tools for the analysis. Some papers focus on generating fingerings from specific positions in a guitar tab, while others leave open the opportunity to select which flavor of a particular chord should be played. For the purposes of this project, generating fingerings (really, machine positions) from specific positions in a guitar tab file is the more relevant problem.
Analysis Approach
The graph-based representation of the problem seemed like a great approach and something I could easily implement. The setup is fairly simple:
- Each potential fingering of a note is a node on the graph, potentially weighted by some heuristic
- The fingering generator I already developed for the chord analysis can be adapted to this
- Each potential transition between fingerings on adjacent notes is an edge on the graph, weighted by some heuristic
- The driving factor I chose for this weight was the acceleration required to move a finger between frets assuming a bang/bang constant acceleration profile
- The lowest-cost path from a node at the starting note to a node at the ending note is the ‘best’ fingering for the song
I immediately ran into issues with all of these points:
- How do you represent the position of an inactive finger in a node? In order to calculate the transition cost you need to know where every finger is at every point in time (even if not involved in the fingering of a note), but in order to minimize transition costs in a future note a finger may need to make some kind of setup move.
- The computation time to solve the graph grows exponentially as more nodes and edges are added. All of the papers avoid this issue by just solving a few measures of music at a time.
- Is the lowest-cost total path the ‘best’ fingering? Or is it the path with the ‘least-bad worst single transition’? Or does it even matter which is best as long as the path is achievable by the machine?
Idle Fingers
The problem with idle fingers isn’t just that you might want to start moving them in advance to reduce how quickly they need to move when eventually needed, but also the issue of moving idle fingers ‘out of the way’ of positions that non-idle fingers might need to be in. This is especially true for the barre finger which blocks all other fingers and often needs to move back up the fretboard after being used to clear space for the other fingers.
In the end, I used a few different methods to generate potential fret positions for fingers not actively fretting a note:
def __yield_potential_inactive_frets_of_finger(self, finger, active_fingering, reference_fingerings):
valid_frets = self.__get_accessible_frets(finger, active_fingering)
reference_frets_of_finger = list(set(reference_fingering[finger].fret for reference_fingering in reference_fingerings if reference_fingering[finger].fret in valid_frets))
for fret in reference_frets_of_finger:
yield fret #it was an old position, try leaving it there (although it may not be valid)
if active_fingering:
if finger == BARRE:
yield min(active_fingering.keys())-1
else:
for active_finger in active_fingering:
yield active_fingering[active_finger].fret
else:
yield self.config.idle_fingering[finger].fret- Consider moving the idle finger to a fret that it was recently used on. This can help set up the machine for frequent cases where music is somewhat repetitive.
- Every finger has an ‘idle position’ that it could be moved to, way up at the top of the neck. This is an especially useful case for moving the barre actuator out of the way.
- The non-barre fingers all have a ‘complementary finger’ that they cannot slide past. Consider moving an idle finger to the position of its complimentary finger to ensure that it gets out of the way.
Solving the Graph
My first attempt at solving the optimization problem basically copied the approach from a paper: set up a complete graph and use dijkstra’s algorithm to find the optimal path. This worked fine for one measure, and sometimes for two measures if they weren’t too busy. But anything over about a dozen or so notes made the algorithm really slow to complete!
My second approach was to use an A* search algorithm through a dynamically generated graph. This is handy because the entire graph does not need to be computed ahead of time, but to really take advantage of the method I need to come up with a ‘heuristic’ measurement of the expected remaining cost of any given node.
Because of the way the data structures in the algorithm work, it is important that the heuristic is never an over-estimate of the cost. The heuristic I decided on was to determine the lowest-possible cost transition between every note then sum them from the end of the sequence going backwards to the note in question. For most note sequences the heuristic was just zero, but for any with tricky chord changes it was able to capture the expected higher cost at that transition and prevent the algorithm from being overly aggressive about avoiding it.
position_heuristic_lookup = []
heuristic_cost = 0
for i in range(len(position_sequence),0,-1):
if i < len(position_sequence):
heuristic_cost += self.__get_lowest_transition_cost(position_sequence[i-1], position_sequence[i], times[i-1], durations[i-1], times[i])
position_heuristic_lookup.insert(0,heuristic_cost)Even with the dynamic A* algorithm in place it was difficult to solve a graph representing more than a few dozen notes, much less a whole song! My solution was to chop up songs into very small continuous sections, ideally while keeping measures together. Then, I would run the solver on two contiguous sections of music as one, with the goal of ‘solving’ the first section of notes while using the second set of notes only as a reference. After solving one section, the script advances by a single section (only half of the notes run through the solver) and the section that had been used only as a reference becomes the primary section being solved, while a new section is introduced as a ‘reference’ for the primary section.
This method was able to output a reasonable fingering for everything I threw at it in better than real-time (with a few exceptions where weird chord sequences made things run somewhat slower than real time). The core of the fingering solver is available in this python file, while the part that reads in the GuitarPro file and feeds it to the solver is here. The output is a text file that shows the time, tab, finger order, transition cost, and max acceleration for each note, along with the fret and string associated with each finger:
Evaluating Measure #1
t=0.000000: | | | | | 12 5/1/2/3/4 |1- 1: |2- 2: |3- 3: |4-12: 1 |5- 0: $ 15 a=0.04g
t=0.075000: | | | | | 11 5/1/2/3/4 |1- 1: |2- 2: |3-11: 1 |4-12: |5- 0: $ 14 a=0.04g
t=0.150000: | | | | | 10 5/1/2/3/4 |1- 1: |2-10: 1 |3-11: |4-12: |5- 0: $ 25 a=0.03g
t=0.225000: | | | | | 9 5/1/3/2/4 |1- 1: |2-10: |3- 9: 1 |4-12: |5- 0: $ 588 a=1.52g
t=0.300000: | | | | | 10 5/1/3/2/4 |1- 1: |2-10: |3- 9: |4-10: 1 |5- 0: $ 62 a=0.16g
t=0.375000: | | | | | 9 5/1/3/2/4 |1- 1: |2-10: |3- 9: 1 |4-10: |5- 0: $ 0 a=0.00g
t=0.450000: | | | | | 8 5/1/2/3/4 |1- 1: |2- 8: 1 |3- 9: |4-10: |5- 0: $ 138 a=0.18g
t=0.525000: | | | | | 7 5/1/3/2/4 |1- 1: |2- 8: |3- 7: 1 |4-10: |5- 0: $ 660 a=1.71g
t=0.600000: | | | | | 8 5/1/3/2/4 |1- 1: |2- 8: |3- 7: |4- 8: 1 |5- 0: $ 69 a=0.18g
t=0.675000: | | | | | 7 5/1/3/2/4 |1- 1: |2- 8: |3- 7: 1 |4- 8: |5- 0: $ 0 a=0.00g
t=0.750000: | | | | | 6 5/1/2/3/4 |1- 1: |2- 6: 1 |3- 7: |4- 8: |5- 0: $ 155 a=0.20g
t=0.825000: | | | | | 5 5/1/3/2/4 |1- 1: |2- 6: |3- 5: 1 |4- 8: |5- 0: $ 741 a=1.92gResults and Conclusions
Test Songs
Choosing a limited set of ‘representative’ guitar tablature is an impossible task. Instead of trying to make these impossible decisions myself I turned to the fingering algorithm paper by Konrad Ilczuk and Philip Skold, which included a variety of different songs, melodies, and scales chosen to evaluate their (human focused) algorithm and justifications for each inclusion. I wasn’t able to find freely available tablatures of all of the examples, but my test data set ended up with these songs from their list:
- Racer X – Technical Difficulties
- Deep Purple – Sometimes I Feel Like Screaming
- Led Zeppelin – Black Dog
- Led Zeppelin – The Ocean
- AC/DC – Thunderstruck
- A. Vivaldi – Summer (L’estate Presto)
Along with these additional songs:
- Several sweeping and scale exercise tabs (similar to the paper’s pentatonic and sweeping scales)
- Lynyrd Skynyrd – Sweet Home Alabama (chosen for its frequent shift between melody and chord)
- Rimsky Korsakov – Flight of the Bumblebee (chosen for its speed and range)
Limiting Strings Available to Actuators
One of the first things I noticed when running the solver was that it would frequently have trouble finding efficient ways to handle a fast sequence of notes on different frets all clustered on either the lowest or highest string. This was probably because only a limited number of fingers were allowed to be used on either the lowest string or highest string.
To a lesser degree these string restrictions also limited the ability to play melodies just before or after a chord, where finger positions are the most restricted. In the end, removing all string limitations from the actuators made the biggest impact to fingering solvability and significantly reduced the number and maximum magnitude of high acceleration movements required.
Limiting Frets Available to Actuators
As I increased the number of songs in my test dataset I kept finding more and more instances of fast melodies being played at the base of the guitar neck. While my chord analysis made me think that reaching frets 16 for the primary actuators and 20 for the secondary actuators would be sufficient, I now see that in order to even find a valid solution the limit needs to be expanded significantly.
My new baseline is a reach down to fret 20 for the primary actuators and fret 24 for the secondary actuators. This should ensure that a much larger variety of music is playable by the machine.
Fret-Change Dynamics
The main output of this study is to understand the speed and acceleration required to move the finger actuators along the fretboard. The majority of all note transitions in the selected songs (>95%) involved no significant acceleration (<0.1g) of the finger actuator in order to get the target fret in time to play the note. The is either because the order of the notes was convenient, or the pace of the song was slow enough to not demand much from the fret slide actuator.
The most common reason for high acceleration is when a finger needs to play two notes on two different frets with only one note being played by a different finger in between. Normally the jump is only a few frets, but it can be as high as four frets, as in the case of measure 313 of Summer:
For this section of music the fingering generator settled on a sequence that included two quick jumps by the ring finger. First, from fret #2 to fret #5, then back further from fret #5 to fret #1. Each jump occurs while a sixteenth note is being played by a different finger, lasting only 115 milliseconds. Despite the time in the calculation not including extra steps like disengaging/re-engaging the string with the fret, these fingering sequences already point to an acceleration requirement of at least 2G (\(20 m/s^2\)).
t=445.000000: | | | | | 3 *|1- 1: |2- 3: 1 |3- 2: |4- 4: a=0.00g
t=445.113636: | | | | | 5 *|1- 1: |2- 3: |3- 5: 1 |4- 5: a=1.45g
t=445.227273: | | | | | 6 *|1- 1: |2- 3: |3- 5: |4- 6: 1 a=0.43g
t=445.340909: | | | | | 5 *|1- 1: |2- 3: |3- 5: 1 |4- 6: a=0.00g
t=445.454545: | | | | | 3 *|1- 1: |2- 3: 1 |3- 5: |4- 6: a=0.00g
t=445.568182: | | | | | 1 *|1- 1: |2- 3: |3- 1: 1 |4- 6: a=1.99g
t=445.681818: | | | | 4 | *|1- 1: |2- 3: |3- 1: |4- 4: 2 a=0.10g
t=445.795455: | | | | 3 | *|1- 1: |2- 3: 2 |3- 1: |4- 4: a=0.00gOne of the few examples of a large jump by a single finger across multiple notes is in the 23rd measure of Flight of the Bumblebee. Here, the ring finger jumps from fret #1 all the way down to fret #9 across two notes (150ms total). While this is about the same 2G acceleration seen in the rest of the measure for single-note jumps, the large distance and time of the jump implies that the top speed of the finger was 6 meters per second! Compare that to the 4.5 m/s from Summer or the 1.73 m/s capability of strumbot.
There is probably room for improvement in the fingering algorithm, because a brief inspection of the fingering plan makes you wonder if there wasn’t somehow a better way to plan this out and avoid the abrupt moves. To be fair, the algorithm only penalizes acceleration, not power (acceleration \(*\) time).
t=26.100000: | | | 3 | | *|1- 1: |2- 2: |3- 3: |4- 3: 3 a=0.03g
t=26.175000: | | | | 0 | *|1- 1: |2- 2: |3- 3: |4- 3: a=0.00g
t=26.250000: | | | | 1 | *|1- 1: |2- 2: |3- 1: 2 |4- 3: a=0.10g
t=26.325000: | | | | 2 | *|1- 2: 2 |2- 2: |3- 1: |4- 3: a=0.08g
t=26.400000: | | | | | 10 *|1- 2: |2- 2: |3- 1: |4-10: 1 a=0.73g
t=26.475000: | | | | | 9 *|1- 2: |2- 2: |3- 9: 1 |4-10: a=2.05g
t=26.550000: | | | | | 8 *|1- 2: |2- 8: 1 |3- 9: |4-10: a=0.17g
t=26.625000: | | | | | 7 *|1- 2: |2- 8: |3- 7: 1 |4-10: a=1.71gThe only other common pattern associated with high acceleration requirements was the use of chords without a rest afterwards. In general, I assumed that the last 20% of the time associated with a note could elapse without the fret engaged (either by letting the string ring like a hammer-off or by muting the note early) otherwise some songs would require near-infinite acceleration to play! One interesting example of this is in Sweet Home Alabama where a barre chord preceds a non-barre chord, and the barre actuator needs to get out of the way of a finger actuator that needs to play on the same fret that the barre just used:
None of the other fingers have to do much to make this chord work, but the barre actuator has to move out of the way fast so that the index finger can reach fret #1 for the next note. This fingering is also interesting because it shows an almost complete regrip between the two chords (to minimize movement between frets), when a human player would likely optimize around not lifting fingers unnecessarily. Currently, the fingering algorithm does not penalize releasing strings, but this example shows how that could be a useful optimization to add in the future.
t=220.80: 3 | | | | | *|1- 3: 6 |2- 5: |3- 7: |4- 9: |5- 0: a=0.00g
t=221.10: 3 | | | | | *|1- 3: 6 |2- 5: |3- 7: |4- 9: |5- 0: a=0.00g
t=221.40: | | 0 0 | | *|1- 3: |2- 5: |3- 7: |4- 9: |5- 0: a=0.00g
t=221.70: 3 | 0 0 | | *|1- 3: 6 |2- 5: |3- 7: |4- 9: |5- 0: a=0.00g
t=221.85: 3 | 0 0 | | *|1- 3: |2- 3: 6 |3- 7: |4- 9: |5- 0: a=0.01g
t=222.00: | 3 3 2 1 1 *|1- 3: |2- 3: 54 |3- 2: 3 |4- 9: |5- 1: 654321 a=0.01g
t=222.60: | 3 2 0 1 0 *|1- 1: 2 |2- 3: |3- 2: 4 |4- 3: 5 |5- 0: a=0.51g
t=223.20: | 5 | | | | *|1- 1: |2- 5: 5 |3- 2: |4- 5: |5- 0: a=0.84g
t=223.50: | 5 7 | | | *|1- 1: |2- 5: 5 |3- 7: 4 |4- 7: |5- 0: a=0.33g
t=223.80: | 5 9 | | | *|1- 1: |2- 5: 5 |3- 7: |4- 9: 4 |5- 0: a=0.11g
t=223.95: | 5 7 | | | *|1- 1: |2- 5: 5 |3- 7: 4 |4- 9: |5- 0: a=0.00gImpact on Requirements
This analysis has let me update the fret requirements from the chord study based on note sequences found in a variety of music styles. The changes are:
- Some actuators must reach as high as fret #24, but all actuators must at least reach fret #20
- All actuators should be able to reach all strings
- Fretboard motions require speeds of at least 7m/s and accelerations of at least 2G.
While the first two changes aren’t much of a problem, the dynamic requirements determined from this study are a serious challenge. 7m/s at 2G acceleration equates to 140W of power per kg of finger actuator payload in order to move it! One saving grace is that this high power requirement is extremely infrequent (<5%), and lasts for a very short duration (<200ms) so using thermally limited actuators (like BLDC motors) driven (temporarily!) well past their standard limits could make it easier to achieve. Alternatively, looking into a non-linear (perhaps rotary) degree of freedom for short, fast fret changes could reduce the power requirements.
Another angle worth exploring is altering the fingering sequencing algorithm to seek out the smallest ever max acceleration for the entire path, instead of working to minimize the total cost of the entire path. This will be harder to implement with the dynamically created A* search methodology but would likely result in less demanding actuator requirements.
Before I iterate on the fretting and fingering algorithm again I want to divert back to the picking and fretting actuator design. Now that I know how important weight will be (for the fretting actuator at least) and have settled on which strings the actuators need to reach, I should be able to make more progress on the arm designs. Once I have a better understanding of the fret finger capabilities I should be able to include some timing limitations from them into the next iteration of the fingering algorithm.